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.
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 Example 1
GCF(48, 18)
| 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
GCF(252, 105)
| 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
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.
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.
- Far faster than listing factors for large numbers.
- Once GCF is found, use LCM = (a × b) ÷ GCF.
Practice Questions
- Find GCF(84, 36) using the Euclidean algorithm.
- Find GCF(100, 75) step by step.
- Find GCF(1,071, 462).
- Use the result to find LCM(84, 36).
- Two numbers have GCF 14. One is 98. Find LCM using the Euclidean result.