What is Extended Euclidean Algorithm?

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:

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

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

Below is a Python program that recursively computes the integers $s$ and $t$ and the GCD via the Extended Euclidean Algorithm:

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.