Pour des entiers a et b (pas tous les deux nuls), le plus grand commun diviseur gcd(a,b) est le plus grand entier positif qui divise à la fois a et b sans reste.

Principe

Parmi les diviseurs communs de deux entiers, choisir l'élément maximal selon l'ordre usuel des entiers positifs ; le pgcd est unique et se caractérise par l'identité de Bézout comme la plus petite combinaison linéaire positive des entiers.

Démonstration

pgcd(48,18)=6 car 6 divise à la fois 48 et 18 et aucun entier positif plus grand ne le fait ; de plus 6 = 48·(−1) + 18·3 vérifie la relation de Bézout.

Mauvaise application

Confondre pgcd et ppcm, ou utiliser des algorithmes de pgcd de manière incorrecte en supposant qu'une factorisation en nombres premiers est nécessaire ; traiter pgcd(0,0) comme bien défini sans préciser la convention.

Conséquence

Une utilisation correcte du pgcd permet de simplifier des fractions, de calculer des solutions entières d'équations diophantiennes linéaires et de comprendre l'existence d'inverses modulaire (lorsque le pgcd vaut 1).

Inversion

La notion complémentaire est le plus petit multiple commun : alors que le pgcd concerne les facteurs communs maximaux, le ppcm se concentre sur les multiples communs minimaux.

Limite

Défini pour les entiers (y compris négatifs via la valeur absolue) et habituellement pour des paires ou des tuples finis ; pgcd(0,0) est conventionnellement indéfini ou posé égal à 0 selon le contexte et doit être traité explicitement. S'applique aux domaines principaux idéaux mais pas directement à anneaux arbitraires sans adaptation.

Tension sémantique

Tension avec le concept de 'premiers entre eux' : pgcd(a,b)=1 est une propriété plutôt qu'une grandeur ; cela relie aussi aux coefficients de Bézout qui ne sont pas uniques alors que le pgcd est unique à un signe près.

Synthèse

Le plus grand commun diviseur de a et b est le plus grand entier positif divisant les deux, unique et central pour la divisibilité, la réduction de fractions et la résolution des relations diophantiennes linéaires.