## Sunday, May 18, 2008

### What is Mathematics: GCD

This is the third in the series of posts on the book What is Mathematics. This post is about the the Greatest Common Denominator (GCD) of a pair of numbers.

The GCD of a pair of positive integers a and b (denoted here as gcd(a, b)) is simply the largest positive integer that divides both a and b. The Euclidean algorithm is a simple way to compute the GCD. The Euclidean algorithm is based on the observation that for any positive integers a and b there exist integers q and r with 0 ≤ r < b such that

a = b × q + r

Note that r is simply the remainder when you divide a by b. From this it is easy to show that u is a common divisor of a and b if and only if u is a common divisor of b and r. Since the set of common divisors are identical, it follows that the greatest common divisors are also identical, i.e.,

gcd(a, b) = gcd(b, r)

To get the Euclidean algorithm, one simply applies the above result recursively to gcd(b, r) until we get to rn-1 and rn such that gcd(rn-1, rn) = 0. When this happens, we can conclude that gcd(a, b) = rn. (We would, of course, use mathematical induction to prove this formally.)

One important property of gcd(a, b) that can be derived from the above is that there exist positive or negative integers k and l such that

gcd(a, b) = k × a + l × b

Using this, the book presents a simple proof of the fundamental theorem of arithmetic. The proof starts by using the above property to show that if a prime p divides a × b then it divides either a or b. One can then easily show that purportedly different prime factorizations of a number are in fact identical.

Finally, the book introduces Euler's function. Two integers a and b are said to be relatively prime if

gcd(a, b) = 1

Euler's function, usually denoted φ(n), is the number of integers from 1 to n that are relatively prime with n. Note, in particular, φ(1) = 1 and φ(p) = p - 1 when p is prime. The book claims that Euler's function is a number-theoretical function of great importance (though it does not expand on this claim immediately).

One interesting property of Euler's function is the generalization of Fermat's little theorem: if n is any integer and a is relatively prime with n then

aφ(n) ≡ 1 (mod n)