PGCD de nombres entiers

Cet article de vulgarisation évite les aspects trop pointus ou techniques. Pour consulter un article plus détaillé, voir : PGCD.

Le PGCD de nombres entiers différents de zéro est, parmi les diviseurs communs à ces entiers, le plus grand d'entre eux. 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. On voit que les diviseurs communs de 30 et 18 sont 1 ; 2 ; 3 et 6, donc leur PGCD est 6. L'abréviation PGCD signifie Plus Grand Commun Diviseur. Le PGCD de deux nombres entiers a et b est généralement noté PGCD(a ; b). Ainsi, 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.

Propriétés

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.

PGCD et autres diviseurs

A priori, il faut connaître la liste des diviseurs communs de deux nombres pour pouvoir déterminer le PGCD. Mais l'inverse est également vrai. En effet, les diviseurs communs de deux nombres entiers sont exactement les diviseurs de leur PGCD. 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.

La réciproque est en partie vraie : le seul nombre positif D qui vérifie les deux propriétés :

D divise a et b ;

tout entier qui divise a et b divise aussi D ;

est le PGCD de a et b.

Ces deux phrases sont parfois prises comme définition du PGCD, ce qui permet d'étendre à d'autres ensembles que celui des nombres entiers (voir l'article PGCD). Mais si on ôte l'adjectif positif, un autre nombre entier vérifie cette propriété : l'opposé du PGCD de a et b. Par exemple, deux nombres D vérifient

D divise 30 et 18 ;

tout entier qui divise 30 et 18 divise aussi D ;

sont 6 et -6.

Ceci montre que, si b est un diviseur de a, alors le PGCD de a et b est b.

PGCD et autres opérations

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

Le PGCD est en partie compatible avec la multiplication :

pour tous nombres entiers non nuls a, b et k, PGCD(ka;kb) = k PGCD(a;b).

Mais il ne l'est pas avec l'addition. Par exemple, PGCD(9;12) = 3 mais, en ajoutant 2, PGCD(11;13) = 1, alors qu'en multipliant par 3 on obtient PGCD(27;36) = 9.

Cependant, il est possible de remplacer l'un de deux nombres a ou b par a+b sans changer le PGCD. Plus généralement, 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é justifie l'algorithme d'Euclide, une méthode qui permet de déterminer le PGCD de deux nombres (voir plus bas).

Par contre, 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) n'est pas forcément égale à PGCD(a;b), mais en est un multiple. Et, réciproquement, un nombre entier c peut s'écrire sous la forme au+bv si et seulement si c est un multiple de PGCD(a;b).

Nombres premiers entre eux

Article détaillé : Nombres premiers entre eux.

Des nombres entiers sont dits premiers entre eux lorsqu'ils n'ont « rien en commun » du point de vue de la divisibilité, autrement dit, leur PGCD est égal à 1.

Une erreur classique consiste à croire que, si un nombre entier c divise un produit d'entier ab, alors il divise a ou b. Il n'en est rien, comme le montre l'exemple de 6, qui divise 9×8=72, mais ne divise ni 9 ni 8. Mais cela devient vrai si on ajoute l'hypothèse que c est premier avec l'un des deux nombres a ou b. Ce résultat est connu sous le nom de Théorème de Gauss et s'énonce ainsi :

Théorème de Gauss — Soient a, b et c trois nombres entiers tels que c divise ab et c est premier avec a. Alors c divise b.

Si deux nombres entiers a et b ont pour PGCD le nombre d, alors ^a⁄_d et ^b⁄_d sont des nombres entiers premiers entre eux.

Cas de zéro

En considérant que tout nombre entier est un diviseur de zéro (car 0 × b = 0 quel que soit b) il vient que, pour tout entier non nul b, PGCD(0;b)= PGCD(b;0)=b.

La notion de PGCD(0;0) contredit la notion du "plus grand diviseur commun" puisqu'il n'existe pas de plus grand diviseur de 0. On définit cependant PGCD(0;0) = 0.

Applications

Simplification de fractions

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 $\frac a d$ et le dénominateur $\frac b d$, où d = PGCD(a;b).

Exemple  :

En sachant que PGCD(30;18)=6, puis en remarquant que $\frac{30}{6}=5$ et $\frac{18}{6}=3$, on déduit que $\frac{30}{18}=\frac{5}{3}$, cette dernière fraction étant irréductible.

Équations diophantiennes

Article connexe : équation diophantienne.

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.

Article détaillé : triplet pythagoricien.

Une autre équation diophantienne classique est la recherche des triplets pythagoriciens. Un triplet pythagoricien est la donné de trois nombres entiers x, y et z qui vérifient la relation de Pythagore : x² + y² = z². 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 PGCD

Il existe plusieurs méthodes pour déterminer le PGCD de deux nombres.

Méthode naïve

Celle qui découle directement de la définition consiste à faire la liste des diviseurs des deux nombres, puis à chercher, dans ces deux listes, le diviseur commun le plus grand. Apparemment très simple, cette méthode devient difficile à mettre en place pour des grands nombres. En effet, certains nombres ont beaucoup de diviseurs (leur liste est donc longue à écrire et à classer) et d'autres en ont très peu. Il n'est pas possible de déterminer a priori le nombre de diviseurs d'un nombre quelconque. Notamment, le système de codage RSA s'appuie sur la très grande difficulté qu'il y a, même avec un ordinateur très puissant, à trouver les diviseurs de certains nombres.

Soustractions successives

Le PGCD de deux nombres a et b est aussi celui de a et b-a. Ceci justifie la méthode des soustractions successives, vue ici sur un exemple :

Exemple  :

Déterminons le PGCD de 675 et 660. Il est également celui de 660 et 675 — 660 = 15. Or, en appliquant les critères de divisibilité par 3 et par 5, on voit que 15 divise 660. Donc PGCD(15;660) = PGCD(675;660) = 15.

Algorithme d'Euclide

Articles connexes : Division euclidienne et Algorithme d'Euclide.

L'algorithme d'Euclide utilise la division euclidienne. Étant donnés deux nombres entiers naturels a et b, la division euclidienne de a par b est la recherche des deux nombres q et r tels que :

1. a = bq + r
2. 0 ≤ r ≤ b-1

Le nombre r est appelé le reste de cette division.

L'algorithme d'Euclide s'appuie également sur deux propriétés du PGCD :

1. le PGCD de a et b est égal au PGCD de b et r ;
2. si b divise a, alors le PGCD de a et b est b.

L'algorithme consiste, pour déterminer le PGCD de deux nombres a et b, à effectuer la division euclidienne de a par b (on trouve alors un reste r₁) puis la division euclidienne de b par r₁ (on note le reste trouvé r₂), puis celle de r₁ par r₂... Et ainsi de suite. La partie 2. de la définition de la division euclidienne assure que la suite r₁, r₂... est strictement décroissante et finira par s'annuler. Le PGCD de a et b est le dernier reste non nul de cette suite.

Exemple  :

Calculons le PGCD de 1071 et de 1029 à l'aide de l'algorithme d'Euclide.

La division euclidienne de 1071 et 1029 donne :

1071 = 1029 × 1 + 42

Donc PGCD(1071;1029) = PGCD(1029;42). On effectue la division euclidienne de 1029 par 42.

1029 = 42 × 24 + 21

Ainsi, PGCD(1029;42) = PGCD(42;21). On poursuit l'algorithme :

42 = 21 × 2 + 0

Cela signifie que 21 divise 42, donc PGCD(42;21) = 21. En « remontant » les égalités de PGCD ci-dessous, il vient :

21 = PGCD(42;21) = PGCD(1029;42) = PGCD(1071;1029)

Donc PGCD(1071;1029) = 21, qui est le dernier différent de zéro donné par l'algorithme.

En informatique, l'algorithme d'Euclide peut être programmé de façon récursive, avec une fonction qui s'appelle elle-même. En pseudo langage, si on dispose d'une fonction reste qui renvoie le reste de la division euclidienne d'un nombre par un autre, la fonction PGCD s'écrira :

fonction pgcd(a,b){

si b est égal à 0 renvoyer a

sinon renvoyer pgcd(b,reste(a,b))

}

Décomposition en facteurs premiers

Articles connexes : Nombre premier et Décomposition en facteurs premiers.

Les nombres premiers sont les « briques » avec lesquelles sont « construits » les nombres entiers. Tout nombre entier s'écrit de façon unique comme produit de nombres premiers. Ainsi :

360 = 2×2×2×3×3×5

qui se note

360 = 2³×3²×5

La connaissance de la décomposition en facteurs premiers d'un nombre entier permet de déterminer de nombreuses caractéristiques de ce nombre. Le PGCD n'échappe pas à la règle.

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 maximal qui apparaît à la fois dans a et b : le plus grand exposant commun à a et b.

Exemple  :

En remarquant que

360 = 2³×3²×5

et

48 = 2⁴×3

On remarque que les facteurs premiers apparaissant dans ces nombres sont 2 ; 3 et 5. Le nombre 2 apparaît avec les exposant 3 et 4, donc son plus grand exposant commun est 3. Pour 3, le plus grand exposant commun est 1 (en considérant que 3 = 3¹). Le facteur 5 apparaît dans une décomposition mais pas dans l'autre. Le PGCD de 360 et 48 sera donc 2³×3, soit 24.

Histoire

Sources et références

Bibliographie

La notion de PGCD de nombres entiers est traitée en classes de troisième et terminale scientifique (enseignement de spécialité mathématiques) en France. Par conséquent, les manuels scolaires de ces classes peuvent être consultés pour étudier ce sujet.

Notes