Extended Euclidean Algorithm
The Euclidean algorithm is arguably one of the oldest and most widely known algorithms. It is a method of computing the greatest common divisor (GCD) of two integers \(a\) and \(b\).
Contents
Euclidean Algorithm
The Euclidean algorithm is basically a continual repetition of the division algorithm for integers. The point is to repeatedly divide the divisor by the remainder until the remainder is 0. The GCD is the last nonzero remainder in this algorithm. The example below demonstrates the algorithm to find the GCD of 102 and 38. \[\begin{align} 102 &= 2 \times 38 + 26 \\ 38 & = 1 \times 26 + 12\\ 26 & = 2 \times 12 + 2 \\ 12 &= 6 \times 2 + 0. \end{align}\] The GCD is 2 because it is the last non zero remainder that appears before the algorithm terminates.
Use Euclid's algorithm to find the GCD of 42823 and 6409.
We have
\[\begin{align} 42823 &= 6409 \times 6 + 4369 \\ 6409 &= 4369 \times 1 + 2040 \\ 4369 &= 2040 \times 2 + 289\\ 2040 &= 289 \times 7 + 17 \\ 289 &= 17 \times 17 + 0. \end{align}\]
The last nonzero remainder is 17, thus the GCD is 17. \(_\square\)
This algorithm can be beautifully implemented using recursion:
Recursive Implementation of Euclid's Algorithm
1 2 3 4 5 6 

Extended Euclidean Algorithm
The extended Euclidean algorithm is an algorithm to compute integers \(x\) and \(y\) such that
\[ax + by = \gcd(a,b)\]
given \(a\) and \(b\).
The existence of such integers is guaranteed by Bezout Lemma.
The extended Euclidean algorithm can be viewed as the reciprocal of modular exponentiation.
By reversing the steps in the Euclidean algorithm, it is possible to find these integers \(x\) and \(y\). The whole idea is to start with the gcd and recursively work our way backwards. This can be done by treating the numbers as variables until we end up with an expression that is a linear combination of our initial numbers. We shall do this with the example we used above.
We start with our GCD. We rewrite it in terms of the previous two terms: \[2 = 26  2 \times 12 .\] We replace for \(12\) by taking our previous line (\(38 = 1 \times 26 + 12\) ) and writing it in terms of 12: \[2 = 26  2 \times (38  1\times 26). \] Collect like terms, the \(26\)'s, and we have \[2 = 3 \times 26  2 \times 38. \] Repeat the process: \[2 = 3 \times (102  2\times 38)  2\times 38.\] The final result is our answer: \[2 = 3 \times 102  8 \times 38.\] Thus \(x\) and \(y\) are \(102\) and \(8\).
Find two integers \(a\) and \(b\) such that \(1914a + 899b = \gcd(1914,899). \)
First use Euclid's algorithm to find the gcd: \[\begin{align} 1914 &= 2\times 899 + 116 \\ 899 &= 7 \times 116 + 87 \\ 116 &= 1 \times 87 + 29 \\ 87 &= 3 \times 29 + 0. \end{align}\] From this the last nonzero remainder (GCD) is \(29\). Now we use the extended algorithm: \[\begin{align} 29 &= 116 + (1)\times 87\\ 87 &= 899 + (7)\times 116. \end{align}\] Substituting for \(87\) in the first equation, we have \[\begin{align} 29 &= 116 + (1)\times (899 + (7)\times 116) \\ &= (1)\times 899 + 8\times 116 \\ &= (1)\times 899 + 8\times ( 1914 + (2)\times 899 )\\ &= 8\times 1914 + (17) \times 899 \\ &= 8\times 1914  17 \times 899. \end{align}\] Since we now wrote the GCD as a linear combination of two integers, we terminate the algorithm and conclude \[ a = 8, b =17. \ _\square\]
Pseudocode of the Algorithm
1 2 3 4 5 6 7 8 9 10 11 12 

Find the value of \(x\) and \(y\) for the following equation: \[\]
\[1432x + 123211y = \gcd(1432,123211). \]
We can write python code that implements the pseudocode to solve the problem.
Python Solution
1 2 3 4 5 6 7 8 9 10 

This gives 22973 and 267 for \(x\) and \(y\).