San Vu Ngoc - IRMAR
Ici aussi on choisit d'abord une méthode récursive, la plus simple du point de vue mathématique, et aussi la plus facile à programmer.
Supposons par récurrence que $bu' + rv' = d = pgcd(b,r)$, alors en utilisant $a = bq + r$ on voit que $bu' + (a-bq)v' = d$ donc $$ av' + b(u' - qv') = d =pgcd(a,b).$$
Remarque: La suite des "restes" est la même que pour l'algorithme d'Euclide, donc on sait que ça termine. Et la complexité est la même.
def Bezout (a,b):
"cette fonction retourne (d,u,v) tel que au+bv=d, où d = pgcd(a,b)"
if b == 0:
return (a, 1, 0)
else:
r = a % b
q = a // b
print("%d = %d*%d + %d" % (a,q,b,r))
d,uu,vv = Bezout(b,r)
print ("* %d*(%d) + %d*(%d) = %d" % (a,vv, b, uu - vv*q, d))
return (d, vv, uu - vv*q)
Bezout(1234,2020)
1234 = 0*2020 + 1234 2020 = 1*1234 + 786 1234 = 1*786 + 448 786 = 1*448 + 338 448 = 1*338 + 110 338 = 3*110 + 8 110 = 13*8 + 6 8 = 1*6 + 2 6 = 3*2 + 0 * 6*(0) + 2*(1) = 2 * 8*(1) + 6*(-1) = 2 * 110*(-1) + 8*(14) = 2 * 338*(14) + 110*(-43) = 2 * 448*(-43) + 338*(57) = 2 * 786*(57) + 448*(-100) = 2 * 1234*(-100) + 786*(157) = 2 * 2020*(157) + 1234*(-257) = 2 * 1234*(-257) + 2020*(157) = 2
(2, -257, 157)
Vérifions:
-257*1234 + 157*2020
2
Puisque le $pgcd$ est 2, on peut diviser chaque nombre par 2: $1234=2\times 617$ et $2020=2\times 1010$.
Que se passe-t'il quand on calcule $pgcd(2\times a, 2\times b)$ ?
En suivant les étapes de l'algo, on voit bien que ce sont les mêmes que $pgcd(a,b)$: il suffit de "multiplier chaque ligne par 2".
Cette remarque fournit une preuve de la formule $pgcd(ka,kb) = |k| pgcd(a,b)$ (qu'on peut démontrer aussi avec le théorème de Bézout).
Bezout(617,1010)
617 = 0*1010 + 617 1010 = 1*617 + 393 617 = 1*393 + 224 393 = 1*224 + 169 224 = 1*169 + 55 169 = 3*55 + 4 55 = 13*4 + 3 4 = 1*3 + 1 3 = 3*1 + 0 * 3*(0) + 1*(1) = 1 * 4*(1) + 3*(-1) = 1 * 55*(-1) + 4*(14) = 1 * 169*(14) + 55*(-43) = 1 * 224*(-43) + 169*(57) = 1 * 393*(57) + 224*(-100) = 1 * 617*(-100) + 393*(157) = 1 * 1010*(157) + 617*(-257) = 1 * 617*(-257) + 1010*(157) = 1
(1, -257, 157)
Bezout(600,124)
600 = 4*124 + 104 124 = 1*104 + 20 104 = 5*20 + 4 20 = 5*4 + 0 * 20*(0) + 4*(1) = 4 * 104*(1) + 20*(-5) = 4 * 124*(-5) + 104*(6) = 4 * 600*(6) + 124*(-29) = 4
(4, 6, -29)
À chaque étape on écrit le "reste courant" comme CL(a,b).
La formule des coefficients de Bézout $(u_n,v_n)$ (construits par récurrence) a été vue en cours.
def BezoutI (a,b):
"cette fonction retourne (d,u,v) tel que au+bv=d"
uu, vv = 1, 0
u, v = 0, 1
rr, r = a, b # invariants de boucle: a*u + b*v = r et a*uu = b*vv = rr
while r != 0:
q = rr // r # on divise l'ancien reste "r(n-1)" (rr) par le reste "r(n)" (r)
print ("On a %d = %d*%d + %d," % (rr, q, r, rr % r ))
r, rr = rr % r, r
u, uu = uu - q*u, u # on calcule les nouveaux coefficients u,v
v, vv = vv - q*v, v
print (" donc %d = %d*(%d) + %d*(%d)." % (r, a, u, b, v))
return (rr,uu,vv)
BezoutI(600,124)
On a 600 = 4*124 + 104, donc 104 = 600*(1) + 124*(-4). On a 124 = 1*104 + 20, donc 20 = 600*(-1) + 124*(5). On a 104 = 5*20 + 4, donc 4 = 600*(6) + 124*(-29). On a 20 = 5*4 + 0, donc 0 = 600*(-31) + 124*(150).
(4, 6, -29)
BezoutI(1234,2020)
On a 1234 = 0*2020 + 1234, donc 1234 = 1234*(1) + 2020*(0). On a 2020 = 1*1234 + 786, donc 786 = 1234*(-1) + 2020*(1). On a 1234 = 1*786 + 448, donc 448 = 1234*(2) + 2020*(-1). On a 786 = 1*448 + 338, donc 338 = 1234*(-3) + 2020*(2). On a 448 = 1*338 + 110, donc 110 = 1234*(5) + 2020*(-3). On a 338 = 3*110 + 8, donc 8 = 1234*(-18) + 2020*(11). On a 110 = 13*8 + 6, donc 6 = 1234*(239) + 2020*(-146). On a 8 = 1*6 + 2, donc 2 = 1234*(-257) + 2020*(157). On a 6 = 3*2 + 0, donc 0 = 1234*(1010) + 2020*(-617).
(2, -257, 157)