Extended Euclid algorithm for GCD in Python

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 does the algorithm work. The below code also has basic GCD algorithm just for reference.

def gcd(a,b):
	if (b==0):
		g = a
	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)	
# 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
print "gcd: ", ans
print "a" + "\t" + "b" + "\t" + "g" +"\t" + "m" + "\t" + "n"
print "-"*35

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

Similar Posts

One Comment

  1. Gгeetings! Very helpful advice within this artіcle!

    It’ѕ the little changes whicһ will make thе most signifiсant
    changes. Thanks for sһaring!

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.