It seems intuitive that of all the numbers dividing a number (the divisors), one is biggest.
If we consider the various divisors of two numbers \(a\) and \(b\), we say that \(d\) is a common divisor of \(a\) and \(b\) if \(d\mid a\) and \(d\mid 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 all the common divisors of 6 and 10? What is the gcd?
We now come to a great definition-theorem.
The greatest common divisor (GCD or gcd) of two integers \(a\) and \(b\) (not both zero) is:
The largest integer \(d\) such that \(d|a\) and \(d|b\). (See above.)
The number achieved by applying the Euclidean algorithm (a repeated division algorithm) to \(a\) and \(b\). (See Section 2.3.)
The smallest positive number which can be written as \(ax+by\) for some integers \(x\) and \(y\). (See Section 2.4 and Subsection 2.4.2.)
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.
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.
