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\). It allows computers to do a variety of simple number-theoretic tasks, and also serves as a foundation for more complicated algorithms in number theory.
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 non-zero 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 non-zero remainder is 17, and thus the GCD is 17. \(_\square\)
This algorithm can be beautifully implemented using recursion as shown below:
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 Bézout's 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 \(3\) 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 non-zero 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\]
Explaining the Algorithm
Without loss of generality we can assume that \(a\) and \(b\) are non-negative integers, because we can always do this: \(\gcd(a,b)=\gcd\big(\lvert a \rvert, \lvert b \rvert\big)\).
Let's define the sequences \(\{q_i\},\{r_i\},\{s_i\},\{t_i\}\) with \(r_0=a,r_1=b\). Set \(i \gets 2\), and increase it at the end of every iteration. We're going to find in every iteration \(q_i, r_i, s_i, t_i\) such that \(r_{i-2}=r_{i-1}q_i+r_i\), \(0 \leq r_i < r_{i-1}\) using the division algorithm. We also want to write \(r_i\) as a linear combination of \(a\) and \(b\), i.e., \(r_i=s_i a+t_i b\). But \(r_i=r_{i-2}-r_{i-1}q_i\), so
\[r_i=s_{i-2}a+t_{i-2}b-(s_{i-1}a+t_{i-1}b)q_i=(s_{i-2}-s_{i-1}q_i)a+(t_{i-2}-t_{i-1}q_i)b.\]
Hence, we obtain \(s_i=s_{i-2}-s_{i-1}q_i\) and \(t_i=t_{i-2}-t_{i-1}q_i\).
Now, we have to find the initial values of the sequences \(\{s_i\}\) and \(\{t_i\}\). By the definition of \(r_i,\) we have
\[\begin{align} a=r_0=s_0 a+t_0 b &\implies s_0=1, t_0=0\\ b=r_1=s_1 a+t_1 b &\implies s_1=0, t_1=1. \end{align}\]
Finally, we stop at the iteration in which we have \(r_{i-1}=0\). Let's call this the \(n^\text{th}\) iteration, so \(r_{n-1}=0\). That means that \(\gcd(a,b)=\gcd(r_0,r_1)=\gcd(r_1,r_2)=\cdots=\gcd(r_{n-2},r_{n-1})=\gcd(r_{n-2},0)=r_{n-2}\), so we found our desired linear combination:
\[\gcd(a,b)=r_{n-2}=s_{n-2} a + t_{n-2} b.\]
This algorithm is always finite, because the sequence \(\{r_i\}\) is decreasing, since \(0 \leq r_i < r_{i-1}\) for \(2 \leq i < n-1\), so \(r_2 > r_3 > \cdots > r_{n-2} > r_{n-1} = 0\). In some moment we reach the value of zero, because all of the \(r_i\) are integers.
To implement the algorithm, note that we only need to save the last two values of the sequences \(\{r_i\}\), \(\{s_i\}\) and \(\{t_i\}\).
Pseudo-code 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 pseudo-code to solve the problem. (See the code in the next section.)
This gives -22973 and 267 for \(x\) and \(y,\) respectively. \(_\square\)
Python Solution
1 2 3 4 5 6 7 8 9 10 | |