Par exemple 32 = 12×2 + 8, PGCD(32,12) = PGCD (12,8)
On recommence alors :
12 = 8×1 + 4, PGCD(12,8) = PGCD (8,4)
8 = 4×2 + 0 et ici c'est fini, 8 est un multiple de 4, le PGCD est 4.
donc PGCD(32,12) = 4.
a0 = a, b0 = b, a>b>0 puis répéter :
| an = bn×qn + rn avec 0≤rn<bn | an+1 = bn, bn+1 = rn Le dernier reste non nul est le PGCD(a,b) |
Si on exprime les restes sous la forme r = a - b×q et en remontant les calculs, on obtient :
PGCD = 4 = 12 - 8×1
puis en remplaçant le reste 8 par sa valeur : 8 = 32 - 12×2
4 = 12 - (32 - 12×2)×1 = 12×(1 + 2×1) - 32×1 = 12×3 - 32×1
et finalement PGCD(a,b) = a.u + b.v : c'est le théorème de Bézout ! avec ici u = -1 et v = 3.
Et par la même occasion la solution de a.u + b.v = p avec p = PGCD(a,b)
Ainsi que le calcul de l'inverse de a modulo b si PGCD(a,b) = 1 :
a.u = 1 - b.v ≡ 1 (mod b).
Ces calculs à rebours peuvent se faire dans la foulée avec l'algorithme d'Euclide étendu :
a0 = a, b0 = b, a>b>0
et par convention P -2 = 0 ,Q -2 = 1 ,P -1 = 1 ,Q -1 = 0 puis répéter à partir de i = 0 : | ai = bi×qi + ri avec 0≤ri<bi | Pi = qiPi-1 + Pi-2 | Qi = qiQi-1 + Qi-2 | ai+1 = bi, bi+1 = ri Le dernier reste non nul rn est le PGCD(a,b) (-1)n.a.Qn + (-1)n+1.b.Pn = rn |
Par définition : a/b = a0/b0 = q0 + r0/b0 =
q0 + 1/(q1 + r1/b1) =
q0 + 1/(q1 + 1/(q2 + r2/b2)) = ...
On reconnaît la représentation en fraction continue de a/b.
Le dernier terme est rn/bn = 1/(qn+1 + 0)
Les Pi / Qi sont les réduites de la fraction continue :
P0 = q0, Q0 = 1 puis
P1 = q1q0 + 1, Q1 = q1,
puis par récurence : Pi / Qi = q0 + 1/(q1 + 1/(... + 1/qi))
En particulier la dernière réduite : Pn+1 / Qn+1 = a/b
Les relations sur les Pi, Qi peuvent s'écrire sous une forme matricielle :
(Pi Qi ) = (qi 1) × (Pi-1 Qi-1) (Pi-1 Qi-1) (1 0) (Pi-2 Qi-2)Le calcul du discriminant montre alors que la quantité PiQi-1 - Pi-1Qi est constante au signe près. Comme P -1Q -2 - P -2Q -1 = 1 :
Nota : On peut obtenir directement les (-1)n par l'algorithme modifié :
a0 = a, b0 = b, a>b>0
et par convention P -2 = 0 ,Q -2 = 1 ,P -1 = 1 ,Q -1 = 0 puis répéter à partir de i = 0 : | ai = bi×qi + ri avec 0≤ri<bi | Pi = -qiPi-1 + Pi-2 | Qi = -qiQi-1 + Qi-2 | ai+1 = bi, bi+1 = ri Le dernier reste non nul rn est le PGCD(a,b) a.Qn + b.Pn = rn |
Un script pour le calcul du PGCD et la résolution de ax + by = c.
Nota : une fois le PGCD calculé, le PPCM est a×b / PGCD(a,b) .