Trusted answers to developer questions

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.

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:

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

def GCD(a, b):if a == 0:return breturn 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))

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)$

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, 1gcd, 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)

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

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

Related Courses