Plus grand commun diviseur de nombres entiers

Plus grand entier naturel divisant simultanément deux nombres entiers
(Redirigé depuis PGCD de nombres entiers)

En mathématiques, le PGCD de nombres entiers différents de zéro est, parmi les diviseurs communs à ces entiers, le plus grand d'entre eux. PGCD signifie plus grand commun diviseur.

Par exemple, les diviseurs positifs de 30 sont, dans l'ordre : 1, 2, 3, 5, 6, 10, 15 et 30. Ceux de 18 sont 1, 2, 3, 6, 9 et 18. Les diviseurs communs de 30 et 18 étant 1, 2, 3 et 6, leur PGCD est 6. Ce qui se note : PGCD(30, 18) = 6.

Les diviseurs communs à plusieurs entiers sont les diviseurs de leur PGCD. Connaître le PGCD de deux nombres entiers non nuls a et b permet de simplifier la fraction a/b. Il est possible de le déterminer par divers raisonnements, dont l'algorithme d'Euclide.

NotationModifier

Le PGCD de deux nombres entiers a et b est généralement noté PGCD(a, b) ou pgcd(a, b). On trouve parfois l'acronyme équivalent PGDC, mais PGCD est la version officielle[1].

PGCD(a, b) est parfois noté ab. Cette notation fait référence aux ensembles ordonnés : tout diviseur commun à a et b divise leur PGCD.

Les anglophones le nomment greatest common divisor, noté gcd(a, b), ou highest common factor, noté hcf(a, b).

DéfinitionModifier

Plus grand au sens usuelModifier

Tout nombre entier n a pour diviseur 1 ; n = n×1. Pour deux nombres entiers a et b, l'ensemble D de tous leurs diviseurs communs, n'est donc pas vide, puisqu'il contient 1.

L'ensemble des diviseurs d'un nombre entier non nul est fini a : tous les diviseurs sont inférieurs à a. Le PGCD de deux nombres entiers a et b dont au moins l'un des deux est non nul peut donc être défini comme le plus grand nombre appartenant à l'ensemble D de tous les diviseurs communs de a et b.

En particulier, comme tout nombre entier est un diviseur de zéro (car 0 × c = 0 quel que soit c) :

  • pour tout entier a > 0, PGCD(a, 0) = PGCD(0, a) = a.

Cette définition ne s'étend pas à PGCD(0, 0), puisqu'il n'existe pas de plus grand diviseur de 0.

Plus grand au sens de la divisibilitéModifier

Mais il est aussi possible de prendre « plus grand » au sens de la divisibilité : (b est plus grand que a quand b est un multiple de a, soit a est un diviseur de b), ce qui conduit à la définition suivante :

  • PGCD(a,b) est un diviseur de a et un diviseur de b ;
  • si c est un diviseur de a et b alors c est un diviseur de PGCD(a,b) ;
  • PGCD(a,b) ≥ 0.

Un tel entier existe bien, et il en existe un seul vérifiant ces trois propriétés qui est le PGCD au sens de la définition précédente quand (a,b) ≠ (0,0). Avec cette définition PGCD(0,0)=0.

La troisième condition PGCD(a,b) ≥ 0 n'est bien sûr pas utile quand on travaille sur les entiers naturels, où la relation de divisibilité est une relation d'ordre. Elle est nécessaire pour l'unicité dans le cas des entiers relatifs : en général deux nombres vérifient les deux premières conditions, le PGCD usuel et son opposé. Par exemple, deux nombres D vérifient

  • D divise 30 et 18 ;
  • tout entier qui divise 30 et 18 divise aussi D ;

à savoir 6 et -6.

Cette définition est aussi la plus susceptible d'être étendue à d'autres anneaux, comme par exemple l'anneau des polynômes à coefficients réels.

PropriétésModifier

Le PGCD peut être défini pour des nombres entiers naturels ou relatifs. Mais tout diviseur d'un nombre entier est également diviseur de son opposé. Les calculs et démonstrations sur le PGCD s'effectuent donc en général sur des nombres entiers positifs, l'extension aux négatifs étant immédiate.

ExemplesModifier

En appliquant directement la définition on a :

  • PGCD(a,a) = a ;
  • plus généralement, si a est un diviseur de b, alors PGCD(a,b) = a ;
  • si p est premier, alors PGCD(p, a) = 1 ou PGCD(p, a) = p.

PGCD et PPCMModifier

Le PGCD de deux nombres entiers positifs a et b est lié avec leur PPCM (le plus petit de leurs multiples communs), par la relation

ab = PGCD(a, b)×PPCM(a, b).

Pour trois entiers relatifs non nuls a, b, c :

  • pgcd(a, b) × ppcm(a, b) = |ab|
  •  
  •  

PGCD et combinaisons linéairesModifier

  • Soient a, b deux entiers non nuls, il est possible de remplacer l'un de deux nombres a ou b par a + b, ou par a - b, sans changer le PGCD.
  ;
  • par conséquent, on peut ajouter ou retrancher à l'un des deux un multiple de l'autre. Plus formellement :

Théorème — Soient a, b, v trois entiers, alors PGCD(a, b) = PGCD(a + bv, b).

Cette propriété fonde l'algorithme d'Euclide, une méthode qui permet de déterminer le PGCD de deux nombres (voir plus bas).

  • Le PGCD est compatible avec la multiplication par un entier naturel : soit k est un entier naturel,
 [2]
par exemple PGCD(9, 12) = 3, en multipliant par 3 on obtient PGCD(27, 36) = 9.
  • une combinaison linéaire quelconque de a et b, c'est-à-dire un nombre de la forme au + bv, où u et v sont des entiers relatifs, est forcément un multiple de tout diviseur commun de a et b, en particulier de PGCD(a, b). On peut montrer que le PGCD(a, b) est lui-même une combinaison linéaire de a et b : c'est le théorème de Bachet-Bezout, que toute combinaison linéaire de a et b est un multiple de PGCD(a, b), et que ce dernier est la plus petite combinaison linéaire de a et bstrictement positive :
 

Tout diviseur commun divise le PGCDModifier

Clairement, tout diviseur du PGCD de deux nombres est aussi un diviseur commun de ces deux nombres. La réciproque est vraie y compris pour la première définition. Par exemple, si le PGCD de deux nombres entiers a et b est 6, les diviseurs communs à a et b seront ceux de 6, soit : 1, 2, 3, 6 et leurs opposés.

C'est une conséquence du théorème de Bachet-Bezout, un diviseur commun de a et b étant un diviseur d'une combinaison linéaire de ceux-ci. La propriété se démontre aussi directement par récurrence, en suivant l'algorithme d'Euclide

Les diviseurs communs de deux nombres entiers sont donc exactement les diviseurs de leur PGCD. Cette propriété permet de démontrer l'équivalence des deux définitions ci-dessus.

Par exemple, si le PGCD de deux nombres entiers a et b est 6, les diviseurs communs à a et b seront ceux de 6, soit : 1, 2, 3, 6 et leurs opposés.

PGCD de trois nombres entiers ou plusModifier

 . On peut étendre à un nombre arbitraire d'éléments.


Nombres premiers entre euxModifier

Des nombres entiers naturels sont dits premiers entre eux lorsqu'ils n'ont pas d'autre diviseur commun que 1, autrement dit, leur PGCD est égal à 1.

Si deux nombres entiers a et b ont pour PGCD le nombre d, alors les entiers a/d et b/d sont premiers entre eux[4].

PGCD et facteurs premiersModifier

D'après le théorème fondamental de l'arithmétique, tout entier n naturel non nul s'écrit de manière unique à l'ordre près des facteurs 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 vp(n). Un entier non nul m divise n si et seulement si pour tout p, vp(m) ≤ vp(n).

De fait, le pgcd d'une famille (ai) d'entiers naturels est donné par :

 

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

On en déduit à nouveau que tout diviseur commun à une famille d'entiers non tous nuls divise leur pgcd.

Suites de Lucas et divisibilité forteModifier

Toute suite de Lucas xn = Un(P, Q) associée à des paramètres P, Q premiers entre eux est à divisibilité forte, c.-à-d. :   C'est le cas, par exemple, de :

ApplicationsModifier

Simplification de fractionsModifier

Une fraction irréductible est une fraction dans laquelle le numérateur et le dénominateur sont les plus proches possibles de 1. Cela revient à dire que le numérateur et le dénominateur sont premiers entre eux. La fraction irréductible égale à une fraction a/b donnée est celle dont le numérateur est a/d et le dénominateur b/d, où d = PGCD(a, b).

Exemple :

En sachant que PGCD(30, 18) = 6, puis en remarquant que   et  , on déduit que  , cette dernière fraction étant irréductible.

Équations diophantiennesModifier

Certaines équations diophantiennes (c'est-à-dire des équations dont les paramètres et les solutions cherchées sont des nombres entiers) se résolvent par une division par un PGCD afin de se ramener à une équation équivalente mettant en jeu des nombres premiers entre eux.

Ainsi l'équation diophantienne ax + by = c d'inconnues x et y admet une infinité de solutions si et seulement si c est un multiple du PGCD de a et b. Lorsque c n'est pas un multiple du PGCD de a et b, elle n'admet aucune solution entière. Ces résultats sont une conséquence du théorème de Bachet-Bézout. La méthode classique de résolution d'une telle équation consiste à diviser l'équation par le PGCD de a et b, puis, en s'appuyant sur le théorème de Gauss, résoudre la nouvelle équation obtenue, de la forme a'x + b'y = c', où a' et b' sont premiers entre eux.

Une autre équation diophantienne classique est la recherche des triplets pythagoriciens. Un triplet pythagoricien est la donnée de trois nombres entiers x, y et z qui vérifient la relation de Pythagore : x2 + y2 = z2. Cela revient à chercher tous les triangles rectangles dont les longueurs des côtés sont des nombres entiers. L'étude de cette équation se ramène à la recherche des nombres x, y et z premiers entre eux : si x, y et z sont des solutions de l'équation et que d est leur PGCD, alors x/d, y/d et z/d sont aussi des solutions de l'équation.

Détermination du PGCDModifier

Le PGCD peut se calculer de façon efficace par l'algorithme d'Euclide et ses variantes. D'autres méthodes, plutôt à vocation pédagogique, peuvent être mises en pratique pour de petits nombres, comme celle utilisant la décomposition en facteurs premiers.

Décomposition en facteurs premiersModifier

La décomposition en facteurs premiers permet de calculer le PGCD (voir #PGCD et facteurs premiers) : pour tout nombre premier p,

 ,

  est la valuation p-adique.

La première étape de cette méthode consiste à décomposer a et b en produits de nombres premiers. Si   et   où tous les exposants vérifient   et   alors le PGCD est donné par :

 . Cependant le calcul de la décomposition en facteurs premiers est coûteux, cette méthode n'est pas utilisée en pratique (hors illustration à visée pédagogique).

Connaissant les décompositions en facteurs premiers de deux nombres entiers a et b, la décomposition en facteurs premiers de leur PGCD est constituée des mêmes facteurs que ceux de a et b, en prenant pour chaque facteur l'exposant minimal qui apparaît à la fois dans a et b : le plus petit exposant commun à a et b.

Exemple :

Avec les décompositions en facteurs premiers

360 = 2×2×2×3×3×5 = 23×32×5

et

48 = 2×2×2×2×3 = 24×3

On remarque que les facteurs premiers communs sont 2 et 3. Le nombre 2 apparaît avec les exposant 3 et 4, donc son plus petit exposant commun est 3. Pour 3, le plus petit exposant commun est 1 (puisque 3 = 31). Le PGCD de 360 et 48 est donc 23×3 = 24.

Une variante, pas fondamentalement plus efficace, est de calculer directement la décomposition en facteurs premiers du PGCD [réf. nécessaire] : en prenant les nombres entiers dans l'ordre, on teste pour chacun s'ils sont diviseurs communs à a et b. C'est-à-dire que l'on trouve un nombre k tel que a = ka′ et b = kb′, alors il suffit de calculer le PGCD de a′ et b′ car on a :  

Exemple : pgcd(60,84). On voit successivement que :  . Or,  , car 5 est premier, et ne divise pas 7. Donc,  .

Algorithme d'EuclideModifier

Par soustractions successivesModifier

 
Animation de l'algorithme d'Euclide par soustractions successives.

Le PGCD de deux nombres a et b est aussi celui de a et de b - a. Ceci justifie la méthode des soustractions successives employée par Euclide pour le calcul du PGCD, connue en histoire des mathématiques sous le nom d'anthyphérèse. Elle repose sur les équations suivantes :

Algorithme d'Euclide par soustraction
pgcd(a,b) = pgcd(a, b - a) pour ba > 0
pgcd(a,b) = pgcd(b, a) pour a > b > 0 ou a = 0
pgcd(a, 0) = a

Exemple : pgcd(75, 60) = pgcd(60,75) = pgcd(60, 15) = pgcd(15,60)= pgcd(15,45) = pgcd(15, 30) = pgd(15, 15) = pgcd(15, 0) = 15.

Par divisions euclidiennesModifier

Dans l'algorithme d'Euclide par soustraction, pour le calcul de pgcd(a, b), ab, a est soustrait successivement de b jusqu'à obtenir r < b. C'est le reste de la division euclidienne de a par b. Ce reste peut se calculer plus efficacement que par soustractions successives, en particulier si a est très supérieur à b.

L'algorithme d'Euclide est souvent donné en utilisant directement la division euclidienne, plus précisément le reste. Le reste de la division de a par b, avec b > 0, noté ici reste(a, b), qui est l'unique entier naturel vérifiant :

  1. a = bq + reste(a, b) pour un certain q (le quotient) ;
  2. 0 ≤ reste(a, b) < b.

L'algorithme d'Euclide par division euclidienne s'appuie sur la même propriété que celui par soustraction, dont on déduit que a et b ont même PGCD que b et reste(a, b), plus précisément il s'appuie sur les équations suivantes :

Algorithme d'Euclide
pgcd(a, b) = pgcd( b, reste(a, b) ) pour b ≠ 0
pgcd(a, 0) = a

Comme, par définition de la division euclidienne, reste(a, b) < b, le second terme décroît strictement tant qu'il est strictement positif, d'où la terminaison de l'algorithme avec une valeur nulle pour ce second terme.

En reprenant le même exemple que pour l'algorithme par soustraction on obtient :

Exemple : pgcd(75, 60) = pgcd(60, 15) = pgcd(15, 0) = 15.

Algorithme du PGCD binaireModifier

L'algorithme du PGCD binaire est une variante de l'algorithme d'Euclide qui est utile quand les nombres sont codés en binaire.

Notes et référencesModifier

  1. « Programmes du collège : Programmes de l’enseignement de mathématiques », sur education.gouv.fr, Ministère de l'Éducation nationale, (consulté le ) : « Connaître et utiliser un algorithme donnant le PGCD de deux entiers (algorithme des soustractions, algorithme d’Euclide) », p. 35.
  2. Pour une démonstration, voir par exemple « Propriétés du PGCD » sur Wikiversité.
  3. Inspirée de Daniel Perrin, « Une précision sur le pgcd ».
  4. Pour une démonstration, voir par exemple « Nombres premiers entre eux » sur Wikiversité.

BibliographieModifier

  • André Deledicq, Mathématiques Lycée : tout le programme de la seconde à la terminale, Éditions de la Cité,
  • Michel Demazure, Cours d'algèbre, Cassini, (ISBN 978-2-84225-127-7)
  • W. Gellert, H. Küstner, M. Hellwich et H. Kästner (trad. de l'allemand par un collectif, sous la direction de Jacques-Louis Lions), Petite encyclopédie des mathématiques [« Kleine Enzyklopädie der Mathematik »], Didier,