# Plus grand commun diviseur de nombres entiers

En mathématiques, le plus grand commun diviseur ou PGCD de nombres entiers différents de zéro est le plus grand entier pouvant les diviser tous. Il est possible de le déterminer par divers raisonnements, dont l'algorithme d'Euclide. Ainsi, par exemple, les diviseurs positifs de 30 sont, par l'ordre croissant : 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 ou pgcd (30,18) = 6 ou encore 30∧18 = 6.
Initialement défini par Euclide pour des entiers naturels non nuls, le concept de PGCD a depuis été étendu au nombre zéro et aux entiers relatifs. Sous certaines conditions, il peut aussi être étendu à d'autres ensembles mathématiques.
Connaître le PGCD de deux nombres entiers non nuls a et b permet notamment de simplifier la fraction a/b.

## 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\land b$. Cette notation fait référence au fait que le PGCD est la borne inférieure de $\{a,b\}$ pour la relation de divisibilité (tout diviseur commun à $a$ et $b$ divise leur PGCD) ; la borne supérieure est le PPCM noté $a\lor b$.
Les anglophones le nomment greatest common divisor, noté gcd(a, b), ou highest common factor, noté hcf(a, b).

## PGCD d'entiers naturels non nuls

Dans ce chapitre, le mot "entier'" désigne un entier naturel non nul, et les nombres désignés par des lettres, comme a, b, c, etc. sont de tels entiers. Les principales notions mathématiques supposées connues sont les entiers naturels, les opérations usuelles d'addition, soustraction, multiplication et division qui peuvent leur être appliquées, et le fait qu'on puisse ranger tout groupe d'entiers naturels en ordre croissant (ou décroissant).

### Existence du PGCD de deux entiers

Deux entiers a et b distincts ont au moins 1 comme diviseur commun, car 1 divise tout entier. Si on classe par ordre croissant tous les diviseurs de a d'une part et tous ceux de b d'autre part, le PGCD(a, b) sera le plus grand nombre qui appartient à ces deux listes.
Lorsque 1 est le seul diviseur commun à a et b, les nombres a et b sont dits premiers entre eux.

### Propriétés élémentaires du PGCD de deux entiers

* PGCD(a, b) = PGCD(b, a)
* PGCD (a, 1) = 1
* PGCD (a, a) = a
* si b divise a, PGCD(a, b)=b, ce qui est une généralisation des propriétés 2 et 3.
* PGCD(a×c, b×c) = c×PGCD(a, b)
* tout diviseur commun à a et b divise PGCD(a, b).
* si a>b, alors PGCD(a, b)=PGCD(a-b, b) : cette propriété est importante pour comprendre le calcul du PGCD par la méthode des soustractions successives. On peut la démontrer de façon élémentaire comme suit : posons p=PGCD(a, b), alors a=m×p et b=n×p avec m>n. Donc p divise a-b car a-b= p×(m-n). D'après la propriété 3, on a donc : PGCD(a-b, b)=p×PGCD(m-n, n). Or PGCD(m, n) =1, car sinon m et n auraient au moins un diviseur commun d>1 , d×p diviserait donc a et b, et d×p>p, ce qui est impossible puisque p est le PGCD de a et b : m et n n'ont donc aucun autre diviseur commun que 1, et, par le même raisonnement, c'est aussi le cas de m-n et n. Donc PGDC(m-n, m)=1, et PGCD(a-b, b)=p=PGCD(a, b). Plus généralement, pour trois entiers a, b et c tels que a>c×b, on a : PDCD(a-c×b, b)=PGCD(a, b). Ceci se démontre en remarquant que : PGCD(a, b)=PGCD(a-b, b)=PGCD(a-2b, b) et ainsi de suite.
* PGCD(a, b)=PGCD(a+b, b) : cette propriété se démontre comme la propriété 7. Plus généralement, pour trois entiers a, b, c on a : PGCD(a+c× b, b)=PGCD(a, b). Ceci se démontre en remarquant que : PGCD(a, b)=PGCD(a+b, b)=PGCD(a+2b, b) et ainsi de suite.
* si p est un nombre premier PGCD(a, p)=p si p divise a, et sinon PGCD(a, p)=1.

### Calcul du PGCD de deux entiers

Plusieurs méthodes permettent de calculer le PGCD de deux entiers. Deux sont explicitées ci-dessous :
* Calcul par soustractions successives : aussi appelée algorithme d'Euclide, cette méthode utilise de façon récurrente les propriétés 7 et 1, ainsi que la propriété 3 jusqu'à trouver l'expression PGCD(p, p) qui donne p comme PGCD, ou PGCD(q, 1) qui indique que le PGCD est 1. Exemples d'application :
** On cherche le PGCD de 75 et 27. La suite d'opérations est la suivante :75∧27=(75-27)∧27=48∧27=27∧21=6∧21=15∧6=9∧6=6∧3=3∧3=3 .
** On cherche le PGCD de 27 et de 5 : 27∧5=22∧5=17∧5=12∧5=7∧5=5∧2=3∧2=2∧1=1.
* Calcul par division euclidienne : le calcul par soustractions peut être assez long à réaliser si a ou b sont très grands. Il peut être plus rapide d'utiliser la division euclidienne en s'appuyant sur le fait que, si r est le reste de la division de a par b (a>b), alors PGCD(a, b)=PGCD(b, r). Cette égalité résulte de la propriété 7, que l'on applique de façon itérative : PGCD(a, b)=PGCD(a-b, b)=PGCD(a-2b, b)...Donc rechercher PGCD(a, b) revient à chercher PGCD(b, r). La méthode est donc la suivante: si b divise a, alors PGCD(a, b)=b ; sinon, on divise a par b et si le reste r divise b, PGCD(a, b)=PGCD(b, r)=r ; sinon, la division de b par donne un reste s, et si s divise r, s est le PGCD recherché, etc. Exemples d'application :
** On cherche le PGCD de 75 et 27 : 75=2×27+21 ; 27=21+6 ; 21=3×6+3; 3 divise 21, donc 75∧27=3
** On cherche le PGCD de 1285 et de 6 : 1285=214×6+1 et donc 1285∧6=1.

### PGCD et PPCM

Le PGCD d'entiers a, b et c est lié avec leur PPCM (le plus petit de leurs multiples communs), par plusieurs relations :
   * R1 : PGCD(a, b)×PPCM(a, b)=a×b
   * R2 : PGCD(a, PPCM(b, c))=PPCM(PGCD(a, b), PGCD(a, c))
   * R3 : PPCM(a, PGCD(b, c))=PGCD(PPCM(a, b), PPCM (a, c))

### PGCD de plusieurs entiers

Le PGCD de trois entiers ou plus est défini par extension de la définition du PGCD de deux entiers. Ainsi PGCD($a_{1},a_{2},...,a_{n}$) est le plus grand entier divisant chacun des entiers $a_{i}$. Cette définition amène notamment les propriétés suivantes :
* PGCD($a_{1},a_{2},...,a_{n}$) = PGCD($a_{1}$, PGCD($a_{2},....,a_{n}$)) = PGCD($a_{1},a_{2}$, PGCD($a_{3},....,a_{n}$))
* PGCD($a_{1},a_{2},...,a_{n}$) = PGCD(PGCD($(a_{1},a_{2})$, PGCD($a_{3},....,a_{n}$)) = PGCD(PGCD($a_{1},a_{2},a_{3})$, PGCD($a_{4},....,a_{n}$))
Ceci montre notamment qu'on peut calculer le PGCD de trois entiers ou plus en le calculant de proche en proche par les méthodes de calcul du PGCD de deux entiers.
Lorsque PGCD($a_{1},a_{2},...,a_{n}$) = 1, on dit que les $a_{i}$ sont premiers entre eux dans leur ensemble. Attention : ceci ne veut pas dire qu'ils sont nécessairement premiers entre eux deux à deux . Ainsi, par exemple, les nombres 6, 10 et 15 sont bien premiers entre eux dans leur ensemble, mais 6 n'est premier ni avec 10 ni avec 15.

## PGCD d'entiers relatifs

La notion de PGCD peut être assez naturellement étendue au nombre zéro, ainsi qu'aux entiers relatifs.

### PGCD relatif au nombre zéro

En conservant la définition du PGCD pour les entiers naturels non nuls, on peut écrire pour tout entier naturel a non nul : PGCD(a, 0)=a. En effet tout entier a non nul divise 0. La définition de PGCD(0, 0) est en revanche plus délicate, car, contrairement aux autres entiers naturels, 0 n'a pas de plus grand diviseur, et n'est pas son propre diviseur. Il est d'usage conventionnel de poser PGCD(0, 0)=0, ce qui a pour avantage d'étendre à zéro en les conservant toutes les propriétés relatives au PGCD d'entiers naturels non nuls, notamment les propriétés 3 (PGCD(a, a)=a) et 5 (PGCD(a×c, b×c) = c×PGCD(a, b)).

### PGCD d'entiers relatifs

Rappelons que les entiers relatifs sont les entiers naturels (0, 1, 2, 3, ...) et leurs opposés (0, -1, -2, -3,...). Notons pour tout entier relatif c : |c|=c si c>0 et |c|=-c si c<0. La définition du PGCD pour les entiers naturels peut alors être étendue à tous entiers relatifs a et b par : PGCD (a, b)= PGCD(|a|, |b|).
Cela revient à se ramener à des raisonnements concernant les entiers naturels. Les propriétés du PGCD ainsi définies sont très semblables à celles énoncées pour les entiers naturels, avec quelques adaptations :
* la propriété 3 devient : PGCD (a, a) = |a|
* la propriété 4 devient : si b divise a, PGCD(a, b)=|b|
* la propriété 5 devient : PGCD(a×c, b×c) =|c|×PGCD(a, b)
* les propriétés 7 et 8 peuvent être fusionnées et énoncées ainsi : pour tous entiers relatifs a, b et c, PGCD(a+c×b)=PGCD(a, b)
* la relation R1 entre PGCD et PPCM devient : PGCD(a, b)×PPCM(a, b)=|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
### PGCD et combinaisons linéaires

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

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
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.

### 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$^n$ – 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).
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$^2$ + y$^2$ = z$^2$. 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.
Avec les décompositions en facteurs premiers
    360 = 2×2×2×3×3×5 = 2$^3$×3$^2$×5
et
    48 = 2×2×2×2×3 = 2$^4$×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$^1$). Le PGCD de 360 et 48 est donc 2$^3$×3 = 24.
Une variante, pas fondamentalement plus efficace, est de calculer directement la décomposition en facteurs premiers du PGCD : 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

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

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 :
* a = bq + reste(a, b) pour un certain q (le quotient) ;
* 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.