Plus grand commun diviseur

Enarithmétique élémentaire, leplus grand commun diviseurouPGCDde deux nombres entiersnon nuls est le plus grand entier qui lesdivisetous les deux. Par exemple, le PGCD de 20 et de 30 est 10, puisque leursdiviseurscommuns sont 1, 2, 5 et 10.
Cette notion s'étend auxentiers relatifsgrâce aux propriétés de ladivision euclidienne. Elle se généralise aussi auxanneaux euclidienscomme l'anneau despolynômessur uncorps commutatif.
La notion de PGCD peut être définie dans toutanneau commutatif. Cependant, l'existence d'un PGCD de deux éléments quelconques n'est plus garantie, mais c'est le cas pour des classes d'anneaux (plus générales que les seuls anneaux euclidiens) comme lesanneaux factoriels. Un anneau pour lequel cette propriété d'existence est satisfaite est appeléanneau à PGCD.
Le PGCD de deux entiersa{\displaystyle a}etb{\displaystyle b}se note :PGCD⁡(a,b){\displaystyle \operatorname {PGCD} (a,b)}.
Par extension, le PGCD d'unefamilled'entiersai{\displaystyle a_{i}}est notéPGCD⁡(ai){\displaystyle \operatorname {PGCD} (a_{i})}.
PGCD⁡(a,b){\displaystyle \operatorname {PGCD} (a,b)}est parfois notéa∧b{\displaystyle a\wedge b}. Cette notation fait référence aux ensembles ordonnés : tout diviseur commun àa{\displaystyle a}etb{\displaystyle b}divise leur PGCD.
Étant donné une famille (finie ou infinie) d'entiers relatifsai{\displaystyle a_{i}}non tous nuls, l'ensemble des diviseurs communs auxai{\displaystyle a_{i}}est une partie finie et non vide deZ{\displaystyle \mathbb {Z} }:
Cet ensemble admet donc unplus grand élémentd{\displaystyle d}, appelé le PGCD de la famille desai{\displaystyle a_{i}}.
Par exemple, les diviseurs communs à 36, 48 et 60 sont 1, 2, 3, 4, 6 et 12 doncPGCD⁡(36,48,60)=12{\displaystyle \operatorname {PGCD} (36,48,60)=12}.
Usuellement, pour des nombres entiers, on considère uniquement des PGCD positifs et la notion de « plus grand » correspond bien à la notion d'ordre usuelle pour les nombres. Pour d'autres cas, le « plus grand » de PGCD ne correspond pas forcément à larelation d'ordrehabituelle mais aupréordrede divisibilité, donc à la définition suivante (équivalente, dans unanneau commutatif unitaire, à ladéfinition par les idéaux— voir plus bas) :
En ce sens, –3 et 3 sont tous deux des PGCD de 6 et 9. C'est cette définition qui est adoptée pour définir lePGCD dans un anneau commutatifquelconque, ou pour le PGCD denombres rationnels. Pour le cas de nombres entiers, on préfère en général prendre le PGCD positif, ce qui permet de faire en sorte qu'il soit bien le plus grand au sens courant du terme. Et même, on ne précise pas qu'on souhaite le PGCD positif quand on désigne le PGCD comme unique.
Évidemment, celui des deux PGCD qui est positif est également le plus grand diviseur au sens de la relation d'ordre habituelle sur les nombres, mais cette assertion n'aura plus de sens dans des anneaux plus généraux, comme les anneaux de polynômes — et encore, même dans l'anneau des entiers, elle est contredite dans le cas dePGCD⁡(0,0){\displaystyle \operatorname {PGCD} (0,0)}, que nous examinerons plus loin.
Dans ce paragraphe, on utilise la définition générale donnéeplus haut:d{\displaystyle d}est un PGCD dea{\displaystyle a}etb{\displaystyle b}sid{\displaystyle d}divisea{\displaystyle a}etb{\displaystyle b}etd{\displaystyle d}est divisible par tout élément divisanta{\displaystyle a}etb{\displaystyle b}.
Premier point de vue : c'est le plus évident : on se place dans le corpsQ{\displaystyle \mathbb {Q} }des rationnels. Alors pourp1/q1{\displaystyle p_{1}/q_{1}}etp2/q2{\displaystyle p_{2}/q_{2}}deux rationnels non tous deux nuls, tout rationnel non nul est un PGCD dep1/q1{\displaystyle p_{1}/q_{1}}etp2/q2{\displaystyle p_{2}/q_{2}}(Q{\displaystyle \mathbb {Q} }étant un corps, tout rationnel autre que 0 divise 1, et 1 divise tout rationnel). Par convention, on choisit 1 comme PGCD. Dans le cas où les deux fractions sont nulles, le PGCD vaut encore 0.
Note : on montre que A est un corps si et seulement siA{\displaystyle A}est unanneau unitairedont les seuls idéaux sont{0}{\displaystyle \{0\}}etA{\displaystyle A}. On comprend facilement, avec la définition du paragraphe 2.1, que deux éléments non tous deux nuls deA{\displaystyle A}admettent n'importe quel élément non nul deA{\displaystyle A}comme PGCD, et on choisit 1 (le neutre de la seconde loi) par convention. La notion de PGCD n'a donc pas beaucoup d'intérêt dans un corps.
Deuxième point de vue : il consiste à considérer qu'une fractionp/q{\displaystyle p/q}en divise une autrep′/q′{\displaystyle p'/q'}non pas s'il existe une fractiona/b{\displaystyle a/b}telle que(p/q)×(a/b)=p′/q′{\displaystyle (p/q)\times (a/b)=p'/q'}(toujours vrai sip{\displaystyle p}ne vaut pas 0 : prendrea=q×p′{\displaystyle a=q\times p'}etb=p×q′{\displaystyle b=p\times q'}) mais seulement s'il existe unentierc{\displaystyle c}tel que(p/q)×c=p′/q′{\displaystyle (p/q)\times c=p'/q'}.
De façon analogue au paragraphe sur les idéaux, un PGCD dep1/q1{\displaystyle p_{1}/q_{1}}etp2/q2{\displaystyle p_{2}/q_{2}}est une fractionp/q{\displaystyle p/q}telle que(p1/q1)×Z+(p2/q2)×Z=(p/q)×Z{\displaystyle (p_{1}/q_{1})\times \mathbb {Z} +(p_{2}/q_{2})\times \mathbb {Z} =(p/q)\times \mathbb {Z} }. Mais attention, les objets manipulés ici ne sont pas des idéaux, ni des pseudo sous-anneaux deQ{\displaystyle \mathbb {Q} }, seulement des sous-groupes.
Finalement, on trouvep=±PGCD⁡(p1,p2){\displaystyle p=\pm \operatorname {PGCD} (p_{1},p_{2})}etq=PPCM⁡(q1,q2){\displaystyle q=\operatorname {PPCM} (q_{1},q_{2})}.
De même, on aPPCM⁡(p1/q1,p2/q2)=±PPCM⁡(p1,p2)PGCD⁡(q1,q2){\displaystyle \operatorname {PPCM} (p_{1}/q_{1},p_{2}/q_{2})=\pm {\frac {\operatorname {PPCM} (p_{1},p_{2})}{\operatorname {PGCD} (q_{1},q_{2})}}}.
Le PGCD obtenu suivant le deuxième point de vue est également un PGCD possible quand on se place sur le corpsQ{\displaystyle \mathbb {Q} }. Les calculatrices et les logiciels de calcul choisissent l'un ou l'autre suivant le choix des programmeurs (par exempleMapleadopte le premier point de vue, laCasio Graph 100+et laTI-92le second).
Un inconvénient du second point de vue est que le PGCD d'une famille infinie de rationnels n'existe pas toujours. Par exemple, la famille des fractions1n{\displaystyle {\frac {1}{n}}},n{\displaystyle n}allant de 1 à l'infini parmi les entiers, n'admet pas de PGCD.
On peut encore étendre les définitions précédentes avec desnombres réels: le premier point de vue conduit à un PGCD de 1 pour tout couple de réels non tous deux nuls.
Le second point de vue dit que pour deux réels quelconquesa{\displaystyle a}etb{\displaystyle b}, s'il existe un réelc{\displaystyle c}tel quea=u×c{\displaystyle a=u\times c}etb=v×c{\displaystyle b=v\times c}avecu{\displaystyle u}etv{\displaystyle v}rationnels, on choisitPGCD⁡(a,b)=|c|×PGCD⁡(u,v){\displaystyle \operatorname {PGCD} (a,b)=|c|\times \operatorname {PGCD} (u,v)}, suivant la définition des PGCD de rationnels vue ci-dessus (2point de vue).
Pour deux réelsa{\displaystyle a}etb{\displaystyle b}tels queab{\displaystyle {\frac {a}{b}}}soit irrationnel (sib=0{\displaystyle b=0}, on est dans la situation précédente) on est obligé de revenir au premier point de vue d'oùPGCD⁡(π,2)=1{\displaystyle \operatorname {PGCD} (\pi ,{\sqrt {2}})=1}; à noter que le PPCM présente le même problème, mais il est déterminé parPGCD⁡(a,b)×PPCM⁡(a,b)=|a×b|{\displaystyle \operatorname {PGCD} (a,b)\times \operatorname {PPCM} (a,b)=|a\times b|}. (PPCM⁡(π,2)=π×2{\displaystyle \operatorname {PPCM} (\pi ,{\sqrt {2}})=\pi \times {\sqrt {2}}}.)
Chaque calculateur se plaçant dans la continuité de son comportement concernant les rationnels,Maple répond suivant le premier point de vue, la Casio Graph 100+ selon le second ; laTi-92n'a pas de réponse.
Le PGCD dans l'anneauR[X]{\displaystyle \mathbb {R} [X]}vérifie la définition donnée plus haut. Mais cette fois, pour deux polynômesf(x){\displaystyle f(x)}etg(x){\displaystyle g(x)}non nuls, il y a une infinité de PGCD possibles : en effet, tout PGCD def(x){\displaystyle f(x)}etg(x){\displaystyle g(x)}multiplié par un réel non nul est aussi un PGCD def(x){\displaystyle f(x)}etg(x){\displaystyle g(x)}. Pour définir un PGCD unique il y a deux conventions possibles : ou bien on pose par convention que le PGCD doit être unpolynôme unitaire, ou bien on choisit le polynôme dont le coefficient dominant est le PGCD des coefficients dominants de A et B, en employant la définition du paragraphe précédent pour les PGCD de réels.
À titre d'exemple, le logiciel (propriétaire) de calcul formelMaplechoisit la première option quand les polynômes sont à coefficients entiers, la seconde sinon, tandis que les calculatrices Casio optent toujours pour la seconde convention.
Si l'on ne dispose pas de moyen automatisé (logiciel ou calculatrice), on peut toujours trouver « manuellement » le PGCD de 2 polynômes en transposant pour ces polynômes l'algorithme d'Euclideservant à trouver le PGCD de deux nombres entiers (voiricicomment on peut effectuer la division de deux polynômes).
La définition générale du PGCD dans un anneau (unitaire — ou même unpseudo-anneau) commutatifA{\displaystyle A}est celle donnéeplus haut, et s'étend à une famille quelconque (éventuellement infinie) : le plus grand commun diviseur d'une familleai{\displaystyle a_{i}}est le plus grand diviseur commun auxai{\displaystyle a_{i}}au sens de la divisibilité.
L'existence du PGCD de deux éléments (tout comme duPPCM) est certaine dans unanneau factoriel, pas toujours dans d'autres anneaux.
Par exemple, dans l'anneauZ[i3]{\displaystyle \mathbb {Z} \left[i{\sqrt {3}}\right]},4{\displaystyle 4}et2+2i3{\displaystyle 2+2i{\sqrt {3}}}admettent2{\displaystyle 2}et1+i3{\displaystyle 1+i{\sqrt {3}}}comme diviseurs, mais aucun élément divisible simultanément par2{\displaystyle 2}et1+i3{\displaystyle 1+i{\sqrt {3}}}ne les divise.
Le PGCD dea{\displaystyle a}etb{\displaystyle b}n'est pas toujours unique, mais deux quelconques PGCD dea{\displaystyle a}etb{\displaystyle b}sont, par définition, toujoursassociés, c'est-à-dire que chacun est divisible par l'autre.
Dans unanneau principal, il existe des élémentsu{\displaystyle u}etv{\displaystyle v}(non uniques) tels quePGCD⁡(a,b)=au+bv{\displaystyle \operatorname {PGCD} (a,b)=au+bv}(théorème de Bachet-Bézout).
Dans unanneau euclidien, une forme de l'algorithme d'Euclidepeut être utilisée pour calculer le PGCD.
L'unicité peut dans certains cas être rétablie en posant une contrainte supplémentaire — comme la positivité dans le cas des entiers relatifs. Par exemple, dans l'anneau des polynômes à coefficients dans un corps commutatif, le PGCD est unique si l'on exige qu'il soit unitaire ou nul.
La définition de ce paragraphe est une reformulation de la précédente.
Dans l'anneau commutatif unitaireA{\displaystyle A}, on note(x){\displaystyle (x)}l'idéal principalengendré par l'élémentx{\displaystyle x}, i.e. l'ensemble des multiples dex{\displaystyle x}par un élément deA{\displaystyle A}. Alors :
Dans un anneau principal, cela équivaut à(a)+(b)=(d){\displaystyle (a)+(b)=(d)}.
Cette reformulation ne vaut pas dans unpseudo-anneaucar l'ensemble des multiples dex{\displaystyle x}peut alors être strictement inclus dans l'idéal engendré parx{\displaystyle x}. Par exemple dans le pseudo-anneau2Z{\displaystyle 2\mathbb {Z} }, 2 est un PGCD de 8 et 12 mais l'idéal engendré par 4, strictement plus petit que celui engendré par 2, contient aussi 8 et 12.
Dans un anneau non commutatif, un élément peut admettre des « diviseurs à droite » et des « diviseurs à gauche ». On peut dans certains cas définir un PGCD à droite et/ou un PGCD à gauche. Mais l'existence de l'un n'implique pas forcément celle de l'autre, et l'existence commune n'implique pas forcément l'égalité.
Demander à un calculateur électronique le PGCD de deux matrices n'est pas forcément interprété au sens de l'algèbre linéaire. Par exemple, une TI-92 interrogée sur le PGCD de deux matrices de même taille répond en donnant la matrice composée des PGCD des éléments de même position des deux matrices.