Supplementary material for the
lecture of Monday, July 12

The Euclidean algorithm

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.

Let's see. Several questions occur immediately..
  1. What's going on here?
  2. Why does the algorithm stop?
  3. Why is the answer correct?
O.k. I will answer first question by giving a formal description of the algorithm, which supposedly finds the greatest common divisor (GCD) of two integers. This "greatest common divisor" must exist, since positive integer divisors of integers can't be any larger than the integers:

Formal description of the Euclidean algorithm
  • Input Two positive integers, a and b.
  • Output The greatest common divisor, g, of a and b.
  • Internal computation
    1. If a<b, exchange a and b.
    2. Divide a by b and get the remainder, r. If r=0, report b as the GCD of a and b.
    3. Replace a by b and replace b by r. Return to the previous step.

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 (described, for example, here, allows the computation of multiplicative inverses mod P. First let's see an example. Since the GCD of 210 and 45 is 15, we should be able to write 15 as a sum of multiples of 210 and 45. Here's how to do it. We look carefully at the steps above and change them each.

The greatest common divisor of 210 and 45 is 15, and we have written 15 as a sum of integer multiples of 210 and 45.

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:

The extended Euclidean algorithm allows us to write 1 as a sum of 97 and 20. Here we go: The final equation tells us that 1=-7·97+34·20, which means that the product of 34 and 20 is equal to 1 plus a multiple of 97. But in mod 97, we ignore multiples of 97. Therefore 34 is the multiplicative inverse of 20 mod 97.

Exercise
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!

Maintained by greenfie@math.rutgers.edu and last modified 7/13/2004.