Plus grand commun diviseur de nombres entiers

En mathématiques, le PGCD de nombres entiers différents de zéro est, parmi les diviseurs communs à ces entiers, le plus grand d'entre eux. PGCD signifie plus grand commun diviseur.

Par exemple, les diviseurs positifs de 30 sont, dans l'ordre : 1, 2, 3, 5, 6, 10, 15 et 30. Ceux de 18 sont 1, 2, 3, 6, 9 et 18. Les diviseurs communs de 30 et 18 étant 1, 2, 3 et 6, leur PGCD est 6. Ce qui se note : PGCD(30, 18) = 6.

Les diviseurs communs à plusieurs entiers sont les diviseurs de leur PGCD. Connaître le PGCD de deux nombres entiers non nuls a et b permet de simplifier la fraction a/b. Il est possible de le déterminer par divers raisonnements, dont l'algorithme d'Euclide.

Notation

Le PGCD de deux nombres entiers a et b est généralement noté PGCD(a, b) ou pgcd(a, b). On trouve parfois l'acronyme équivalent PGDC, mais PGCD est la version officielle.

PGCD(a, b) est parfois noté a∧b. Cette notation fait référence aux ensembles ordonnés : tout diviseur commun à a et b divise leur PGCD.

Les anglophones le nomment greatest common divisor, noté gcd(a, b), ou highest common factor, noté hcf(a, b).

Définition

Plus grand au sens usuel

Tout nombre entier n a pour diviseur 1, puisque n = n×1. Pour deux nombres entiers a et b, l'ensemble D de tous leurs diviseurs communs, n'est donc pas vide, puisqu'il contient 1.

L'ensemble des diviseurs d'un nombre entier non nul est fini a : tous les diviseurs sont inférieurs à a. Le PGCD de deux nombres entiers a et b dont au moins l'un des deux est non nul peut donc être défini comme le plus grand nombre appartenant à l'ensemble D de tous les diviseurs communs de a et b.

En particulier, comme tout nombre entier est un diviseur de zéro (car 0 × c = 0 quel que soit c) :

• pour tout entier a > 0, PGCD(a, 0) = PGCD(0, a) = a.

Cette définition ne s'étend pas à PGCD(0, 0), puisqu'il n'existe pas de plus grand diviseur de 0.

Plus grand au sens de la divisibilité

Mais il est aussi possible de prendre « plus grand » au sens de la divisibilité : (b est plus grand que a quand b est un multiple de a, soit a est un diviseur de b), ce qui conduit à la définition suivante :

• PGCD(a,b) est un diviseur de a et un diviseur de b ;
• si c est un diviseur de a et b alors c est un diviseur de PGCD(a,b) ;
• PGCD(a,b) ≥ 0.

Un tel entier existe bien, et il en existe un seul vérifiant ces trois propriétés qui est le PGCD au sens de la définition précédente quand (a,b) ≠ (0,0). Avec cette définition PGCD(0,0)=0.

La troisième condition PGCD(a,b) ≥ 0 n'est bien sûr pas utile quand on travaille sur les entiers naturels, où la relation de divisibilité est une relation d'ordre. Elle est nécessaire pour l'unicité dans le cas des entiers relatifs : en général deux nombres vérifient les deux premières conditions, le PGCD usuel et son opposé. Par exemple, deux nombres D vérifient

• D divise 30 et 18 ;
• tout entier qui divise 30 et 18 divise aussi D ;

à savoir 6 et -6.

Cette définition est aussi la plus susceptible d'être étendue à d'autres anneaux, comme l'anneau des polynômes à coefficients réels.

Propriétés

Le PGCD peut être défini pour des nombres entiers naturels ou relatifs. Mais tout diviseur d'un nombre entier est également diviseur de son opposé. Les calculs et démonstrations sur le PGCD s'effectuent donc en général sur des nombres entiers positifs, l'extension aux négatifs étant immédiate.

Exemples

En appliquant directement la définition on a :

• PGCD(a,a) = a ;
• plus généralement, si a est un diviseur de b, alors PGCD(a,b) = a ;
• si p est premier, alors PGCD(p, a) = 1 ou PGCD(p, a) = p.

PGCD et PPCM

Le PGCD de deux nombres entiers positifs a et b est lié avec leur PPCM (le plus petit de leurs multiples communs), par la relation

ab = PGCD(a, b)×PPCM(a, b).

Pour trois entiers relatifs non nuls a, b, c :

• pgcd(a, b) × ppcm(a, b) = |ab|
• $\operatorname {pgcd} (a,\operatorname {ppcm} (b,c))=\operatorname {ppcm} (\operatorname {pgcd} (a,b),\operatorname {pgcd} (a,c))$
• $\operatorname {ppcm} (a,\operatorname {pgcd} (b,c))=\operatorname {pgcd} (\operatorname {ppcm} (a,b),\operatorname {ppcm} (a,c))$

PGCD et combinaisons linéaires

• Soient a, b deux entiers non nuls, il est possible de remplacer l'un de deux nombres a ou b par a + b, ou par a - b, sans changer le PGCD.

$\operatorname {pgcd} (a,b)=\operatorname {pgcd} (a,b+a)=\operatorname {pgcd} (a,b-a)$ ;

• par conséquent, on peut ajouter ou retrancher à l'un des deux un multiple de l'autre. Plus formellement :

Théorème — Soient a, b, v trois entiers, alors PGCD(a, b) = PGCD(a + bv, b).

Cette propriété fonde l'algorithme d'Euclide, une méthode qui permet de déterminer le PGCD de deux nombres (voir plus bas).

• Le PGCD est compatible avec la multiplication par un entier naturel : soit k un entier naturel,

$\operatorname {pgcd} (ka,kb)=k\operatorname {pgcd} (a,b)$.

Par exemple PGCD(9, 12) = 3, en multipliant par 3 on obtient PGCD(27, 36) = 9.

• Une combinaison linéaire quelconque de a et b, c'est-à-dire un nombre de la forme au + bv, où u et v sont des entiers relatifs, est forcément un multiple de tout diviseur commun de a et b, en particulier de PGCD(a, b).
  On peut montrer (théorème de Bachet-Bézout) que le PGCD(a, b) est lui-même une combinaison linéaire de a et b. C'est donc la plus petite combinaison strictement positive :

  $\operatorname {pgcd} (a,b)=\min \left(\left\{au+bv\mid (u,v)\in \mathbb {Z} ^{2}\right\}\cap \mathbb {N} ^{*}\right)$.

Tout diviseur commun divise le PGCD

Clairement, tout diviseur du PGCD de deux nombres est aussi un diviseur commun de ces deux nombres. La réciproque est vraie y compris pour la première définition. Par exemple, si le PGCD de deux nombres entiers a et b est 6, les diviseurs communs à a et b seront ceux de 6, soit : 1, 2, 3, 6 et leurs opposés.

C'est une conséquence du théorème de Bachet-Bezout, un diviseur commun de a et b étant un diviseur d'une combinaison linéaire de ceux-ci. La propriété se démontre aussi directement par récurrence, en suivant l'algorithme d'Euclide

Preuve par soustractions successives

Il suffit de montrer que tout diviseur commun à deux entiers naturels non tous deux nuls b ≤ a divise leur PGCD. Soit c ≥ 1 ; en supposant que la propriété est vraie pour tous les couples (a, b) tels que a + b < c, elle l'est encore pour ceux tels que a + b = c : c'est évident si b = 0, et cela résulte de l'hypothèse de récurrence si b > 0, car les diviseurs communs à a et b (dont le plus grand) sont les mêmes que ceux communs à a – b et b.

Les diviseurs communs de deux nombres entiers sont donc exactement les diviseurs de leur PGCD. Cette propriété permet de démontrer l'équivalence des deux définitions ci-dessus.

Par exemple, si le PGCD de deux nombres entiers a et b est 6, les diviseurs communs à a et b seront ceux de 6, soit : 1, 2, 3, 6 et leurs opposés.

PGCD de trois nombres entiers ou plus

$\operatorname {pgcd} (x,y,z)=\operatorname {pgcd} (\operatorname {pgcd} (x,y),z)=\operatorname {pgcd} (x,\operatorname {pgcd} (y,z))$. On peut étendre à un nombre arbitraire d'éléments.

Nombres premiers entre eux

Des nombres entiers naturels sont dits premiers entre eux lorsqu'ils n'ont pas d'autre diviseur commun que 1, autrement dit, leur PGCD est égal à 1.

Si deux nombres entiers a et b ont pour PGCD le nombre d, alors les entiers a/d et b/d sont premiers entre eux.

PGCD et facteurs premiers

D'après le théorème fondamental de l'arithmétique, tout entier n naturel non nul s'écrit de manière unique à l'ordre près des facteurs comme un produit fini de nombres premiers. Le nombre de fois que l'entier premier p apparait dans cette écriture s'appelle la valuation p-adique de n, notée v_p(n). Un entier non nul m divise n si et seulement si pour tout p, v_p(m) ≤ v_p(n).

De fait, le pgcd d'une famille (a_i) d'entiers naturels est donné par :

$\mathrm {pgcd} (a_{i})=\prod _{p}p^{\min v_{p}(a_{i})}$

où le produit porte sur l'ensemble des nombres premiers (presque tous les facteurs du produit, hormis une quantité finie, sont égaux à 1).

On en déduit à nouveau que tout diviseur commun à une famille d'entiers non tous nuls divise leur pgcd.

Suites de Lucas et divisibilité forte

Toute suite de Lucas x_n = U_n(P, Q) associée à des paramètres P, Q premiers entre eux est à divisibilité forte, c.-à-d. : $\operatorname {pgcd} (x_{m},x_{n})=x_{\operatorname {pgcd} (m,n)}$ C'est le cas, par exemple, de :

• la suite de Fibonacci U_n(1, –1) (cf. « propriété 6 » de la suite de Fibonacci) ;
• la suite U_n(b + 1, b) = (bⁿ – 1)/(b – 1) des répunits en base b (pour tout entier b > 1) donc $\operatorname {pgcd} (b^{m}-1,b^{n}-1)=b^{\operatorname {pgcd} (m,n)}-1$.

Applications

Simplification de fractions

Une fraction irréductible est une fraction dans laquelle le numérateur et le dénominateur sont les plus proches possibles de 1. Cela revient à dire que le numérateur et le dénominateur sont premiers entre eux. La fraction irréductible égale à une fraction a/b donnée est celle dont le numérateur est a/d et le dénominateur b/d, où d = PGCD(a, b).

Exemple :

En sachant que PGCD(30, 18) = 6, puis en remarquant que ${\frac {30}{6}}=5$ et ${\frac {18}{6}}=3$, on déduit que ${\frac {30}{18}}={\frac {5}{3}}$, cette dernière fraction étant irréductible.

Équations diophantiennes

Certaines équations diophantiennes (c'est-à-dire des équations dont les paramètres et les solutions cherchées sont des nombres entiers) se résolvent par une division par un PGCD afin de se ramener à une équation équivalente mettant en jeu des nombres premiers entre eux.

Ainsi l'équation diophantienne ax + by = c d'inconnues x et y admet une infinité de solutions si et seulement si c est un multiple du PGCD de a et b. Lorsque c n'est pas un multiple du PGCD de a et b, elle n'admet aucune solution entière. Ces résultats sont une conséquence du théorème de Bachet-Bézout. La méthode classique de résolution d'une telle équation consiste à diviser l'équation par le PGCD de a et b, puis, en s'appuyant sur le théorème de Gauss, résoudre la nouvelle équation obtenue, de la forme a'x + b'y = c', où a' et b' sont premiers entre eux.

Une autre équation diophantienne classique est la recherche des triplets pythagoriciens. Un triplet pythagoricien est la donnée de trois nombres entiers x, y et z qui vérifient la relation de Pythagore : x² + y² = z². Cela revient à chercher tous les triangles rectangles dont les longueurs des côtés sont des nombres entiers. L'étude de cette équation se ramène à la recherche des nombres x, y et z premiers entre eux : si x, y et z sont des solutions de l'équation et que d est leur PGCD, alors x/d, y/d et z/d sont aussi des solutions de l'équation.

Détermination du PGCD

Le PGCD peut se calculer de façon efficace par l'algorithme d'Euclide et ses variantes. D'autres méthodes, plutôt à vocation pédagogique, peuvent être mises en pratique pour de petits nombres, comme celle utilisant la décomposition en facteurs premiers.

Décomposition en facteurs premiers

La décomposition en facteurs premiers permet de calculer le PGCD (voir #PGCD et facteurs premiers) : pour tout nombre premier p,

$v_{p}({\text{pgcd}}(a,b))=\min(v_{p}(a),v_{p}(b))$,

où $v_{p}$ est la valuation p-adique.

La première étape de cette méthode consiste à décomposer a et b en produits de nombres premiers. Si $a=p_{1}^{\alpha _{1}}\times p_{2}^{\alpha _{2}}\times \cdots \times p_{k}^{\alpha _{k}}$ et $b=p_{1}^{\beta _{1}}\times p_{2}^{\beta _{2}}\times \cdots \times p_{k}^{\beta _{k}}$ où tous les exposants vérifient $\alpha _{i}\geq 0$ et $\beta _{i}\geq 0$ alors le PGCD est donné par :

$\mathrm {pgcd} \left(a,b\right)=p_{1}^{\min \left(\alpha _{1},\beta _{1}\right)}\times p_{2}^{\min \left(\alpha _{2},\beta _{2}\right)}\times \cdots \times p_{k}^{\min \left(\alpha _{k},\beta _{k}\right)}$. Cependant le calcul de la décomposition en facteurs premiers est coûteux, cette méthode n'est pas utilisée en pratique (hors illustration à visée pédagogique).

Connaissant les décompositions en facteurs premiers de deux nombres entiers a et b, la décomposition en facteurs premiers de leur PGCD est constituée des mêmes facteurs que ceux de a et b, en prenant pour chaque facteur l'exposant minimal qui apparaît à la fois dans a et b : le plus petit exposant commun à a et b.

Exemple :

Avec les décompositions en facteurs premiers

360 = 2×2×2×3×3×5 = 2³×3²×5

et

48 = 2×2×2×2×3 = 2⁴×3

On remarque que les facteurs premiers communs sont 2 et 3. Le nombre 2 apparaît avec les exposant 3 et 4, donc son plus petit exposant commun est 3. Pour 3, le plus petit exposant commun est 1 (puisque 3 = 3¹). Le PGCD de 360 et 48 est donc 2³×3 = 24.

Une variante, pas fondamentalement plus efficace, est de calculer directement la décomposition en facteurs premiers du PGCD ^{[réf. nécessaire]} : en prenant les nombres entiers dans l'ordre, on teste pour chacun s'ils sont diviseurs communs à a et b. C'est-à-dire que l'on trouve un nombre k tel que a = ka′ et b = kb′, alors il suffit de calculer le PGCD de a′ et b′ car on a : $\mathrm {pgcd} \left(a,b\right)=\mathrm {pgcd} \left(ka^{\prime },kb^{\prime }\right)=k~\mathrm {pgcd} \left(a^{\prime },b^{\prime }\right).$

Exemple : pgcd(60,84). On voit successivement que : $\mathrm {pgcd} \left(60,84\right)=2\times \mathrm {pgcd} \left(30,42\right)=2\times 2\times \mathrm {pgcd} \left(15,21\right)=2\times 2\times 3\times \mathrm {pgcd} \left(5,7\right)$. Or, $\mathrm {pgcd} \left(5,7\right)=1.$, car 5 est premier, et ne divise pas 7. Donc, $\mathrm {pgcd} \left(60,84\right)=2\times 2\times 3=12$.

Algorithme d'Euclide

Par soustractions successives

Animation de l'algorithme d'Euclide par soustractions successives.

Le PGCD de deux nombres a et b est aussi celui de a et de b - a. Ceci justifie la méthode des soustractions successives employée par Euclide pour le calcul du PGCD, connue en histoire des mathématiques sous le nom d'anthyphérèse. Elle repose sur les relations suivantes qui constituent une caractérisation fonctionnelle du PGCD :

Algorithme d'Euclide par soustraction

pgcd(a,b) = pgcd(a, b - a) pour b ≥ a > 0

pgcd(a,b) = pgcd(b, a) pour a > b > 0 ou a = 0

pgcd(a, 0) = a

Exemple : pgcd(75, 60) = pgcd(60,75) = pgcd(60, 15) = pgcd(15,60)= pgcd(15,45) = pgcd(15, 30) = pgcd(15, 15) = pgcd(15, 0) = 15.

Par divisions euclidiennes

Algorithme d'Euclide.

Dans l'algorithme d'Euclide par soustraction, pour le calcul de pgcd(a, b), a ≤ b, a est soustrait successivement de b jusqu'à obtenir r < b. C'est le reste de la division euclidienne de a par b. Ce reste peut se calculer plus efficacement que par soustractions successives, en particulier si a est très supérieur à b.

L'algorithme d'Euclide est souvent donné en utilisant directement la division euclidienne, plus précisément le reste. Le reste de la division de a par b, avec b > 0, noté ici reste(a, b), qui est l'unique entier naturel vérifiant :

1. a = bq + reste(a, b) pour un certain q (le quotient) ;
2. 0 ≤ reste(a, b) < b.

L'algorithme d'Euclide par division euclidienne s'appuie sur la même propriété que celui par soustraction, dont on déduit que a et b ont même PGCD que b et reste(a, b), plus précisément il s'appuie sur les équations suivantes :

Algorithme d'Euclide

pgcd(a, b) = pgcd( b, reste(a, b) ) pour b ≠ 0

pgcd(a, 0) = a

Comme, par définition de la division euclidienne, reste(a, b) < b, le second terme décroît strictement tant qu'il est strictement positif, d'où la terminaison de l'algorithme avec une valeur nulle pour ce second terme.

En reprenant le même exemple que pour l'algorithme par soustraction on obtient :

Exemple : pgcd(75, 60) = pgcd(60, 15) = pgcd(15, 0) = 15.

Algorithme du PGCD binaire

L'algorithme du PGCD binaire est une variante de l'algorithme d'Euclide qui est utile quand les nombres sont codés en binaire.

Notes et références

• Cet article est partiellement ou en totalité issu de l'article intitulé « Plus grand commun diviseur » (voir la liste des auteurs).

Bibliographie

• André Deledicq, Mathématiques Lycée : tout le programme de la seconde à la terminale, Éditions de la Cité, 1998
• Michel Demazure, Cours d'algèbre, Cassini, 2008 (ISBN 978-2-84225-127-7)
• W. Gellert, H. Küstner, M. Hellwich et H. Kästner (trad. de l'allemand par un collectif, sous la direction de Jacques-Louis Lions), Petite encyclopédie des mathématiques [« Kleine Enzyklopädie der Mathematik »], Didier, 1980