En mathématiques, le plus grand commun diviseur (en abrégé P.G.C.D.), de deux entiers non tous deux nuls, est le plus grand nombre entier naturel qui divise les deux nombres.

Le P.G.C.D. de a et b est souvent noté : PGCD(a,b), pgcd(a,b) ou a⋀b. Par exemple, pgcd (12,18) = 6, pgcd (-4,14) = 2 et pgcd (5,0) = 5. Le P.G.C.D. de 0 et 0 est par convention égal à 0.

Deux nombres entiers sont dits premiers entre eux si leur plus grand commun diviseur est égal 1. Par exemple, 9 et 28 sont premiers entre eux.

Le plus grand commun diviseur est utile pour réduire les fractions. En divisant le numérateur et le dénominateur d’une fraction a/b par le P.G.C.D. de a et b, on obtient une fraction irréductible a’/b’. Le P.G.C.D. de a’ et b’ vaut 1. Considérons par exemple

42/56 = 3/4

Table of contents

1 Calcul du P.G.C.D. 2 Propriétés 3 P.G.C.D. dans les anneaux commutatifs

Calcul du P.G.C.D.

On pourrait calculer le P.G.C.D. 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 n’utilise jamais cette méthode, parce qu'elle est trop lente.

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

L’algorithme d’Euclide étendu permet de calculer aussi des nombres entiers relatifs p et q tels que : ap + bq = pgcd(a, b).

Propriétés

Chaque diviseur commun de a et b divise le P.G.C.D. de a et b.

Le plus grand commun diviseur des entiers non tous deux nuls a et b peut être défini alternativement comme, le plus petit nombre entier strictement positif d qui peut s'écrire sous la forme ap+bq où p et q sont des nombres entiers.

Si d est le P.G.C.D. de a et b, et a divise le produit bc, alors a/d divise c.

Si m est un entier quelconque, alors pgcd (ma,mb) =m pgcd (a,b) et pgcd (a+mb,b) = pgcd (a,b). Si m est un diviseur commun différent de zéro de a et b, alors pgcd(a/m,b/m) = pgcd (a,b)/m.

Le P.G.C.D. de trois entiers peut être calculé par :

pgcd (a,b,c) =pgcd(pgcd(a,b),c) = pgcd (a, pgcd (b, c)).

pgcd(a, b) × ppcm (a, b) = ab.

pgcd(a, ppcm (b, c)) = ppcm(pgcd(a, b), pgcd (a, c))

ppcm(a, pgcd (b, c)) = pgcd(ppcm(a, b), ppcm (a, c)).

P.G.C.D. 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.

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.