On donne deux entiers (a,b), la fonction retourne (u,v,d) tels que au+bv=d est le PGCD de a et b.
bezout(287,129) renvoie (-40,89,1) car -40×287+89×129=1, ils sont premiers entre eux. Pour information, deux autres versions, une par soustraction et une autre, sans appel récursif et plus compréhensible: à chaque étape du calcul d’Euclide des restes des divisions successives.
def bezout(a,b): # Par division if a == 0: return (0, 1, b) else: v, u, d = bezout(b % a, a) return (u - (b // a) * v, v, d) def bezout_(a,b): # Par soustractions if a == 0: return (0, 1, b) elif a>b: u, v, d = bezout(a-b, b) return (u, v-u, d) v, u, d = bezout(b-a, a) return (u-v, v, d) def bezout__(a,b): # Renvoie (u,v,d) tels que a*u+b*v=d le PGCD(a,b) rkm1 = a # r_{k-1}, ici r_0 rk = b # r_k, ici r_1 (ukm1,vkm1) = (1,0) # (u_0, v_0) (uk,vk) = (0,1) # (u_1, v_1) while rk != 0: # On s'arrete quand le dernier reste est nul r = rkm1 % rk # Sinon on calcule la division de rk par rk q = (rkm1-r)//rk # Quotient entier (u,v)=(ukm1-q*uk,vkm1-q*vk) # Nouvelles valeurs (ukm1,vkm1)=(uk,vk) # On decale u,v (uk,vk)=(u,v) rkm1=rk # On decale r rk=r return (ukm1,vkm1,rkm1) # le dernier reste non nul est le PGCD