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
- 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
For the completeness sake, let's prove #2 directly, without invoking #1. To this end, assume that
Note that g must divide a; for, otherwise,
Note that as + bt = gcd(a, b) implies that any common divisor of a and b also divides
|Contact| |Front page| |Contents| |Generalizations| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
71491835