Plus grand commun diviseur - Définition

Introduction

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

Par exemple le PGCD de 42 et 56 est 14. En effet, , et 3 et 4 sont premiers entre eux (il n'y a aucun naturel à part 1 qui soit à la fois diviseur de 3 et de 4).

Pour une explication plus détaillée suivant ce sens, voir :

On peut étendre cette notion, tout d'abord aux entiers relatifs, 0 compris, mais aussi aux nombres rationnels, voire aux réels. On pose même des définitions s'appliquant pour n'importe quel anneau, en distinguant les propriétés valables pour tous les anneaux et celles valables pour des anneaux de types particuliers.

De plus, on peut également considérer le PGCD d'un nombre arbitraire d'éléments, et dans certains cas d'une infinité.

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 il était plus normal de dire "commun diviseur" que "diviseur commun" et l'on retrouve plus souvent l'appellation PGCD.

Définitions

Pour des entiers

Étant donnée une séquence finie ou infinie a_i d'entiers qui ne sont pas tous nuls, l'ensemble des diviseurs communs des termes de la séquence est une partie finie et non vide de N

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

Non vide car contient 1, entier qui divise tous les entiers.

Cet ensemble admet donc un élément maximal d, appelé le pgcd de la séquence a_i considérée.

Par exemple, les diviseurs communs de 36, 48 et 60 sont 1, 3, 4 et 12. Le pgcd de 36, 48 et 60 est donc 12.

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 .

De fait, le pgcd d'une séquence a_i est donnée par :

où le produit portent sur l'ensemble des nombres premiers (presque tous les termes du produit, hormis une quantité finie, sont égaux à 1).

Tout diviseur commun à une séquence d'entiers relatifs, non tous nuls, divise leur pgcd. Ce constat résulte immédiatement de l'écriture ci-dessus en produit de nombres premiers. Le pgcd apparait de fait comme l'élément maximal de l'ensemble des diviseurs communs, maximal au sens de la division (avec son opposé : certains préfèrent même préciser "le PGCD positif", cependant quand on parle des entiers, si on demande le PGCD, il est évident qu'on parle du PGCD positif).

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 fait que tout diviseur commun de a et de b divise PGCD(a,b). Le ou les PGCD de a et de b sont donc les plus grands éléments de l'ensemble des diviseurs de a et de b au sens de la relation de divisibilité, et donc -3 et 3 sont tous deux des PGCD de 6 et de 9. Cette façon de voir les choses est utile pour définir le PGCD, pour des polynômes par exemple, ou pour le PGCD de nombres rationnels. Dans le cas des polynômes, le PGCD est le diviseur de plus haut degré. 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 normal 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 « supérieur ou inférieur », mais ce n'est vrai que pour le cas des nombres (le PGCD s'étend à d'autres objets mathématiques). Et encore, le cas de PGCD(0,0), que nous examinerons plus loin, contredit cette assertion.

Rappelons 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. 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, sauf si l'on considère "dénominateur" comme synonyme de "diviseur" (ce qu'on fait parfois à cause de sa position en bas d'une fraction, le nombre rationnel n/m étant égal à n divisé par m, et m est le dénominateur).