# coding: utf8

def division_euclidienne(a,b):
	reste=a
	quotient=0
	while reste > b-1:
	    reste=reste-b
	    quotient=quotient+1
	return(reste,quotient)


def euclide(a,b):
    if b==0:
	    print("Le pgcd de "+str(a)+" et 0 est "+str(a)+".")
    else:
       a0=a ; b0=b ; newa=a ; newb=b  
       [r,q]=division_euclidienne(newa,newb)
       print(str(newa)+" = "+str(newb)+" x "+str(q)+" + "+str(r))
       while not(r==0): 
	   newa=newb ; newb=r    
	   [r,q]=division_euclidienne(newa,newb)
	   print(str(newa)+" = "+str(newb)+" x "+str(q)+" + "+str(r))
       print("Le pgcd de "+str(a0)+" et "+str(b0)+" est le dernier reste non nul, c'est donc "+str(newb)+".")


def euclide_etendu(a,b):
    if b==0:
	  print("Le pgcd de "+str(a)+" et 0 est "+str(a)+".")
	  print("Une relation de Bezout pour "+str(a)+" et 0 est")
	  print(str(a)+" x 1 +"+str(b)+" x 0 = "+str(a))
    if not(b==0): 
	    print(str(a)+" x 1 +"+str(b)+" x 0 = "+str(a)+"      (L00)")
	    print(str(a)+" x 0 +"+str(b)+" x 1 = "+str(b)+"      (L0)")
	    u=1 ; v=0 ; w=0 ; z=1 
	    newa=a ; newb=b
	    step=1
	    [r,q]=division_euclidienne(newa,newb)
	    while not(r==0):
		    if step-2==-1:
			    chL2="00"
		    else:
			    chL2=str(step-2)
		    print("")
		    print("Division euclidienne n° "+str(step)+" : "+str(newa)+" = "+str(newb)+" x "+str(q)+" + "+str(r))
		    print("")
		    print("On pose : (L"+str(step)+") = (L"+chL2+") - "+str(q)+" x (L"+str(step-1)+")")
		    print("")
		    neww=u-q*w;newz=v-q*z;u=w;v=z;w=neww;z=newz
		    if w<0:
			    chw="("+str(w)+")"
		    else:
			    chw=str(w)
		    if z<0:
			    chz="("+str(z)+")"
		    else:
			    chz=str(z)
		    print(str(a)+" x "+chw+" +"+str(b)+" x "+chz+" = "+str(r)+"      (L"+str(step)+")")
		    newa=newb ; newb=r
		    step=step+1
		    [r,q]=division_euclidienne(newa,newb)
	    print("")
	    print("Division euclidienne n° "+str(step)+" : "+str(newa)+" = "+str(newb)+" x "+str(q)+" + "+str(r))
	    print("")  
	    print("La division euclidienne n° "+str(step)+" a un reste nul.")
	    print("Le pgcd de "+str(a)+" et "+str(b)+" est donc le reste de la division euclidienne n° "+str(step-1)+", c'est-à-dire "+str(newb)+",")
	    print("et (L"+str(step-1)+") donne une relation de Bezout pour "+str(a)+" et "+str(b)+".")