Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithms

What is Extended Euclidean Algorithm?

Abdul Monum

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Extended Euclidean Algorithm is an extension of the Euclidean Algorithm that computes the greatest common divisor (GCD) of integers aa and bb. GCD is the largest integer that divides both aa and bb without any remainder.

Euclidean Algorithm

Recall the division algorithm from grade school. When we divide an integer from a non-zero integer, there exists integers qq and rr such that:

a=bq+ra=bq+r where 0<=r<=b0<=r <=b

qq is known as the quotient and rr is the remainder. The Euclidean Algorithm repeatedly applies the division algorithm to find the GCD of integers aa and bb. We repeatedly divide the divisor by the remainder until the remainder is zero. The last non-zero remainder is the greatest common divisor. Below is an example of how to use the Euclidean Algorithm to find the GCD of 56 and 15:

GCD(56,15)

Below is a Python program that recursively computes the GCD via the Euclidean Algorithm:

def GCD(a, b):
if a == 0:
return b
return GCD(b%a, a)
print("GCD(25,10)=", GCD(25,10))
print("GCD(63,57)=", GCD(63,57))
print("GCD(7,9)=", GCD(7,9))
print("GCD(4,14)=", GCD(4,16))

Extended Euclidean Algorithm

In addition to computing GCD, Extended Euclidean Algorithm also finds integers ss and tt such that as+bt=gcd(a,b)as+bt=gcd(a,b).

Bézout’s Identity guarantees the existence of ss and tt.

Extended Euclidean Algorithm finds ss and tt by using back substitutions to recursively rewrite the division algorithm equation until we end up with the equation that is a linear combination of our initial numbers. Below is an example of how to use the Extended Euclidean Algorithm to find the GCD of 56 and 15 to find ss and tt such that 56s+15t=gcd(56,15)56s + 15t =gcd(56,15)

extendedGCD(56,15)

Below is a Python program that recursively computes the integers ss and tt and the GCD via the Extended Euclidean Algorithm:

def extendedGCD(a, b):
if a == 0:
return b, 0, 1
gcd, s1, t1 = extendedGCD(b%a, a)
s,t = updateCoeff(a,b,s1,t1)
return gcd, s, t
def updateCoeff(a,b,s,t):
return (t - (b//a) * s, s)
gcd, s, t = extendedGCD(25,10)
print("extendedGCD(25,10)-> ", "GCD:", gcd,"\ts:", s, "\tt:",t)
gcd, s, t = extendedGCD(63,57)
print("extendedGCD(63,57)-> ", "GCD:", gcd,"\ts:", s, "\tt:",t)
gcd, s, t = extendedGCD(7,9)
print("extendedGCD(7,9)-> ", "GCD:", gcd,"\ts:", s, "\tt:",t)

Explanation

In the above code, we find the GCD in the same way as the Euclidean Algorithm but in addition, we update the values of ss and tt using the updateCoeff() function after each recursive call.

RELATED TAGS

algorithms

CONTRIBUTOR

Abdul Monum
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring