algorithm (or algorism) is a method of computing the greatest common
divisor (gcd) of two numbers. It is very important in number theory and
The Greatest Common Divisor
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
Divide the larger number, a, by the smaller, b, and add the remainder, r1.
The previous b, 124, becomes the new a. Divide a by b and add the remainder, r2.
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.
We divide a by b and add the remainder.
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.
We continue in the pattern established.
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
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.
Least Positive Remainder
Least Absolute Remainder
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).
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).
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
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.
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. [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. [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. ■