Plus grand commun diviseur

Pour les articles homonymes, voir Pgcd (homonymie).

Cet article ou cette section concernant les mathématiques doit être recyclé.

Une réorganisation et une clarification du contenu est nécessaire. Discutez des points à améliorer en page de discussion.

Pour une introduction, voir PGCD de nombres entiers.

En arithmétique élémentaire, le plus grand commun diviseur, abrégé en général PGCD, de deux nombres entiers naturels non nuls est le plus grand entier qui divise simultanément ces deux entiers.

Par exemple le PGCD de 20 et 30 est 10. En effet, leurs diviseurs communs sont 1, 2, 5 et 10.

La notion peut se définir sur les entiers relatifs, et s'étudier en utilisant en particulier les propriétés de la division euclidienne. La définition du PGCD et beaucoup de ses propriétés se généralisent alors aux anneaux euclidiens comme l'anneau des polynômes sur un corps commutatif.

On peut en fait parler de PGCD sur n'importe quel anneau commutatif unitaire ; 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 les anneaux factoriels. Un anneau pour lequel cette propriété d'existence est satisfaite est appelé anneau à PGCD.

Dénomination

L'élément dont nous parlons est le plus grand diviseur commun de a et b. On pourrait s'attendre à le voir appelé le plus grand diviseur commun, abrégé « PGDC » et non le plus grand commun diviseur. Mais le nom est assez ancien, et en ancien français ce terme est accentué sur "commun", qui désigne le nombre et "diviseur" est ici employé comme adjectif. C'est pourquoi^{[réf. souhaitée]} on retrouve plus souvent l'appellation PGCD.

Notations

Le PGCD de deux entiers a et b est souvent noté : PGCD(a,b) ou pgcd(a,b). De même, le PGCD d'une famille d'entiers a_i sera noté pgcd(a_i) ou PGCD(a_i).

Certains auteurs notent le PGCD de deux entiers a et b sous la forme a∧b. Cette notation fait référence aux ensembles ordonnés : tout diviseur commun à a et b divise leur PGCD (voir ci-dessous).

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

Définitions

Pour des entiers

PGCD d'une famille d'entiers

Étant donnée une famille (finie ou infinie) d'entiers relatifs a_i non tous nuls, l'ensemble des diviseurs communs aux a_i est une partie finie et non vide de ℤ :

finie, car un diviseur d'un entier non nul a est borné par |a| ;

non vide car contient 1.

Cet ensemble admet donc un plus grand élément d, appelé le PGCD de la famille des a_i.

Exemples

On cherche le PGCD de 15 et 12.
Les diviseurs positifs de 15 sont : 1, 3, 5, 15.
Les diviseurs positifs de 12 sont : 1, 2, 3, 4, 6, 12.
Les seuls diviseurs communs à 15 et 12 sont donc 1 et 3. On en déduit PGCD(12, 15) = 3.
Les diviseurs communs à 36, 48 et 60 sont 1, 3, 4 et 12 donc PGCD(36, 48, 60) = 12.

Tout diviseur commun divise le PGCD

Rappelons qu'un entier n s'écrit de manière unique à l'ordre près des facteurs et au signe près 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 m divise un entier n si et seulement si pour tout p, v_p(m) ≤ v_p(n).

De fait, le pgcd d'une famille (a_i) 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 termes du produit, hormis une quantité finie, sont égaux à 1).

Tout diviseur commun à une famille d'entiers non tous nuls divise leur pgcd. Ce constat résulte immédiatement de l'écriture ci-dessus en produit de nombres premiers mais peut aussi se déduire de l'algorithme d'Euclide ou ses variantes :

Preuve par la méthode soustractive^[1]

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 « trivial » 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.

Quelques précisions sur « plus grand »

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 à la relation d'ordre habituelle mais au préordre de divisibilité, donc à la définition suivante (équivalente, dans un anneau commutatif unitaire, à la définition par les idéaux — voir plus bas) :

Un PGCD de a et b est un diviseur d de a et de b tel que tout autre diviseur commun à a et b est aussi un diviseur de d.

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 le PGCD dans un anneau commutatif quelconque, ou pour le PGCD de nombres 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 de PGCD(0, 0), que nous examinerons plus loin.

Rappelons que le D de PGCD signifie toujours diviseur et non dénominateur. Lors de la réduction de fractions au même dénominateur, on peut être amené à chercher le plus petit commun dénominateur qui est en fait le PPCM des dénominateurs. L'emploi de cette expression n'est pas une erreur, c'est un cas particulier d'emploi du PPCM. L'expression « Plus grand commun dénominateur » est en revanche erronée.

Cas du zéro

La définition générale ci-dessus du PGCD, avec « plus grand » au sens de la divisibilité, coïncide pour des entiers non tous nuls avec la définition naïve — en particulier, pour tout entier n > 0, PGCD(0, n) = n — et l'étend à des entiers tous nuls : leur PGCD est nul (alors que pour la relation d'ordre usuelle, il n'y a pas de plus grand diviseur de 0).

PGCD(0, 0) = 0 est d'ailleurs la réponse donnée par les calculatrices.

Il s'agit du seul PGCD de deux entiers pour lequel il n'y a pas à choisir entre un PGCD positif et un négatif.

Calcul du pgcd de deux entiers a et b

Il existe plusieurs méthodes, chacune plus ou moins adaptée à certaines situations. La plupart des méthodes comportent plusieurs étapes qui consistent à passer du calcul d'un pgcd à celui d'un autre pgcd avec des nombres « plus simples ». En général, on s'arrête lorsque l'un des nombres est premier ou lorsque l'un des nombres est multiple de l'autre, car dans ces cas le calcul du pgcd est très simple.

Méthode « devinette »

Cette méthode est particulièrement adaptée pour les petits nombres ou les nombres qui ont beaucoup de diviseurs faciles à trouver (2, 3, 5, 11). Elle consiste à simplifier le calcul en utilisant des diviseurs communs à a et b que l'on voit. En effet, si a et b ont de façon visible un facteur commun k, c'est-à-dire que l'on peut écrire 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 que 60 et 84 sont multiples de 4 donc

$\mathrm{pgcd}\left( 60,84\right) =4\times \mathrm{pgcd}\left( 15,21\right) .$

Ensuite, comme 15 et 21 sont multiples de 3 on a

$\mathrm{pgcd}\left( 15,21\right) =3\times \mathrm{pgcd}\left( 5,7\right) .$

Or, $\mathrm{pgcd}\left( 5,7\right)=1.$ Donc, $\mathrm{pgcd}\left( 60,84\right) =4\times 3=12.$

Méthode soustractive

Article détaillé : Anthyphérèse.

Cette méthode est particulièrement adaptée pour les nombres grands mais relativement proches. Supposons que a soit plus grand que b, on a

\mathrm{pgcd}\left( a,b\right) =\mathrm{pgcd}\left( a-b,b\right).

En effet, pour tout diviseur d de b :

si a est multiple de d alors a – b également ;
réciproquement, si d divise a – b, il divise également (a – b) + b = a.

Exemple : pgcd(675, 660) = pgcd(660, 15) = 15 car 660 est multiple de 15.

Algorithme d'Euclide

Article détaillé : Algorithme d'Euclide.

Cette méthode marche dans tous les cas et est donc particulièrement adaptée lorsque l'on n'est pas dans un cas où l'une des méthodes précédentes est rapide. C'est un raffinement de la méthode soustractive.

Avec la décomposition en facteurs premiers

Cette méthode n'est utilisable que si l'on a déjà factorisé a et b en produit 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

$\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) }$

$\text{Exemple : } 1248=2^{5}\times 3\times 13 \text{ et } 264= 2^{3}\times 3\times 11 \text{ donc } \mathrm{pgcd}\left( 1248,264\right) =2^{3}\times 3=24.$

Remarque : Si cette méthode semble attrayante car familière, il faut bien avoir en tête que la factorisation de a et b est en général beaucoup plus longue et difficile que le calcul de leur pgcd.

Propriétés

Soient $a$ , $b$ , $c$ trois entiers non nuls.

$\operatorname{pgcd}(a,b) = \operatorname{pgcd}(b, a-cb)$ ^[2]
$\operatorname{pgcd}(ac,bc) = |c|\operatorname{pgcd}(a,b)$ ^[3]
$\operatorname{pgcd}(a,b)=\min\left(\left\{au+bv\mid(u,v)\in\Z^2\right\}\cap\N^*\right)$
$pgcd(a, b) \times 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))$
$\operatorname{pgcd}(a,b,c) = \operatorname{pgcd}(\operatorname{pgcd}(a,b),c) = \operatorname{pgcd}(a,\operatorname{pgcd}(b,c))$ , on peut étendre à un nombre arbitraire d'éléments
Géométriquement, pgcd(a,b) est le nombre de points de coordonnées entières sur le segment d'extrémités les points (0,0) et (a,b), sans compter (0,0).

Généralisations

PGCD de fractions

Dans ce paragraphe, on utilise la définition générale donnée plus haut : d est un pgcd de a et b si d divise a et b et d est divisible par tout élément divisant a et b.

Premier point de vue : c'est le plus évident : on se place dans le corps ℚ des rationnels. Alors pour p1/q1 et q2/p2 deux rationnels non tous deux nuls, tout rationnel non nul est un PGCD de p1/q1 et q2/p2 (ℚ é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 si A est un anneau unitaire dont les seuls idéaux sont {0} et A. On comprend facilement, avec la définition du paragraphe 2.1, que deux éléments non tous deux nuls de A admettent n'importe quel élément non nul de 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 fraction p/q en divise une autre p'/q' non pas s'il existe une fraction a/b telle que (p/q)×(a/b) = p'/q' (toujours vrai si p ne vaut pas 0 : prendre a = q×p' et b = p×q') mais seulement s'il existe un entier c tel que (p/q)×c = p'/q'.

De façon analogue au paragraphe sur les idéaux, un pgcd de p1/q1 et q2/p2 est une fraction p/q telle que (p1/q1)×ℤ + (p2/q2)×ℤ = (p/q)×ℤ. Mais attention, les objets manipulés ici ne sont pas des idéaux, ni des pseudo sous-anneaux de ℚ, seulement des sous-groupes.

Finalement, on trouve p = ±pgcd(p1,p2) et q = ppcm(q1,q2).

De même, on a ppcm(p1/q1,p2/q2) = ±ppcm(p1,p2)/pgcd(q1,q2).

Le PGCD obtenu suivant le deuxième point de vue est également un PGCD possible quand on se place sur le corps Q. Les calculatrices et les logiciels de calcul choisissent l'un ou l'autre suivant le choix des programmeurs (par exemple Maple adopte le premier point de vue, la Casio Graph 100+ et la TI-92 le 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 fractions 1/n, n allant de 1 à l'infini parmi les entiers, n'admet pas de PGCD.

Cas des réels

On peut encore étendre les définitions précédentes avec des nombres 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 quelconques a et b, s'il existe un réel c tel que a = u×c et b = v×c avec u et v rationnels, on choisit PGCD(a,b) = |c|×PGCD(u,v), suivant la définition des PGCD de rationnels vue ci-dessus (2^e point de vue).

Pour deux réels a et b tels que a/b soit irrationnel (si b = 0, on est dans la situation précédente) on est obligé de revenir au premier point de vue d'où PGCD(Pi,√2) = 1 ; à noter que le PPCM présente le même problème, mais il est déterminé par PGCD(a,b)×PPCM(a,b) = |a×b|. (PPCM(Pi,√2) = Pi×√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 ; la Ti-92 n'a pas de réponse.

Polynômes à coefficients réels

Le PGCD dans l'anneau ℝ[X] vérifie la définition donnée plus haut. Mais cette fois, pour deux polynômes A et B non nuls, il y a une infinité de PGCD possibles : en effet tout PGCD de A et B multiplié par un réel non nul est aussi un PGCD de A et B. Pour définir un PGCD unique il y a deux conventions possibles : ou bien on pose par convention que le PGCD doit être un polynô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 formel Maple choisit 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'Euclide servant à trouver le PGCD de deux nombres entiers (voir ici comment on peut effectuer la division de deux polynômes).

Dans les anneaux commutatifs

La définition générale du PGCD dans un anneau (unitaire — ou même un pseudo-anneau) commutatif A est celle donnée plus haut, et s'étend à une famille quelconque (éventuellement infinie) : le plus grand commun diviseur d'une famille a_i est le plus grand diviseur commun aux a_i au sens de la divisibilité.

L'existence du PGCD de deux éléments (tout comme du PPCM) est certaine dans un anneau factoriel, pas toujours dans d'autres anneaux.

Par exemple, dans l'anneau ℤ[i√3], 4 et 2 + 2i√3 admettent 2 et 1 + i√3 comme diviseurs, mais aucun élément divisible simultanément par 2 et 1 + i√3 ne les divise.

Le PGCD de a et b n'est pas toujours unique, mais deux quelconques PGCD de a et b sont, par définition, toujours associés, c'est-à-dire que chacun est divisible par l'autre.

Dans un anneau principal, il existe des éléments u et v (non uniques) tels que PGCD(a, b) = au + bv (théorème de Bachet-Bézout).

Dans un anneau euclidien, une forme de l'algorithme d'Euclide peut ê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.

Définition par les idéaux

La définition de ce paragraphe est une reformulation de la précédente.

Dans l'anneau commutatif unitaire A, on note (x) l'idéal principal engendré par l'élément x, i.e. l'ensemble des multiples de x par un élément de A. Alors :

d est un PGCD de a et b si et seulement si (d) est le plus petit idéal principal contenant a et b, autrement dit : contenant l'idéal (a) + (b).

Dans un anneau principal, cela équivaut à (a) + (b) = (d).

Cette reformulation ne vaut pas dans un pseudo-anneau car l'ensemble des multiples de x peut alors être strictement inclus dans l'idéal engendré par x. Par exemple dans le pseudo-anneau 2ℤ, 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.

Anneaux non commutatifs

Dans un anneau non commutatif, un élément peut admettre des « diviseurs à droite » et des « diviseurs à gauche ». On peut dans certain 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.

Notes

↑ Inspirée de Daniel Perrin, « Une précision sur le pgcd ».
↑ Car l'ensemble des diviseurs communs est le même pour les deux couples. Cette propriété fonde l'algorithme d'Euclide.
↑ Pour une démonstration, voir par exemple Propriétés du PGCD sur Wikiversité.

Voir aussi

Liens externes

Outil en ligne calculant le PGCD de deux nombres
Paragraphe 3.3 : utilisation des PGCD dans un anneau non commutatif

Portail des mathématiques

This article is issued from Wikipédia - version of the Saturday, October 03, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.