NTIC The Greatest Common Divisor

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,$ we say that $d$ is a common divisor of $a$ and $b$ if $d ∣ a$ and $d ∣ b .$ If $d$ is the biggest such common divisor, it is called the greatest common divisor, or gcd, of $a$ and $b,$ written $d = gcd (a, b) .$

🔗

Example 2.2.2.

What are all the common divisors of 6 and 10? What is their gcd?

🔗

Remark 2.2.3.

What is the greatest common divisor of zero and zero? By definition, there is none (or it is infinity?). Some authors (such as [E.2.1]) simply don't allow this case at all; others (like [E.2.4]) define it to be zero without further comment. As for computation, both SageMath and Wolfram Alpha apparently compute it to be zero (perhaps by The Euclidean Algorithm), while one online calculator throws an error.

This text chooses to remain agnostic on this point. However, ring theory and lattice theory both allow for an alternate definition which naturally yields zero as the answer; either consult an abstract algebra text, or see all the answers to this question at Mathematics StackExchange for some good fireside reading after you do your homework for this section.

🔗

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 ∣ a$ and $d ∣ b .$ (This is Definition 2.2.1.)
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 $a x + b y$ 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, 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.