Plus grand commun diviseur

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

En mathématiques, le plus grand commun diviseur (abrégé PGCD) de deux entiers, non tous deux nuls, est le plus grand nombre entier naturel qui divise les deux nombres. (certaines définitions permettent d'étendre au cas de deux entiers simultanément nuls)

Le PGCD de a et b est souvent noté : PGCD(a,b), pgcd(a,b) ou a∧b (il y a alors confusion avec le et logique, c'est pourquoi cette notation ne sera pas utilisée ici).

Deux nombres entiers sont dits « premiers entre eux » si leur plus grand commun diviseur égale 1.

On peut étendre le PGCD à un nombre d'entiers $n$ supérieur à deux : le PGCD est le plus grand entier naturel divisant simultanément les $n$ nombres. Il est même possible de définir le PGCD d'un ensemble infini d'entiers.

Sommaire

1 Définition
2 Dénomination
3 PGCD dans les anneaux commutatifs
- 3.1 Définition par les idéaux
- 3.2 Anneaux non-commutatifs
4 Cas du zéro
5 Généralisations immédiates
6 Exemple
7 Calcul du PGCD
8 Propriétés
9 Voir aussi
10 Liens Externes

[modifier] Définition

Soit $(a,b)\in{\mathbb{Z}^*\times\mathbb{Z}}$ .

On note $d_{a,b}=\left\{ d\in\mathbb{N}^* / d|a \land d|b \right\}$

On vérifie alors :

$d_{a,b} \subset \mathbb{N}$
$d_{a,b} \ne \empty$ (car $1 \in d_{a,b}$ )
$\forall n\in d_{a,b}, n \le a$

En effet, soit n dans

d a, b

. On a donc n|a. On en déduit qu'il existe un k dans $\mathbb{N}^*$ tel que n.k=a. Comme $k \ge 1$ , $n \le a$ .

Par axiome, $max(d a, b)$ existe.

On définit $\operatorname{pgcd}(a,b)=\max(d_{a,b})$ .

[modifier] 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". On peut parfois trouver cette forme. Mais le nom est assez ancien, et en ancien français il était plus normal de dire "commun diviseur" que "diviseur commun".

Nous allons voir plus loin une définition du PGCD permettant de dire que -3 et 3 sont tous deux des PGCD de 6 et 9. Cela peut paraître incongru, puisque 3 est supérieur à -3. Mais le "plus grand" de PGCD ne correspond pas à la relation d'ordre habituelle mais au fait que tout diviseur commun de a et b divise pgcd(a,b). Le ou les pgcd de a et b sont donc les plus grands éléments de l'ensemble des diviseurs de a et b au sens de la relation de divisibilité.

Evidemment, celui des deux pgcd qui est positif est également le plus grand diviseur au sens de la relation d'ordre "supérieur ou inférieur", mais ce n'est vrai que pour le cas des nombres. Et encore, le cas de pgcd(0,0), que nous verrons plus loin, contredit cette assertion.

Certains préfèrent préciser "le pgcd positif" quand ils parlent du pgcd de nombres entiers.

Rapellons que le D de PGCD signifie toujours diviseur et non dénominateur. Le plus petit commun dénominateur est en fait le PPCM employé pour la réduction de fractions (ce n'est pas une erreur). L'expression "Plus grand commun dénominateur" est en fait erronée.

Quant au terme "plus grand", il ne se rapporte pas à la relation d'ordre habituelle (supérieur ou inférieur) mais à la relation de divisibilité. Dans le cas des entiers, avec la convention "le PGCD est positif", les deux sens coïncident. Dans le cas des polynômes, le PGCD est le diviseur de plus haut degré.

Tous ces termes sont depuis peu utilisés à titre de métaphores en politique, souvent avec des erreurs: ainsi on entend régulièrement parler de plus petit commun diviseur ou de plus grand commun multiple (dénominateur étant utilisé indifférement). Ces notions ne sont pas employées en mathématiques puisque le PPCD vaudrait trivialement 1 pour tout ensemble de nombres, et le PGCM 0 (et non l'infini, puisque la relation utilisée est la divisibilité).

[modifier] PGCD dans les anneaux commutatifs

Le plus grand commun diviseur peut être défini plus généralement pour les éléments d'un anneau commutatif arbitraire, pas forcément unitaire (certaines terminologies diraient : pseudo-anneau).

Si A est un anneau commutatif, et a et b sont dans A, alors un élément c de A est appelé un diviseur commun de a et b s'il divise à la fois a et b (c'est-à-dire s'il existe des éléments x et y de A tels que cx = a et cy = b). Si c est un diviseur commun de a et b, et chaque diviseur commun de a et b divise c, alors c est appelé un plus grand commun diviseur de a et b.

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

Par exemple, dans l'anneau , 4 et  admettent 2 et 
comme diviseurs, mais aucun élément divisible simultanément par 2 et  ne les divise.

Notons que le PGCD de a et b n'est pas toujours unique, mais si A est intègre alors deux quelconques PGCD de a et b sont des éléments associés.

Dans le pseudo-anneau  $2 * Z / 20 Z$ , [8] et [12] admettent comme pgcd possibles [4], [8], [12], [16] ([2]*[4]=[8],
[4]*[8]=[32]=[12], [8]*[12]=[96]=[16],  [4]*[16]=[64]=[4]), qui ne sont pas associés.

Dans un anneau principal, il existe $c$ et $d$ éléments de $A$ (non uniques) tels que $a c + b d = p g c d (a, b)$ (identité de Bezout)

Si A est un anneau euclidien alors 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. Par exemple dans l'anneau des polynômes à coefficients complexes, le PGCD est unique si on exige qu'il soit un polynôme unitaire.

D'ailleurs dans le cas des nombres entiers, l'unicité du PGCD est obtenue avec la convention "le PGCD est un nombre positif". Sans cette convention, la définition ci-dessus donne deux PGCD distincts, opposés.

Tout ce qui précède se généralise à un nombre arbitraire ou même infini d'éléments, sauf l'algorithme d'Euclide.

[modifier] Définition par les idéaux

La définition de ce paragraphe est un peu plus générale que celle du paragraphe précédent, et permet de définir des PGCD dans des cas où ils ne pourraient l'être suivant la définition précédente.

Dans l'anneau commutatif A, on note (x) l'idéal principal engendré par l'élément x, ie l'intersection de tous les idéaux de A contenant x, (l'ensemble des éléments xy, y décrivant A si A est unitaire).

Pour a et b éléments de A, (a)+(b) est également un idéal.

Alors d est un pgcd de a et b ssi (d) est le plus petit idéal engendré par un seul élément incluant (a)+(b), ie (a)+(b) ⊂(d) et pour tout x ⊂ A, (a)+(b) ⊂ (x) (ce qui équivaut à x est un diviseur de a et b si A est unitaire) ⇒ (d) ⊂ (x) (ce qui équivaut à x est un diviseur de d si A est unitaire).

Dans le pseudo-anneau (anneau non unitaire) 2Z, 8 et 12 ont pour PGCD possibles 4 et -4… En effet, (8)+(12) ⊂ (4) = (-4) = 4Z,
et pourtant 4 n'est pas un diviseur de 12 dans 2Z!

Dans un anneau principal, ce qui précède équivaut à (a)+(b) = (d)

Comme plus haut, il n'y a ici non plus pas unicité du pgcd.

Ici encore, on peut étendre à un nombre arbitraire voire infini d'éléments.

[modifier] 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é.

[modifier] Cas du zéro

Certaines définitions du PGCD autorisent le calcul du PGCD d'un entier quelconque avec 0. Pour tout $n$ entier, $p g c d (0, n) = n$ .

Cette propriété reste vraie pour n=0.

Pour la justifier dans ce dernier cas, il faut adopter la propriété (a) + (b) = (pgcd(a,b)) (vraie dans un anneau principal, comme nous l'avons vu plus haut) comme définition du PCGD (à un choix parmi les éléments associés près).

Donc pgcd(0,0)=0 (c'est la réponse donnée par les calculatrice: elle ne peut se justifier par la définition du PGCD du premier paragraphe) Ce n'est pas une simple convention, mais la conséquence de la définition formelle du PGCD.

[modifier] Généralisations immédiates

[modifier] PGCD de fractions

Dans ce paragraphe, on utilise la définition suivante: 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. (paragraphe 2)

Premier point de vue: c'est le plus évident: on se place dans le corps $\mathbb Q$ 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 (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 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*\mathbb Z+p2/q2*\mathbb Z=p/q*\mathbb Z$ . Mais attention, les objets manipulés ici ne sont pas des idéaux, ni des pseudo sous-anneaux de Q, 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 bien entendu également un PGCD possible quand on se place sur le corps Q. Les calculatrices et 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+ le second).

Un inconvénient du second point de vue est que le PGCD d'une famille infinie de rationnels n'existe pas toujours.

[modifier] 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 (2e 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, $\sqrt[]{2}$ )=1; à noter que le PPCM le même problème, mais il est déterminé par PGCD(a,b)*PPCM(a,b)=|a*b|. (PPCM(Pi, $\sqrt[]{2}$ )=Pi* $\sqrt[]{2}$ )

Ici encore, on ne tranche pas entre les deux points de vue mais il s'agit d'expliquer pourquoi PGCD(Pi/3,Pi/2) vaut Pi/6 selon certaines calculatrices, 1 selon d'autres.

[modifier] Polynômes à coefficients réels

Le PGCD dans l'anneau $\mathbb R[X]$ vérifie la définition donnée plus haut. Mais cette fois il y a une infinité de PGCD possibles pour 2 polynômes: tout PGCD des polynômes 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, 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.

[modifier] Exemple

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.

On obtient donc $d 12,15 = {1,3}$

On en déduit pgcd(12, 15) = 3.

Dans la pratique, on utilise l'algorithme d'Euclide

[modifier] Calcul du PGCD

On pourrait calculer le PGCD de deux nombres en écrivant leur décomposition en produit de facteurs premiers et en considérant le produit de certains facteurs premiers communs, mais dans la pratique on utilise rarement cette méthode du fait de sa lenteur, excepté dans les cas évidents (par exemple pour 4 et 6, on trouve immédiatement 4=2*2 et 6=2*3, d'où PGCD(4,6)=2).

Une méthode beaucoup plus efficace est l'algorithme d'Euclide.

[modifier] Propriétés

Soit $(a,b,c)\in{\mathbb{Z}^*}^3$

$\operatorname{pgcd}(a,b)|a \land \operatorname{pgcd}(a,b)|b$
$c|a \land c|b \Leftrightarrow c|\operatorname{pgcd}(a,b)$
$\operatorname{pgcd}(ac,bc) = |c|\operatorname{pgcd}(a,b)$
$\operatorname{pgcd}(a,b)=\min\left\{|au+bv| / (u,v)\in\mathbb{Z}^2 \right\}$
$\operatorname{pgcd}(a,b) = \operatorname{pgcd}(a+cb,b)$
$\operatorname{pgcd}(a,b) \operatorname{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).