Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Plus grand commun diviseur

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

Nous avons divisé le numérateur et le dénominateur par 14, le plus grand commun diviseur de 42 et 56.

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 également 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)).

Le P.G.C.D. de a et b est relié au plus petit commun multiple, ppcm (a, b) par la relation :

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

De plus, les propriétés suivantes de distributivité sont vérifiées:

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

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

Géométriquement, pgcd (a,b) est le nombre de points de coordonnées entières sur le segment d'extrémités les points (0,0) et (a,b), sans compter (0,0).

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.

Notons que le P.G.C.D. de a et b n'est pas unique, mais si A est intègre alors deux quelconques P.G.C.D. de a et b sont des éléments associés. Aussi, a et b ne peuvent avoir un P.G.C.D. à moins que A soit un anneau factoriel. Si A est un anneau euclidien alors une forme de l'algorithme d'Euclide peut être utilisée pour calculer le P.G.C.D..