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 $a$ and $b$. GCD is the largest integer that divides both $a$ and $b$ 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 $q$ and $r$ such that:

$a=bq+r$ where $0<=r <=b$

$q$ is known as the quotient and $r$ is the remainder. The Euclidean Algorithm repeatedly applies the division algorithm to find the GCD of integers $a$ and $b$. 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 $s$ and $t$ such that $as+bt=gcd(a,b)$.

Bézout’s Identity guarantees the existence of $s$ and $t$.

Extended Euclidean Algorithm finds $s$ and $t$ 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 $s$ and $t$ such that $56s + 15t =gcd(56,15)$

extendedGCD(56,15)

Below is a Python program that recursively computes the integers $s$ and $t$ 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, tdef 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 $s$ and $t$ using the updateCoeff() function after each recursive call.

RELATED TAGS

algorithms

CONTRIBUTOR

Abdul Monum 