def gcd(a,b):
'''Compute the gcd of two numbers'''
if b == 0:
return a
return gcd(b, a%b)
def printNumber(i):
if i%10 == 1:
return str(i)+ "st row"
elif i%10 == 2:
return str(i)+ "nd row"
else:
return str(i)+"th row"
def bezout(a, b, i=1, first = True, a_1 = 0, b_1=0):
if first == True:
a_1 = a
b_1 = b
print ("We would like to find Bezout coefficients of %d and %d")%(a, b)
print("That is x and y such that gcd(%d, %d)= %d = x*%d+y*%d")%(a,b, gcd(a,b) , a,b)
print ("__________________________________________________")
print "Initializing first equation:", "%d = (1)*%d + (0)*%d"%(a,a,b)
print "Initializing secod equation:", "%d = (0)*%d + (1)*%d"%(b,b,a)
a = (a, 1, 0)
b = (b, 0, 1)
if b[0] == 0:
print ("__________________________________________________")
return
quotient = a[0]//b[0]
a = (a[0]%b[0], a[1] - quotient*b[1],a[2] - quotient*b[2])
print printNumber(i)+" -(%d)*"%quotient +printNumber(i+1)+":-----> " + \
"%d = (%d)*%d + (%d)*%d"%(a[0],a[1],a_1, a[2],b_1)
return bezout(b,a, i+1, False, a_1, b_1)