Plus grand commun diviseur de nombres entiers

vignette|Le PGCD de 22050 et 1512 est 126 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. On dit aussi plus grand diviseur commun (PGDC). 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 et permet notamment de simplifier la fraction .

Notations Le PGCD de deux nombres entiers et est généralement noté ou . On trouve parfois l'acronyme équivalent PGDC, mais PGCD est la version officielle en France..

est parfois noté . Cette notation fait référence au fait que le PGCD est la borne inférieure de pour la relation de divisibilité (tout diviseur commun à et divise leur PGCD) ; la borne supérieure est le PPCM noté .

Les anglophones le nomment greatest common divisor, noté , ou highest common factor, noté .

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 listesLa démonstration formelle détaillée prouvant que l'ensemble des diviseurs communs à a et b possède un maximum sort du cadre de cet article. Elle s'appuie sur le fait que tout sous ensemble de , comme de , contenant un nombre fini d'éléments possède un élément minimal et un élément maximal..

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

si b divise a, , ce qui est une généralisation des propriétés 2 et 3.

tout diviseur commun à a et b divise . si , alors : 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 : on pose , alors il existe m et n tels que et avec . Donc p divise car . D'après la propriété 5, on a donc : . Or , car sinon m et n auraient au moins un diviseur commun et p ne serait alors plus le PGCD : m et n n'ont donc aucun autre diviseur commun que 1, et, par le même raisonnement, c'est aussi le cas de et n. Donc , et . Plus généralement, pour trois entiers tels que , on a : . Ceci se démontre en remarquant que : et ainsi de suite. : cette propriété se démontre comme la propriété précédente. Plus généralement, pour trois entiers on a : . Ceci se démontre en remarquant que et ainsi de suite. si p est un nombre premier, alors si p divise a, et sinon . les nombres et sont entiers et premiers entre eux.

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 qui donne p comme PGCD, ou 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 : . On cherche le PGCD de 27 et de 5 : . 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 (avec ), alors on applique directement . Cette égalité résulte de la propriété 7, que l'on applique de façon itérative. Donc rechercher revient à chercher . La méthode est donc la suivante : si b divise a, alors ; sinon, on divise a par b et si le reste r divise b, ; sinon, la division de b par r 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 : 3 divise 21, donc On cherche le PGCD de 1285 et de 6 : et donc .

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 : R2 : R3 :

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 est le plus grand entier divisant chacun des entiers a. Cette définition amène notamment les propriétés suivantes :

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 , on dit que les a 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, b)=PGCD(a, b) la relation R1 entre PGCD et PPCM devient : PGCD(a, b)×PPCM(a, b)=|a×b|

Applications et autres propriétés 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 donnée est celle dont le numérateur est et le dénominateur , où .

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. Donc si et sont deux entiers, et , …, sont les nombres premiers, rangés en ordre croissant, qui divisent ou , la décomposition de en produit de facteurs premiers est de la forme ….. = Le nombre de fois que l'entier premier p apparait dans cette écriture s'appelle la valuation p-adique de n, notée vp(n). Un entier non nul m divise n si et seulement si pour tout p, vp(m) ≤ vp(n).. De même, celle de est de la forme . Alors : .

Cette propriété permet de calculer le PGCD de toute famille d'entiers, et de démontrer que tout diviseur commun aux éléments de cette famille divise leur PGCD.

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 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 de la forme au + bv : . Suites de Lucas et divisibilité forte Toute suite de Lucas x = U(P, Q) associée à des paramètres P, Q premiers entre eux est à divisibilité forte, :

C'est le cas, par exemple, de : la suite de Fibonacci U(1, –1) (cf. « propriété 6 » de la suite de Fibonacci) ; la suite U(b + 1, b) = (b – 1)/(b – 1) des répunits en base b (pour tout entier b > 1) donc .

É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 ax + by = 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.

Méthodes de détermination du PGCD Le PGCD peut se calculer par l'algorithme d'Euclide et ses variantes. D'autres méthodes peuvent également être mises en pratique pour de petits nombres, comme celle utilisant la décomposition en facteurs premiers.

Algorithme d'Euclide et variantes Par soustractions successives vignette|Algorithme d'Euclide pour calculer le PGCD 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, qui emploie les trois propriétés suivantes :

PGCD(a ,b) = PGCD(a, b – a) pour b ≥ a > 0 PGCD(a, b) = PGCD(b, a) 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

vignette|Algorithme d'Euclide pour calculer le PGCD par divisions successives.|200x200px