#Fonction DEI: division euclidienne iterative par algorithme des differences

def DEI(a,b):
    r=a
    q=0
    while(r-b>=0):
        q=q+1
        r=r-b
    return (q,r)


# Version recursive
def DER(a,b):
    def DER1(b,q,r):
        if (r<b) :
            return (q,r)
        else :
            return DER1(b,q+1,r-b)
    return DER1(b,0,a)



def PGCDR(a,b):
    (q,r)=DEI(a,b)
    if r==0:
        return b
    else:
        return PGCDR(b,r)



def PGCDI(a,b):
    aa,bb=a,b
    (q,r)=DEI(aa,bb)
    while(r!=0):
        aa,bb=bb,r
        (q,r)=DEI(aa,bb)
    return bb
    

def BEZOUTI(a,b):
    aa,bb=a,b
    u,v,uu,vv=1,0,0,1
    (q,r)=DEI(aa,bb)
    while(r!=0):
        aa,bb=bb,r
        uu,vv,u,v=u-q*uu,v-q*vv,uu,vv
        (q,r)=DEI(aa,bb)
    return(uu,vv)

def BEZOUTR(a,b):
    def BEZOUTR1(a,b,u,v,uu,vv):
        (q,r)=DEI(a,b)
        if r==0:
            return (uu,vv)
        else:
            return BEZOUTR1(b,r,uu,vv,u-q*uu,v-q*vv)
    return BEZOUTR1(a,b,1,0,0,1)
        

#zone de test: commenter/decommenter les lignes pour tester les fonctions


#print DEI(input("a="),input("b="))
#print DER(input("a="),input("b="))

#print PGCDR(input("a="),input("b="))
#print PGCDI(input("a="),input("b="))

#a=input("a=")
#b=input("b=")
#(uu,vv)=BEZOUTI(a,b)
#
#print(str(a)+"*"+str(uu)+"+"+str(b)+"*"+str(vv)+"="+str(a*uu+b*vv))
#
#a=input("a=")
#b=input("b=")
#(uu,vv)=BEZOUTR(a,b)
#
#print(str(a)+"*"+str(uu)+"+"+str(b)+"*"+str(vv)+"="+str(a*uu+b*vv))