# 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 the 3 Glass and Hour Glass problems we used the following property of gcd:

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

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

It's not by accident or magic that gcd(*a*, *b*) is representable in the form *as* + *bt*.

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

Note that *g* must divide *a*; for, otherwise, *a* = *gu* + *r**u* and *r*, *r* < *g*.*r* = *a* - *ug* = (1 - *us*)*a* - *utb*.*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, *g* ≤ gcd(*a*, *b*)*g* = gcd(*a*, *b*).

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

|Contact| |Front page| |Contents| |Generalizations| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

65001711 |