Section2.2The GCD

It seems intuitive (though see the exercises) that of all the numbers dividing a number (the divisors), one is biggest. If we now consider the set of divisors two numbers \(a\) and \(b\), we say that \(d\) is a common divisor if \(d|a\) and \(d|b\).

If \(d\) is the biggest such common divisor, it is called the greatest common divisor, or gcd, written \(d=gcd(a,b)\). What are the common divisors of 6 and 10? What is the gcd?

We now come to a great definition-theorem.

Theorem2.2.1

The greatest common divisor of two integers \(a\) and \(b\) is:

The largest integer \(d\) such that \(d|a\) and \(d|b\).
The number achieved by applying the Euclidean algorithm (a repeated division algorithm) to \(a\) and \(b\). (See below 2.3.)
The smallest positive number which can be written as \(ax+by\) for some integers \(x\) and \(y\).

This is amazing, and the first real indication of the power of having multiple perspectives on a problem. It means that the very theoretical issue of when a GCD exists (and finding it) can be treated as a purely computational problem, characterized completely independent of actually finding divisors. And further, there is a definition purely in terms of addition and multiplication, not division or subtraction.

So if you need to actually calculate a GCD, you use the algorithm. If you want to prove something about it that has to do with dividing, you use the original definition. And if you need to prove something about it where division is hard to use, you use the third characterization. This sort of idea will come up again and again in this book - that having multiple ways to define something really helps.