Algorithme d'Euclide

L'algorithme d'Euclide permet de calculer le PGCD de deux nombres a et b.
Dans la division Euclidienne a = b×q + r, tout diviseur de b et r divise a, et tout diviseur de a et b divise r = a - b×q.
Le PGCD de a et b est donc le PGCD de b et r.

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) 
L'algorithme se termine toujours puisque la suite des rn est strictement décroissante.

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 :
 PiQi-1 - Pi-1Qi = (-1)i-1  (invariant de boucle)
Cette relation prouve (théorème de Bézout) que PGCD(Pi, Qi) = 1
Pn+1 / Qn+1 = a/b = (a/p) / (b/p) avec p = PGCD(a,b).
Soit Pn+1 = a/p et Qn+1 = b/p
Alors : Pn+1Qn - PnQn+1 = (-1)n donne Qna/p - Pnb/p = (-1)n
Ou encore :  (-1)n.Qna/p + (-1)n+1.Pnb/p = 1  CQFD.

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
La condition a>b peut être ignorée, la première division donne si a<b :
a = 0×b + a et au tour suivant tout rentre dans l'ordre.
La condition sur les signes peut elle aussi être supprimée si la division signée de a par b utilisée est bien telle que :
a = b.q + r, 0≤|r|<|b|, avec a,b,q,r Z au lieu de N. Mais dire que le PGCD(-3,2) = -1 n'est pas très standard !

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

 

Accueil Arithmétiques Géométrique Divers Thèmes Scripts Jeux Exercices Précédent Suivant