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).

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, r_{1}. |

2 | 124= | 93·1+ | 31 | The previous b, 124, becomes the new a. Divide a by b and add the remainder, r_{2}. |

3 | 93= | 31·3+ | 0 | The new a is the old b, 93, and the new b is the old reminder, r_{2}. Divide a by b and add the remainder, r_{3}. The remainder is 0, so the gcd is the previous non-zero remainder (r_{2}). |

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, r_{1}, becomes the new b, and we divide as before, adding the new remainder, r_{2}. |

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, r_{3}, is the gcd. In this case, it is 1, so the numbers are relatively prime. |

The remainders always become smaller and eventually become zero.

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!

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

Also gcd(0,0) is undefined.

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

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).

[1.1]

The gcd, d could be written r

On the second line up, clearly d divides itself, and also r

Similarly, on the third line up, we note that d divides r

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

Finally, we have d|r

So d divides the first two numbers, 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.

[1.1, repeated]

By assumption, the number c divides r

Similarly, for the second equation above, c divides r

By continuing in this manner, we show that c divides d in the penultimate equation above, because it divides r

As c is any number, even the greatest number, that divides r

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

■

Ken Ward's Mathematics Pages

No script follows:

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle: