Voir la source de Plus grand commun diviseur

{{à recycler|thème=mathématiques|date=décembre 2007}}{{Article détaillé|contenu=Pour une introduction, voir [[Plus grand commun diviseur de nombres entiers]].}}

En [[arithmétique élémentaire]], le '''plus grand commun diviseur''' ou [[Plus grand commun diviseur de nombres entiers|'''PGCD''' de deux nombres entiers]] non nuls est le plus grand entier qui les [[divisibilité|divise]] tous les deux. Par exemple, le PGCD de 20 et de 30 est 10, puisque leurs [[diviseur]]s communs sont 1, 2, 5 et 10.

Cette notion s'étend aux [[entiers relatifs]] grâce aux propriétés de la [[division euclidienne]]. Elle se généralise aussi aux [[anneau euclidien|anneaux euclidiens]] comme l'anneau des [[polynôme]]s sur un [[corps commutatif]].

La notion de PGCD peut être définie dans tout [[anneau 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 les [[anneau factoriel|anneaux factoriels]]. Un anneau pour lequel cette propriété d'existence est satisfaite est appelé [[anneau à PGCD]].

== Notation ==

Le PGCD de deux entiers <math>a</math> et <math>b</math> se note : <math>\operatorname{PGCD}(a,b)</math>.
Par extension, le PGCD d'une [[Famille (mathématiques)|famille]] d'entiers <math>a_i</math> est noté <math>\operatorname{PGCD}(a_i)</math>.

<math>\operatorname{PGCD}(a,b)</math> est parfois noté <math>a\wedge b</math>. Cette notation fait référence aux ensembles ordonnés : tout diviseur commun à <math>a</math> et <math>b</math> divise leur PGCD.

== PGCD d'une famille d'éléments ==
=== Définition pour une famille de nombres entiers ===
{{Article détaillé|Plus grand commun diviseur de nombres entiers}}
Étant donné une famille (finie ou infinie) d'[[Entier relatif|entiers relatifs]] <math>a_i</math> non tous nuls, l'ensemble des diviseurs communs aux <math>a_i</math> est une partie finie et non vide de <math>\mathbb{Z}</math> :
* finie, car un diviseur d'un entier non nul <math>a</math> est borné par <math>|a|</math> ;
* non vide car contient 1.
Cet ensemble admet donc un [[plus grand élément]] <math>d</math>, appelé le PGCD de la famille des <math>a_i</math>.

Par exemple, les diviseurs communs à 36, 48 et 60 sont 1, 2, 3, 4, 6 et 12 donc <math>\operatorname{PGCD}(36, 48, 60) = 12</math>.

=== Définition dans un anneau commutatif ===

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|définition par les idéaux]] — voir plus bas) :
{{énoncé|Un PGCD de <math>a</math> et <math>b</math> est un diviseur <math>d</math> de <math>a</math> et de <math>b</math> tel que tout autre diviseur commun à <math>a</math> et <math>b</math> est aussi un diviseur de <math>d</math>.}}
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 [[#Dans les anneaux commutatifs|PGCD dans un anneau commutatif]] quelconque, ou pour le PGCD de [[Nombre rationnel|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 <math>\operatorname{PGCD}(0, 0)</math>, que nous examinerons plus loin.

== PGCD de nombres rationnels ==
{{section à sourcer|date=septembre 2021}}

Dans ce paragraphe, on utilise la définition générale donnée [[#Définition dans un anneau commutatif|plus haut]] : <math>d</math> est un PGCD de <math>a</math> et <math>b</math> si <math>d</math> divise <math>a</math> et <math>b</math> et <math>d</math> est divisible par tout élément divisant <math>a</math> et <math>b</math>.

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

De façon analogue au paragraphe sur les idéaux, un PGCD de <math>p_1/q_1</math> et <math>p_2/q_2</math> est une fraction <math>p/q</math> telle que <math>(p_1/q_1)\times\mathbb{Z}+(p_2/q_2)\times\mathbb{Z}=(p/q)\times\mathbb{Z}</math>. Mais attention, les objets manipulés ici ne sont pas des idéaux, ni des pseudo sous-anneaux de <math>\mathbb{Q}</math>, seulement des sous-groupes.

Finalement, on trouve <math>p=\pm\operatorname{PGCD}(p_1,p_2)</math> et <math>q=\operatorname{PPCM}(q_1,q_2)</math>.

De même, on a <math>\operatorname{PPCM}(p_1/q_1, p_2/q_2)=\pm\frac{\operatorname{PPCM}(p_1,p_2)}{\operatorname{PGCD}(q_1,q_2)}</math>.

Le PGCD obtenu suivant le deuxième point de vue est également un PGCD possible quand on se place sur le corps <math>\mathbb{Q}</math>. 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 <math>\frac{1}{n}</math>, <math>n</math> allant de 1 à l'infini parmi les entiers, n'admet pas de PGCD.

== Cas des nombres réels ==
{{section à sourcer|date=septembre 2021}}

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

Pour deux réels <math>a</math> et <math>b</math> tels que <math>\frac{a}{b}</math> soit irrationnel (si <math>b = 0</math>, on est dans la situation précédente) on est obligé de revenir au premier point de vue d'où <math>\operatorname{PGCD}(\pi,\sqrt{2}) = 1</math> ; à noter que le PPCM présente le même problème, mais il est déterminé par <math>\operatorname{PGCD}(a,b) \times \operatorname{PPCM}(a,b) = |a \times b|</math>. (<math>\operatorname{PPCM}(\pi,\sqrt{2}) = \pi\times\sqrt{2}</math>.)

Chaque calculateur se plaçant dans la continuité de son comportement concernant les rationnels, {{référence nécessaire|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}}.

== PGCD de polynômes à coefficients entiers ou réels ==

Le PGCD dans l'anneau <math>\mathbb{R}[X]</math> vérifie la définition donnée plus haut. Mais cette fois, pour deux polynômes <math>f(x)</math> et <math>g(x)</math> non nuls, il y a une infinité de PGCD possibles : en effet, tout PGCD de <math>f(x)</math> et <math>g(x)</math> multiplié par un réel non nul est aussi un PGCD de <math>f(x)</math> et <math>g(x)</math>. 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 [[Poser une division#Division de polynômes|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 <math>A</math> est celle donnée [[#Définition dans un anneau commutatif|plus haut]], et s'étend à une famille quelconque (éventuellement infinie) : le plus grand commun diviseur d'une famille <math>a_i</math> est le plus grand diviseur commun aux <math>a_i</math> au sens de la divisibilité.

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

Par exemple, dans l'anneau <math>\mathbb{Z}\left[i\sqrt{3}\right]</math>, <math>4</math> et <math>2+2i\sqrt{3}</math> admettent <math>2</math> et <math>1+i\sqrt{3}</math> comme diviseurs, mais aucun élément divisible simultanément par <math>2</math> et <math>1+i\sqrt{3}</math> ne les divise.

Le PGCD de <math>a</math> et <math>b</math> n'est pas toujours unique, mais deux quelconques PGCD de <math>a</math> et <math>b</math> sont, par définition, toujours [[éléments associés dans un anneau|associés]], c'est-à-dire que chacun est divisible par l'autre.

Dans un [[anneau principal]], il existe des éléments <math>u</math> et <math>v</math> (non uniques) tels que <math>\operatorname{PGCD}(a,b)=au+bv</math> ([[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 <math>A</math>, on note <math>(x)</math> l'[[idéal principal]] engendré par l'élément <math>x</math>, i.e. l'ensemble des multiples de <math>x</math> par un élément de <math>A</math>. Alors :
{{énoncé|<math>d</math> est un PGCD de <math>a</math> et <math>b</math> si et seulement si <math>(d)</math> est le plus petit idéal principal contenant <math>a</math> et <math>b</math>, autrement dit : contenant l'idéal [[Somme d'idéaux|<math>(a)+(b)</math>]].}}
Dans un anneau principal, cela équivaut à <math>(a)+(b)=(d)</math>.

Cette reformulation ne vaut pas dans un [[pseudo-anneau]] car l'ensemble des multiples de <math>x</math> peut alors être strictement inclus dans l'idéal engendré par <math>x</math>. Par exemple dans le pseudo-anneau <math>2\mathbb{Z}</math>, 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 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.
<!--

== Notes et références ==
{{Références}}
-->

== Voir aussi ==
=== Articles connexes ===
* [[Plus grand commun diviseur de nombres entiers]]
* [[Plus petit commun multiple]]
* [[Treillis (ensemble ordonné)]]
* [[Algorithme d'Euclide]]
* [[Livre VII des Éléments d'Euclide]]
* [[Nombres premiers entre eux]]

=== Liens externes ===
* [http://www.ilemaths.net/calcul_outils_entiers_pgcd.php Outil en ligne calculant le PGCD de deux nombres]
* [http://cas.ensmp.fr/~chaplais/FTP/Cours_Systemes/Algebre_matricielle.pdf Paragraphe 3.3 : utilisation des PGCD dans un anneau non commutatif]

{{Palette|Opérations binaires}}
{{Portail|mathématiques}}

[[Catégorie:Divisibilité et factorisation]]
[[Catégorie:Opération]]