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 and . 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.
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:
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.
The last non-zero remainder is 17, and thus the GCD is 17.
This algorithm can be beautifully implemented using recursion as shown below:
1 2 3 4 5 6
The extended Euclidean algorithm is an algorithm to compute integers and such that
given and .
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 and . 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:
We replace for by taking our previous line and writing it in terms of 12:
Collect like terms, the 's, and we have
Repeat the process:
The final result is our answer:
Thus and are and .
Find two integers and such that
First use Euclid's algorithm to find the GCD:
From this, the last non-zero remainder (GCD) is . Now we use the extended algorithm:
Substituting for in the first equation, we have
Since we now wrote the GCD as a linear combination of two integers, we terminate the algorithm and conclude
Without loss of generality we can assume that and are non-negative integers, because we can always do this: .
Let's define the sequences with . Set , and increase it at the end of every iteration. We're going to find in every iteration such that , using the division algorithm. We also want to write as a linear combination of and , i.e., . But , so
Hence, we obtain and .
Now, we have to find the initial values of the sequences and . By the definition of we have
Finally, we stop at the iteration in which we have . Let's call this the iteration, so . That means that , so we found our desired linear combination:
This algorithm is always finite, because the sequence is decreasing, since for , so . In some moment we reach the value of zero, because all of the are integers.
To implement the algorithm, note that we only need to save the last two values of the sequences , and .
1 2 3 4 5 6 7 8 9 10 11 12
Find the value of and for the following equation:
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 and respectively.
1 2 3 4 5 6 7 8 9 10