MISSION · Number sense
The Euclidean Algorithm
Divide, keep the remainder, repeat — the oldest algorithm still in use
LEVEL 1 · EXPLORE
Make the idea move
Change the controls and watch what happens. Follow your curiosity and see what you notice.
Loading the activity…
LEVEL 2 · LEARN
Unlock the explanation
Open the chapters in any order. Try the examples as you go.
The idea in one sentence
Any number dividing both \(a\) and \(b\) also divides their remainder, so you can keep replacing the pair with a smaller pair until the answer is staring at you.
The method
To find \(\gcd(48, 18)\), divide and keep only the remainder. Then divide the old divisor by that remainder. Repeat.
\(48 = 2 \times 18 + \mathbf{12}\) \(18 = 1 \times 12 + \mathbf{6}\) \(12 = 2 \times 6 + \mathbf{0}\)
Stop when the remainder hits zero. The last non-zero remainder is the gcd, so \(\gcd(48, 18) = 6\).
Three lines, no factorising, and the same three lines work whatever the numbers are.
Why it works
The key fact is one line long:
\[\gcd(a, b) = \gcd(b, \; a \bmod b)\]Suppose \(d\) divides both \(a\) and \(b\). Write \(a = qb + r\). Then \(r = a - qb\), and \(d\) divides both terms on the right, so \(d\) divides \(r\) too.
The argument runs backwards just as well: anything dividing \(b\) and \(r\) divides \(qb + r = a\). So the pair \((a, b)\) and the pair \((b, r)\) have exactly the same common divisors — not merely overlapping ones. Their greatest common divisor is therefore the same number.
Each step shrinks the pair, remainders cannot go below zero, so the process must stop. And \(\gcd(x, 0) = x\), because everything divides 0.
Why not just factorise?
Prime factorisation also finds a gcd, and for small numbers it is perfectly good. It falls apart as the numbers grow.
Try \(\gcd(1071, 462)\) by factorising and you must first break both into primes. By the algorithm:
\(1071 = 2 \times 462 + 147\) \(462 = 3 \times 147 + 21\) \(147 = 7 \times 21 + 0\)
Three lines again, and the answer is 21.
The gap widens brutally. Factorising a 600-digit number is beyond every computer on earth; running the Euclidean algorithm on two of them takes well under a second. That asymmetry — easy to find a gcd, hard to factorise — is not a curiosity. RSA encryption is built on exactly it, and the algorithm runs inside the key generation.
It is roughly 2300 years old, appearing in Euclid’s Elements around 300 BC, and it is still the method actually used. Very little else in mathematics has that record.
Coprime numbers
If the algorithm ends with a gcd of 1, the two numbers share no factor beyond 1 and are called coprime or relatively prime.
\(\gcd(8, 15) = 1\), even though neither is prime. Being coprime is a property of the pair, not of either number.
This is exactly the condition for a fraction to be in lowest terms, and it is what the algorithm is doing when a computer simplifies \(\frac{48}{18}\) to \(\frac{8}{3}\): one division by the gcd, found in three steps.
Common mix-ups
- Reporting the last remainder instead of the last non-zero one. The final remainder is always 0, which is never the answer.
- Stopping early. Carry on until a remainder of 0 appears.
- Keeping the quotient. Only the remainders matter; the quotients are discarded.
- Starting with the smaller number first. It is harmless — \(\gcd(18, 48)\) makes the first step \(18 = 0 \times 48 + 18\), which simply swaps them — but it wastes a line.
- Confusing gcd with lcm. Once you have one, the other follows from \(\gcd \times \text{lcm} = ab\).
Check yourself
Finish \(48 = 2\times18 + 12\), \(18 = 1\times12 + 6\), \(12 = 2\times6 + 0\). What remainder stops the algorithm, and what is \(\gcd(1071, 462)\)?
The last non-zero remainder is 6, so \(\gcd(48,18) = 6\). The algorithm stops at a remainder of 0. And \(1071, 462 \to 147 \to 21 \to 0\), so the answer is 21.
LEVEL 3 · REFLECT
Add this quest to your trail
When you feel ready, mark this idea as explored. You can always come back and try it again.
EXPLORER STRATEGIES