euclide_etendu.py

Created by remy-cobena

Created on May 02, 2018

227 Bytes

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)