nav.gif (1245 bytes)mathematics

Ken Ward's Mathematics Pages

Number Theory Euclid's Algorithm

Number Theory Contents

Page Contents

  1. The Algorithm
    1. The Greatest Common Divisor
    2. Calculating the Greatest Common Divisor
  2. Proof of Euclid's Algorithm
    1. The Algorithm Eventually Reaches Zero
    2. The Last Non-Zero Remainder Divides The Two Initial Numbers
    3. The Last Non-Zero Remainder is the GCD

The Algorithm

Euclid's algorithm (or algorism) is a method of computing the greatest common divisor (gcd) of two numbers. It is very important in number theory and in computing.

The Greatest Common Divisor

Also known as "the greatest common factor", " the greatest common measure" of a number. The Greatest Common Divisor (gcd) of two numbers is the largest number which divides both of the numbers. If the two numbers are relatively prime, the gcd is 1.

For instance, the gcd of 9 and 15 is 3, because 3 is the largest number which divides both 9 and 15. This is written:
3=(9,15), or 3=gcd(9,15).

Calculating the Greatest Common Divisor

Example 1 
gcd(124,217)=31
nabremainder, r
1
217=124·1+93Divide the larger number, a, by the smaller, b, and add the remainder, r1.
2124=93·1+31The previous b, 124, becomes the new a. Divide a by b and add the remainder, r2.
393=31·3+0The new a is the old b, 93, and the new b is the old reminder, r2. Divide a by b and add the remainder, r3. The remainder is 0, so the gcd is the previous non-zero remainder (r2).

Note that the remainders become smaller and smaller, until they become zero, when the previous remainder is the gcd. We are using the algorithm with the least positive remainder. That is, all the remainders are positive.

gcd(97,42)=1
nabremainder, r
197=42·2+13We divide a by b and add the remainder. 
242=13·3+3The previous b becomes the new a, and the previous remainder, r1, becomes the new b, and we divide as before, adding the new remainder, r2.
313=3·4+1We continue in the pattern established.
43=1·3+0The remainder is now 0, so the previous non-zero remainder, r3, is the gcd. In this case, it is 1, so the numbers are relatively prime.

The remainders always become smaller and eventually become zero.

Least Absolute Remainder

In the previous examples, we have taken the least positive remainder (Although in the second example, the answer would be the same). The following example compares, the method using the least positive remainder, with the least absolute remainder.
gcd(987,960)=3
Least Positive RemainderLeast Absolute Remainder
nabrabr
1987=960·1+27987=960·1+27
2960=27·35+15960=27·35+15
327=15·1+1227=15·2-3
415=12·1+315=3·5+0
512=3·4+0

The least absolute remainder method terminates before the least positive remainder method. The least absolute method is always as fast as  the least positive method, if not faster (stated without proof). 

Although we normally write the gcd with a positive value, the sign is not important, because technically, the gcd is plus or minus (the factors of 960 are 3·320, and (-3)·(-320), giving gcd ±3). This means we do not have to ponder over its sign in (27=15·2-3) above!

Proof of Euclid's Algorithm

In our proof, we like to say that both a and b cannot be zero. And when one is zero, say b, then the gcd is taken as a, because a divides itself and, like all numbers divides zero (all numbers, that is, except zero itself, when the result is indeterminate).

So gcd(a,0)=a (a≠0).

Also gcd(0,0) is undefined.

 [1. The Algorithm Eventually Reaches Zero

First we note that a<b. And r1<b. Similarly, r2<r1, and rk+1<rk. Eventually, rn=0. A succession of reducing positive integers must eventually become zero. (This is an implicit use of mathematical induction). A further generality is that a succession of integers reducing in absolute value must also eventually reach zero. This means that there is always a zero remainder and the previous remainder, the gcd, is greater than zero in absolute value.

The algorithm always terminates at zero, as stated above, when a and b are finite and have a finite number of digits. Otherwise, the algorithm does not terminate.

We need to prove that the last non-zero remainder, d, is the gcd. To do this, we prove that this remainder divides a and b, and that any other divisor of a and b also divides d.

If any other divisor divides d, then d is the greatest common divisor.

The actual start of the algorithm is not determined, because a and b could be the result of some previous steps in the algorithm. We can write them as r1 and r2, with r1>=r2. If r1=r2, then the gcd is r1 (or r2). For instance, the gcd(r,r)=r, because clearly r divides itself, and cannot be divided by a greater number.

The French mathematician, Gabriel Lamé (1795-1870), showed that the greatest possible number of divisions in the algorithm is five times the number of digits in the smallest number (a or b).

The Last Non-Zero Remainder Divides The Two Initial Numbers

While it is conventional to write the first two numbers, for which we seek the gcd, as a and b, they are written below as r1 and r2, with r1>r2, both to show they are theoretically remainders from some possible previous process, and for consistency with the other remainders.
euclidProof1.gif [1.1]

The gcd, d could be written rn, because it is the nth remainder.  Looking at the last line, we note that d clearly divides rn-1. This is so because the product qn-1. d, with no remainder, so the q and d are factors of rn-1. Also, because d divides rn-1, then there is no remainder, so rn+1 is written as zero.

On the second line up, clearly d divides itself, and also rn-1, so it divides rn-2. (If one side of an equation is divisible by a number, then that number must divide the other side!)

Similarly, on the third line up, we note that d divides rn-1, and rn-2, so it divides rn-3.

For every line above, we find a similar relationship, where each of the remainders is divisible by d.

Finally, we have d|r1 and d|r2.

So d divides the first two numbers, r1 and r2.  
■
We have proved that d divides all the remainders, that is, it is a common divisor. It remains to prove that d is the greatest common divisor.

The Last Non-Zero Remainder is the GCD

Let c be any common divisor of the initial numbers, r1 and r2.
euclidProof1.gif [1.1, repeated]


By assumption, the number c divides r1 and r2. It must also divide r3, because if it did not, then one side of the first equation above would be divisible by c, but the other side would not. This would mean that r1/c, an integer would be equal to q1r2/c, an integer, plus r3/c, a fraction (because c would not divide r3). So an integer would be equal to a fraction, which is impossible. Therefore, c must also divide r3.

Similarly, for the second equation above, c divides r2 and r3, so it must also divide r4. 

By continuing in this manner, we show that c divides d in the penultimate equation above, because it divides rn-2 and rn-1, by our previous reasoning.

As c is any number, even the greatest number, that divides r1 and r2, and it also divides d, then d is the greatest common divisor of r1 and r2.

We therefore conclude that d, the last non-zero remainder, is the greatest common divisor.
■




Ken Ward's Mathematics Pages