Supplementary material for the
The Euclidean algorithm is a way to find the greatest common divisor of two positive integers, a and b. First let me show the computations for a=210 and b=45.
Formal description of the Euclidean algorithm|
Here is one link which describes the algorithm. Here's another link, with more information. If you want to "do" some further examples, Paul Garrett of the University of Minnesota has a Visible Euclidean algorithm page where you can specify further examples and see the algorithm work..
Why does the algorithm stop?|
At each step, the remainder, r, decreases by at least 1. Therefore r must eventually be 0. A formal proof would use mathematical induction.
Why is the answer actually equal to the GCD?|
In the final stage, when r=0, we see that the "final b" must divide the final a. Go backwards along the string of equations (a=q·b+r), and you will see that at each step, the "final b" divides each of the parts of the equation. Therefore the "final b" must be a divisor of both of the initial a and initial b.
Now look at the first equation. In the equation a=q·b+r, the GCD divides both a and b and therefore must divide r as well (because a-q·r is a multiple of the GCD). Now carry this observation through all of the equations, forward. The GCD must divide two of the three pieces in all of the equations, and thus must divide the third. Therefore, the GCD also divides the "final b". So the "final b" divides both a and b, and is itself a multiple of the GCD. Well, the GCD is the greatest such divisor, and therefore the "final b" must be equal to the GCD of the initial values.
The extended Euclidean algorithm
Here's a true statement:
|If a and b are positive integers, then there are always integers m and n so that the GCD of a and b equals m·a+n·b.|
The extended Euclidean algorithm has a very important use: finding multiplicative inverses mod P. Choose a prime, P: how about 97. I know 97 is prime, because 2 and 3 and 5 and 7 and even 11 aren't factors of 97, and I only need to check division by primes up to the square root of 97.
Now let me take a fairly random integer, say 20. Since 20 is less than 97, and 97 is prime, the GCD of 20 and 97 should be 1. (Remember, since 97 is prime, its only divisors are itself and 1.) I will verify this by "running" the Euclidean algorithm:
Find the multiplicative inverse of 60 mod 97 by hand. As I mentioned in class, doing just one of these computations "by hand" is good enough. Here's a link to the answer.
The extended Euclidean algorithm is easy to implement on a computer and the amount of memory needed is not large. The algorithm runs very fast. For example, I am currently running a copy of Maple in another window on a PC which is neither very fast nor has much memory. I just selected a 100 decimal digit prime, P, and found the multiplicative inverse of a 50 decimal digit number mod P. The system returned 0.00 as the amount of time used. That is, the computation used less than .01 seconds!