Two properties of Greatest Common Divisor

Greatest Common Divisor is one of the best known arithmetic notions. It's also one of the most common and useful tools in arithmetic. In 3 Glass and Hour Glass problems we used the following property of gcd:

1. For every pair of whole numbers a and b there exist two integers s and t such that as + bt = gcd(a,b).

The fact is a byproduct of the Euclid's Algorithm. However, when one hears it the first time, the reaction is often that of disbelief. Why? gcd? Of all things! The following statement (which is implied by the first one) asserts the central role played by gcd among linear combinations as + bt.

2. gcd(a,b) is the least positive integer representable in the form as + bt. All the rest are multiples of gcd(a,b).

It's not by accident or magic that gcd(a,b) is representable in the form as + bt. In all seriousness, if not gcd - nothing else would. Obviously, #1 follows from #2 which generalizes #1 by actually specializing the assertion.

For the completeness sake, let's prove #2 directly, without invoking #1. To this end, assume that g = as + bt is the least positive linear combination of a and b. Since a linear combination of a and b is divisible by any of their common factors (gcd(a,b), in particular), gcd(a,b)|g and, hence, gcd(a,b)g.

Note that g must divide a; for, otherwise, a = gu + r for some integers u and r, 0r<g. This would give r = a - ug = (1 - us) - utb. In other words, r, an integer smaller than g, would also be representable as a linear combination of a and b which would contradict our assumption that g is the least such integer. Therefore, g|a. Similarly, g|b. Since, g is a common divisor of a and b, we get, by definition, ggcd(a,b) which, combined with the opposite inequality obtained previously, implies that the two are indeed equal: g = gcd(a,b). QED.

Note that as + bt = gcd(a,b) implies that any common divisor of a and b also divide gcd(a,b).

Copyright © 1996-2008 Alexander Bogomolny