The Greatest Common Divisor
Take two whole numbers. Some numbers divide both of them — these are their
common divisors. The largest of those is the
greatest common divisor, written \gcd(a, b). It
measures exactly how much arithmetic the two numbers share, and it turns out to be
one of the most useful quantities in all of number theory.
From a list of divisors
The most direct way to see it: list the
divisors
of each number and look for the biggest one they have in common. For
12 and 18:
\begin{aligned} 12 &: \ 1,\ 2,\ 3,\ 4,\ 6,\ 12 \\ 18 &: \ 1,\ 2,\ 3,\ 6,\ 9,\ 18 \end{aligned}
The shared divisors are 1, 2, 3, 6, and the greatest is
6. So \gcd(12, 18) = 6.
From prime factorisations
Prime factorisation
gives a cleaner recipe: write each number as a product of primes, then for each prime take the
smaller power that appears in both.
12 = 2^2 \cdot 3, \qquad 18 = 2 \cdot 3^2
\gcd(12,18) = 2^{\min(2,1)} \cdot 3^{\min(1,2)} = 2^1 \cdot 3^1 = 6.
Whatever a prime contributes to the gcd is limited by whichever number is "stingier" with it.
This is beautiful and exact — but factorising large numbers is slow, which is why the next page
introduces a far faster route.
Coprime numbers
When two numbers share no prime at all, their only common divisor is
1:
\gcd(a, b) = 1.
We call such numbers coprime (or relatively prime). For example
8 = 2^3 and 15 = 3 \cdot 5 are coprime even
though neither is itself prime. Coprimality — not primality — is the condition that will matter
again and again, from fractions in lowest terms to
modular inverses.