PGCD

Imaginez 252 jetons rouges et 105 jetons jaunes à répartir en lots tous identiques, sans reste. Le plus grand nombre de lots possible est 21 : chacun contient 12 jetons rouges et 5 jaunes. Ce nombre 21 est le PGCD de 252 et 105.

Le PGCD indique donc le nombre maximal de lots identiques que l'on peut former sans reste. S'il vaut 1, il est impossible de former plus d'un lot commun : les nombres sont premiers entre eux, même si chacun peut être composé.

Pour une famille finie d'entiers qui ne sont pas tous nuls, le plus grand commun diviseur est l'unique entier positif qui remplit deux conditions : il divise chaque entier de la famille, et tout autre diviseur commun le divise. On note le PGCD de deux entiers $aa$ et $bb$ par $\mathrm{PGCD}(a,b)\backslash operatorname\{PGCD\}(a,b)$. Les signes ne changent pas sa valeur. Lorsque ce PGCD vaut 1, les deux entiers sont dits premiers entre eux, ou copremiers.

Pour les polynômes à coefficients réels, le mot « plus grand » renvoie à la divisibilité, pas à l'ordre des valeurs. Lorsque le PGCD est non nul, deux représentants peuvent différer par un facteur réel non nul ; choisir le représentant unitaire, dont le coefficient dominant vaut 1, rend le résultat unique. Pour la paire de polynômes nuls, on adopte séparément la convention PGCD(0, 0) = 0. Dans un anneau commutatif intègre quelconque, la même caractérisation par divisibilité a un sens, mais un PGCD n'existe pas forcément pour toute paire. Lorsqu'il existe, il est déterminé à multiplication par une unité près.

On cherche le plus grand nombre de lots identiques que permettent 252 jetons rouges et 105 jetons jaunes. Les données sont les deux entiers positifs 252 et 105. L'algorithme d'Euclide remplace à chaque étape le plus grand nombre par le reste de sa division par le plus petit.

1. Divisez 252 par 105. Le quotient est 2 et le reste est 42.

2. Divisez ensuite 105 par le reste 42. Le quotient est 2 et le nouveau reste est 21.

3. Divisez enfin 42 par 21. Le reste nul arrête l'algorithme.

Le dernier reste non nul est 21 : le PGCD de 252 et 105 vaut donc 21. On peut former 21 lots, chacun contenant 12 jetons rouges et 5 jetons jaunes.

Le contrôle est direct : 21 × 12 = 252 et 21 × 5 = 105. De plus, 12 et 5 sont premiers entre eux ; aucun nombre supérieur à 21 ne peut donc diviser simultanément 252 et 105.

Pour simplifier la fraction 252/105, on divise le numérateur et le dénominateur par leur PGCD, 21. On obtient 12/5, une fraction irréductible. La décomposition en facteurs premiers est une alternative pratique lorsque les nombres sont petits et se factorisent vite.

Pour constituer le plus grand nombre de lots identiques avec 252 objets d'un type et 105 d'un autre, le PGCD donne 21 lots de 12 et 5 objets. Si la taille des lots est imposée, un simple test de divisibilité suffit à la place.

Pour vérifier que deux entiers sont premiers entre eux, on calcule leur PGCD et l'on regarde s'il vaut 1. L'algorithme d'Euclide est préférable à la liste des diviseurs lorsque les nombres sont grands, car il travaille seulement avec des divisions successives.

PGCD et PPCM. Le PGCD divise les nombres, tandis que le plus petit commun multiple est divisible par chacun d'eux. Pour 12 et 18, le PGCD vaut 6, alors que le PPCM vaut 36.

PGCD et diviseur commun. Un diviseur commun n'est pas nécessairement le plus grand. Pour 252 et 105, 3, 7 et 21 sont communs, mais seul 21 est leur PGCD.

Premiers entre eux et nombres premiers. Deux nombres sont premiers entre eux quand leur PGCD vaut 1 ; ils ne doivent pas être premiers individuellement. Ainsi, 8 et 15 sont composés, mais leur PGCD vaut 1.

Deux zéros. Tous les entiers positifs divisent 0, donc il n'existe pas de plus grand diviseur positif de 0 et 0. La convention usuelle pose néanmoins PGCD(0, 0) = 0 ; il faut annoncer cette convention lorsqu'elle intervient.

Zéro et signes. Pour un entier non nul $aa$, le PGCD de $aa$ et 0 est la valeur absolue de $aa$. Un résultat négatif signale que la normalisation positive a été oubliée.

Polynômes. Multiplier un diviseur commun polynomial par une constante réelle non nulle ne change pas son rôle. Lorsque le PGCD est non nul, on choisit son représentant unitaire pour obtenir une écriture unique. Pour la paire de polynômes nuls, la convention PGCD(0, 0) = 0 s'applique, mais le polynôme nul ne peut pas être normalisé en polynôme unitaire.

Anneau intègre général. L'absence de diviseur commun maximal au sens de la divisibilité peut empêcher l'existence d'un PGCD. Il faut donc vérifier les propriétés de l'anneau ; en cas d'existence, deux réponses associées par une unité représentent le même PGCD.

L'algorithme d'Euclide approfondit la suite de divisions qui calcule efficacement le PGCD sans dresser la liste des diviseurs.

Le Ppcm complète le PGCD pour étudier les multiples communs et comparer concrètement les deux opérations.

La fiche Premiers entre eux développe le cas charnière où le PGCD de deux entiers vaut exactement 1.

L'anneau commutatif présente le cadre algébrique dans lequel la divisibilité et les unités généralisent la notion.