The Greatest Common Divisor

You have 12 red roses and 18 white ones, and you want to tie them into identical bunches with none left over. The biggest number of bunches you can make — and the size of each — is a greatest-common-divisor question. The very same idea is what lets you reduce a fraction like \tfrac{12}{18} to its simplest form.

Take two whole numbers. Some numbers divide both of them — these are their common divisors (you might also hear "common factors"). The largest of those is the greatest common divisor, written \gcd(a, b) and sometimes called the highest common factor. 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.

Put plainly: the greatest common divisor is the biggest number that divides both of your numbers exactly — with nothing left over. "Exactly" is the whole game: a number only counts if it goes into both with no remainder.

From a list of divisors

The most direct way to see it: list the divisors of each number, then 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 of those is 6. So \gcd(12, 18) = 6. Notice the recipe has three small steps: list, find the shared ones, pick the largest.

Two more worked examples

Once you have the recipe, every pair works the same way.

Example 1. \gcd(8, 12):

\begin{aligned} 8 &: \ 1,\ 2,\ 4,\ 8 \\ 12 &: \ 1,\ 2,\ 3,\ 4,\ 6,\ 12 \end{aligned}

Shared: 1, 2, 4. The largest is 4, so \gcd(8, 12) = 4.

Example 2. \gcd(16, 24):

\begin{aligned} 16 &: \ 1,\ 2,\ 4,\ 8,\ 16 \\ 24 &: \ 1,\ 2,\ 3,\ 4,\ 6,\ 8,\ 12,\ 24 \end{aligned}

Shared: 1, 2, 4, 8. The largest is 8, so \gcd(16, 24) = 8.

The number you want must divide BOTH — it is the largest common factor, not the largest factor of either number on its own.

\gcd(8, 12) is 4, not 12. True, 12 is the biggest factor of 12 — but it does not divide 8, so it is not common.
The answer can never be bigger than the smaller of your two numbers, because it has to fit into that one too.
1 is always a common divisor, so the list of shared factors is never empty.

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.

See it: shared factors lit up

Here are the factor lists of two numbers, one row each. The tiles they have in common are filled in, and the greatest shared one wears a ring — that ring is the gcd. Press Refresh for a brand-new pair and watch where the ring lands.

Where this shows up

You have 12 cookies and 18 strawberries, and you want to fill as many identical party bags as possible — every bag the same, with whole snacks and nothing left over.

cookie cookie cookie strawberry

The number of bags has to divide both 12 and 18, so the most bags you can make is \gcd(12, 18) = 6. Each bag then holds 2 cookies and 3 strawberries. The gcd is the answer to "how many equal groups?"

A teacher lines up 8 ducks and 12 frogs. She wants both lined into rows of the same length, the longest rows possible, with no animal sticking out.

duck duck duck duck frog frog frog frog

The row length must divide both 8 and 12, so the longest equal rows hold \gcd(8, 12) = 4 animals each — giving 2 rows of ducks and 3 rows of frogs. Same idea, whether you are cutting two ribbons into the biggest equal pieces or laying tiles along two walls.

Simplifying fractions

The most everyday use of the gcd is putting a fraction in its lowest terms. Divide the top and the bottom by their greatest common divisor and the fraction shrinks to its simplest shape in one step. Take \tfrac{18}{24}:

\gcd(18, 24) = 6, \qquad \frac{18}{24} = \frac{18 \div 6}{24 \div 6} = \frac{3}{4}.

Because we divided by the greatest common divisor, the new top and bottom share no factor any more — the fraction cannot be simplified further. (If you only spotted a smaller common factor, say 2, you would get \tfrac{9}{12} and have to keep going. The gcd finishes the job in one move.)

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.