Factors, Multiples & Primes
The Euclidean Algorithm – The Fastest Way to Find the GCF
The Euclidean Algorithm is a method for finding the GCF of two numbers that was described by the Greek mathematician Euclid around 300 BC. It remains one of the most efficient algorithms in all of mathematics, even for very large numbers.
Historians of mathematics often call this the oldest nontrivial algorithm still in everyday use — the Greeks themselves called the underlying idea anthyphairesis (“reciprocal subtraction”), and it appears in Book VII of Euclid’s Elements essentially unchanged from the version taught today. Donald Knuth, one of the founders of modern computer science, went so far as to call it “the granddaddy of all algorithms” in his classic textbook The Art of Computer Programming, because it is also one of the earliest known examples of a precisely specified, guaranteed-to-terminate step-by-step procedure — the very definition of what an algorithm is.
The Core Idea
GCF(a, b) = GCF(b, a mod b), where “mod” means the remainder when a is divided by b. Repeat until the remainder is 0. The GCF is the last non-zero remainder.
Step by Step: Applying the Algorithm
- Divide the larger number by the smaller number, and find the remainder.
- Replace the larger number with the smaller number, and replace the smaller number with that remainder.
- Repeat step 1 on the new pair.
- Stop as soon as the remainder is 0. The GCF is whatever the smaller number was on that final step — in other words, the last non-zero remainder you calculated.
Step-by-Step Example 1
| Step | Division | Remainder |
|---|---|---|
| 1 | 48 ÷ 18 = 2 remainder 12 | 12 |
| 2 | 18 ÷ 12 = 1 remainder 6 | 6 |
| 3 | 12 ÷ 6 = 2 remainder 0 | 0 — stop |
GCF(48,18) = 6
Step-by-Step Example 2
| Step | Division | Remainder |
|---|---|---|
| 1 | 252 ÷ 105 = 2 r 42 | 42 |
| 2 | 105 ÷ 42 = 2 r 21 | 21 |
| 3 | 42 ÷ 21 = 2 r 0 | 0 — stop |
GCF(252,105) = 21
More Examples, Including Two Special Cases
| Step | Division | Remainder |
|---|---|---|
| 1 | 45 ÷ 15 = 3 remainder 0 | 0 — stop |
GCF(45,15) = 15
When the smaller number already divides the larger one exactly, the algorithm finishes in a single step — the smaller number itself is the GCF.
| Step | Division | Remainder |
|---|---|---|
| 1 | 17 ÷ 5 = 3 remainder 2 | 2 |
| 2 | 5 ÷ 2 = 2 remainder 1 | 1 |
| 3 | 2 ÷ 1 = 2 remainder 0 | 0 — stop |
GCF(17,5) = 1
A GCF of 1 means the two numbers are coprime — they share no common factor at all beyond 1. The algorithm handles this exactly the same way as any other case; it just happens to land on 1 as the final non-zero remainder.
| Step | Division | Remainder |
|---|---|---|
| 1 | 1071 ÷ 462 = 2 remainder 147 | 147 |
| 2 | 462 ÷ 147 = 3 remainder 21 | 21 |
| 3 | 147 ÷ 21 = 7 remainder 0 | 0 — stop |
GCF(1071,462) = 21
Just three divisions solved a problem that would need listing dozens of factors of 1071 and 462, or fully factoring both into primes, to solve any other way.
Why It Works
If d divides both a and b, it also divides their difference a − b, and any remainder when a is divided by b. So the set of common divisors of (a, b) is identical to that of (b, remainder). We keep reducing until one number is 0, leaving the GCF.
How Fast Is It, Really?
The Euclidean Algorithm isn’t just fast in practice — how fast it is has actually been proven mathematically. A 19th-century result known as Lamé’s theorem shows that the number of division steps needed is never more than about five times the number of digits in the smaller number. A pair of 100-digit numbers, however enormous, will always finish in well under 500 steps — which is instant for a computer, and entirely manageable by hand.
The numbers that force the most steps for their size, it turns out, are consecutive Fibonacci numbers — a beautiful, unexpected link between two completely different areas of mathematics.
| Step | Division | Remainder |
|---|---|---|
| 1 | 13 ÷ 8 = 1 remainder 5 | 5 |
| 2 | 8 ÷ 5 = 1 remainder 3 | 3 |
| 3 | 5 ÷ 3 = 1 remainder 2 | 2 |
| 4 | 3 ÷ 2 = 1 remainder 1 | 1 |
| 5 | 2 ÷ 1 = 2 remainder 0 | 0 — stop |
GCF(13,8) = 1 — but it took 5 whole steps to get there, far more than the earlier examples used on numbers of similar or even larger size. 13 and 8 are consecutive Fibonacci numbers (…3, 5, 8, 13, 21…), and every consecutive Fibonacci pair behaves this way — each step’s quotient is always exactly 1, which is precisely what makes the algorithm take as many steps as possible.
Key Takeaways
- Divide the larger by the smaller; take the remainder.
- Replace the larger with the smaller and the smaller with the remainder.
- Repeat until the remainder is 0; the GCF is the last non-zero remainder.
- If the smaller number divides the larger exactly, the algorithm finishes in one step.
- A final GCF of 1 means the two numbers are coprime.
- Far faster than listing factors for large numbers — Lamé’s theorem guarantees it never takes more than about five times the digit-count of the smaller number.
- Once GCF is found, use LCM = (a × b) ÷ GCF.