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:

Calculating the Greatest Common Divisor

Example 1 

	gcd(124,217)=31
n	a	b	remainder, r
1	217=	124·1+	93	Divide the larger number, a, by the smaller, b, and add the remainder, r1.
2	124=	93·1+	31	The previous b, 124, becomes the new a. Divide a by b and add the remainder, r2.
3	93=	31·3+	0	The 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
n	a	b	remainder, r
1	97=	42·2+	13	We divide a by b and add the remainder.
2	42=	13·3+	3	The 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.
3	13=	3·4+	1	We continue in the pattern established.
4	3=	1·3+	0	The 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 Remainder			Least Absolute Remainder
n	a	b	r	a	b	r
1	987=	960·1+	27	987=	960·1+	27
2	960=	27·35+	15	960=	27·35+	15
3	27=	15·1+	12	27=	15·2-	3
4	15=	12·1+	3	15=	3·5+	0
5	12=	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 r₁<b. Similarly, r₂<r₁, and r_k+1<r_k. Eventually, r_n=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 r₁ and r₂, with r₁>=r₂. If r₁=r₂, then the gcd is r₁ (or r₂). 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 r₁ and r₂, with r₁>r₂, both to show they are theoretically remainders from some possible previous process, and for consistency with the other remainders.
[1.1]

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

On the second line up, clearly d divides itself, and also r_n-1, so it divides r_n-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 r_n-1, and r_n-2, so it divides r_n-3.

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

Finally, we have d|r₁ and d|r₂.

So d divides the first two numbers, r₁ and r₂.  
■
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, r₁ and r₂.
[1.1, repeated]


By assumption, the number c divides r₁ and r₂. It must also divide r₃, 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 r₁/c, an integer would be equal to q₁r₂/c, an integer, plus r₃/c, a fraction (because c would not divide r₃). So an integer would be equal to a fraction, which is impossible. Therefore, c must also divide r₃.

Similarly, for the second equation above, c divides r₂ and r₃, so it must also divide r₄. 

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

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

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




Ken Ward's Mathematics Pages

---

---

Faster Arithmetic - by Ken Ward