La fonction calcule un couple de coefficients de Bézout . (deux entiers u et v tels que au + bv = PGCD(a, b). exemple: euclide(13,11) retourne alors : ‘13x-5 + 11x6 = 1’
def euclide(a,b): r,u,v,r2,u2,v2=a,1,0,b,0,1 while r2!=0: q=r//r2 r,u,v,r2,u2,v2=r2,u2,v2,r-q*r2,u-q*u2,v-q*v2 return str(a)+"*"+str(u)+" + "+str(b)+"*"+str(v)+" = "+str(r)