Euclid’s recursive program-based algorithm to compute GCD (Greatest Common Divisor) is very straightforward. If we want to compute gcd(a,b) and b=0, then return a. Otherwise, recursively call the function using a=b and b=a mod b.
There is an extension to the basic Euclid’s algorithm for GCD, and it computes, besides the greatest common divisor of integers a and b, the coefficients of Bézout’s identity, that is, integers m and n such that ma + nb = gcd(a, b). The value of m & n may also be zero or negative. This algorithm, to compute the value of gcd and the coefficients, is also based on recursion. The following Python code explains how the algorithm works. The below code also has a basic GCD algorithm just for reference.
def gcd(a,b):
if (b==0):
g = a
else:
g=gcd(b,a%b)
return g
def extended_gcd(a,b):
if (b == 0):
# if b =0, then return g =a, m=1, n=0
print a,"\t",b,"\t",a,"\t",1,"\t",0
return (a,1,0)
else:
# if b is not 0, then recursively call the function to get the value of
# g,m,n at each step. The code also displays the value of a,b at each step
(g,m,n) = extended_gcd(b,a%b)
print a,"\t",b,"\t",g,"\t",n,"\t",m-(a//b)*n
return(g,n,m-(a//b)*n)
x=26
y=15
ans=gcd(x,y)
print "gcd: ", ans
print "a" + "\t" + "b" + "\t" + "g" +"\t" + "m" + "\t" + "n"
print "-"*35
extended_gcd(x,y)When I used a=26 and b=15, I got the following output. If you take the values of g,m,n at any step, you will find that they satisfy the expression ma + nb = gcd(a, b)
gcd: 1
a b g m n
-----------------------------------
1 0 1 1 0
3 1 1 0 1
4 3 1 1 -1
11 4 1 -1 3
15 11 1 3 -4
26 15 1 -4 7