Section 2.2 The Greatest Common Divisor
It seems intuitive that of all the numbers dividing a number (the divisors of the number), one is biggest. We can carry that idea to two numbers.
Definition 2.2.1. Common Divisors.
If we consider the various divisors of two numbers \(a\) and \(b\text{,}\) we say that \(d\) is a common divisor of \(a\) and \(b\) if \(d\mid a\) and \(d\mid b\text{.}\) If \(d\) is the biggest such common divisor, it is called the greatest common divisor, or gcd, of \(a\) and \(b\text{,}\) written \(d=\gcd(a,b)\text{.}\)
Example 2.2.2.
What are all the common divisors of 6 and 10? What is their gcd?
We now come to a great definition-theorem.
Theorem 2.2.4. Characterizing the greatest common divisor.
Let \(a\) and \(b\) be integers, not both zero. Then the greatest common divisor of \(a\) and \(b\) is all of the following:
The largest integer
\(d\) such that
\(d\mid a\) and
\(d\mid b\text{.}\) (This is
Definition 2.2.1.)
The number achieved by applying the Euclidean algorithm (a repeated division algorithm) to
\(a\) and
\(b\text{.}\) (See
Section 2.3.)
The smallest positive number which can be written as
\(ax+by\) for some integers
\(x\) and
\(y\text{.}\) (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, completely independent of finding divisors in the usual sense. And further, there is a definition purely in terms of addition and multiplication, nothing more complex.
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.
sagecell.sagemath.org/?z=eJxLT07RMNAx0AQACuICDA==
www.wolframalpha.com/input/?i=gcd(0,0)
math.stackexchange.com/questions/495119/what-is-gcd0-0
