PGCD et algorithme d'Euclide

Le PGCD (plus grand commun diviseur) de deux entiers naturels non nuls a et b est le plus grand entier qui divise à la fois a et b. On le note PGCD(a, b), ou pgcd(a, b) : par exemple, PGCD(84, 126) = 42. On le calcule soit avec les décompositions en facteurs premiers, soit, plus rapidement pour les grands nombres, avec l'algorithme d'Euclide, une suite de divisions euclidiennes dont le dernier reste non nul est le PGCD. Ce chapitre présente les deux méthodes, la notion d'entiers premiers entre eux et les applications du PGCD.

Définition

Les diviseurs de 84 sont 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84. Ceux de 126 sont 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63, 126. Leurs diviseurs communs sont 1, 2, 3, 6, 7, 14, 21 et 42. Le plus grand est 42 : PGCD(84, 126) = 42.

Lister les diviseurs marche pour de petits nombres, mais devient vite fastidieux. Deux méthodes plus efficaces suivent.

Méthode 1 : avec les décompositions en facteurs premiers

Décompose les deux nombres (chapitre 6), puis garde les facteurs premiers communs, chacun avec le plus petit exposant.

Exemple : PGCD(84, 126).

84 = 2² × 3 × 7
126 = 2 × 3² × 7
Facteurs communs : 2 (exposants 2 et 1, on garde 1), 3 (exposants 1 et 2, on garde 1), 7 (exposant 1).

PGCD(84, 126) = 2 × 3 × 7 = 42.

Exemple : PGCD(4 410, 1 188).

4 410 = 2 × 3² × 5 × 7²
1 188 = 2² × 3³ × 11
Facteurs communs : 2 (on garde 2¹) et 3 (on garde 3²). 5, 7 et 11 ne sont pas communs.

PGCD(4 410, 1 188) = 2 × 3² = 18.

Cette méthode est claire, mais elle demande de décomposer les deux nombres, ce qui devient long dès qu'ils ont de grands facteurs premiers.

Méthode 2 : l'algorithme d'Euclide

L'algorithme d'Euclide repose sur une propriété de la division euclidienne :

On remplace donc le couple (a, b) par le couple (b, r), plus petit, et on recommence. Les restes diminuent à chaque étape, donc on finit forcément par obtenir un reste nul. Comme PGCD(x, 0) = x, le PGCD est le dernier reste non nul.

La méthode :

fais la division euclidienne de a par b : a = b × q + r ;
si r = 0, le PGCD est b ;
sinon, remplace a par b et b par r, et recommence.

Exemple : PGCD(4 410, 1 188).

a	b	Division euclidienne	Reste r
4 410	1 188	4 410 = 1 188 × 3 + 846	846
1 188	846	1 188 = 846 × 1 + 342	342
846	342	846 = 342 × 2 + 162	162
342	162	342 = 162 × 2 + 18	18
162	18	162 = 18 × 9 + 0	0

Le dernier reste non nul est 18 : PGCD(4 410, 1 188) = 18. On retrouve le résultat de la méthode 1, sans avoir décomposé quoi que ce soit.

Pourquoi l'algorithme est-il rapide ? Le reste diminue très vite : on montre qu'il est au moins divisé par deux toutes les deux étapes. Pour deux nombres de 100 chiffres, il faut quelques centaines de divisions au plus, alors que décomposer de tels nombres en facteurs premiers est hors de portée des ordinateurs actuels. C'est l'un des plus anciens algorithmes connus (vers 300 avant notre ère) et il est toujours utilisé, par exemple dans les bibliothèques de chiffrement.

Une image de l'algorithme : découper un rectangle en carrés

On veut couvrir un panneau de 252 cm sur 180 cm avec des dalles carrées identiques, les plus grandes possible, sans découpe. Le côté d'une dalle doit diviser 252 et 180 : c'est leur PGCD.

252 = 180 × 1 + 72 ; 180 = 72 × 2 + 36 ; 72 = 36 × 2 + 0 : PGCD(252, 180) = 36

252 = 180 × 1 + 72 : on place un carré de 180, il reste une bande de 72 de large ;
180 = 72 × 2 + 36 : on place deux carrés de 72, il reste une bande de 36 ;
72 = 36 × 2 + 0 : deux carrés de 36 remplissent exactement la bande.

PGCD(252, 180) = 36. Les dalles font 36 cm de côté : 252 ÷ 36 = 7 dalles en longueur, 180 ÷ 36 = 5 en largeur, soit 35 dalles.

Entiers premiers entre eux

Deux entiers sont premiers entre eux quand leur PGCD vaut 1. L'algorithme d'Euclide le vérifie sans décomposer :

PGCD(89, 55) : 89 = 55 × 1 + 34 ; 55 = 34 × 1 + 21 ; 34 = 21 × 1 + 13 ; 21 = 13 × 1 + 8 ; 13 = 8 × 1 + 5 ; 8 = 5 × 1 + 3 ; 5 = 3 × 1 + 2 ; 3 = 2 × 1 + 1 ; 2 = 1 × 2 + 0. Le dernier reste non nul est 1 : 89 et 55 sont premiers entre eux.

(Les restes successifs sont les nombres de Fibonacci : c'est le cas où l'algorithme est le plus lent, avec des quotients tous égaux à 1.)

Le fait d'être premiers entre eux compte en arithmétique modulaire : un entier a a un inverse modulo n si et seulement si PGCD(a, n) = 1 (chapitre 9), et c'est la condition pour qu'une clé de chiffrement affine fonctionne.

Applications du PGCD

Simplifier une fraction. Pour rendre une fraction irréductible, divise le numérateur et le dénominateur par leur PGCD : 84/126 = (84 ÷ 42)/(126 ÷ 42) = 2/3.

Trouver le format d'un écran. Une résolution de 1 920 × 1 080 pixels : PGCD(1 920, 1 080) = 120, et 1 920 ÷ 120 = 16, 1 080 ÷ 120 = 9. Le format est 16:9. De même, 1 920 × 1 200 donne 16:10 (PGCD 240, soit 8:5), et 1 280 × 1 024 donne 5:4 (PGCD 256).

Partager en lots identiques. Un technicien doit répartir 84 câbles RJ45 et 126 attaches en kits identiques, sans reste, avec le plus de kits possible. Le nombre de kits divise 84 et 126 : le maximum est PGCD(84, 126) = 42 kits, chacun avec 2 câbles et 3 attaches.

Pour aller plus loin : le PPCM

Le PPCM (plus petit commun multiple) de deux entiers non nuls a et b est le plus petit entier strictement positif qui soit à la fois multiple de a et de b. Il vérifie :

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

PPCM(84, 126) = 84 × 126 ÷ 42 = 252. Avec les décompositions : on garde tous les facteurs premiers, chacun avec le plus grand exposant. 2² × 3² × 7 = 252.

Exemple d'usage : une tâche planifiée tourne tous les 6 jours, une autre tous les 8 jours. Elles ont tourné ensemble aujourd'hui ; elles tourneront de nouveau le même jour dans PPCM(6, 8) = 6 × 8 ÷ 2 = 24 jours.

Le PGCD en Python

python

import math

math.gcd(4410, 1188)   # 18
math.lcm(6, 8)         # 24 (Python 3.9 et plus)

La fonction math.gcd utilise l'algorithme d'Euclide. Le chapitre 11 le programme toi-même, en quatre lignes, comme un sujet peut le demander.