The Euclidean Algorithm: The Fastest Way to Find the GCF
How Euclid's division method finds the greatest common factor of large numbers in a few steps, why it works, and how to extend it to three or more numbers.
Listing factors is fine for small numbers, and prime factorization works for medium ones. But try finding the GCF of 1,071 and 462 that way and you'll be at it for a while. The Euclidean algorithm, described by the Greek mathematician Euclid more than 2,000 years ago, solves it in three lines.
The method
- Divide the larger number by the smaller and note the remainder.
- Replace the larger number with the smaller, and the smaller with the remainder.
- Repeat until the remainder is 0.
- The last non-zero remainder is the GCF.
Worked example: GCF(1071, 462)
| Step | Division | Remainder |
|---|---|---|
| 1 | 1071 = 462 × 2 + 147 | 147 |
| 2 | 462 = 147 × 3 + 21 | 21 |
| 3 | 147 = 21 × 7 + 0 | 0 |
The last non-zero remainder is 21, so GCF(1071, 462) = 21. You can check: 1071 = 21 × 51 and 462 = 21 × 22, and 51 and 22 share no common factor.
Why it works
Any number that divides both a and b also divides a − b, and therefore also divides the remainder when a is divided by b (which is a minus some multiple of b). So the pair (a, b) and the pair (b, remainder) have exactly the same common factors, and therefore the same greatest one. Each step makes the numbers smaller, so the process must end, and when the remainder is 0, the last divisor divides everything above it.
Another example: GCF(252, 105)
- 252 = 105 × 2 + 42
- 105 = 42 × 2 + 21
- 42 = 21 × 2 + 0
GCF = 21. Enter two numbers in the GCF calculator and it prints these steps for you.
Three or more numbers
Apply the algorithm to the first two numbers, then to that result and the next number, and so on: GCF(a, b, c) = GCF(GCF(a, b), c). For 84, 126 and 210: GCF(84, 126) = 42, and GCF(42, 210) = 42.
The subtraction version
Euclid's original form used repeated subtraction: subtract the smaller number from the larger until they're equal. It gives the same answer but can take many more steps. Using division (the remainder) jumps straight to the result of many subtractions at once.
How fast is it?
Very. The number of steps grows only with the number of digits, not with the size of the numbers. Even for numbers in the billions, it rarely takes more than a few dozen divisions. That's why computers use it, and why it sits at the heart of the RSA encryption used to secure websites, which relies on related calculations with numbers hundreds of digits long.
Finding the LCM afterwards
For two numbers, LCM = (a × b) ÷ GCF. For 1071 and 462: 1071 × 462 ÷ 21 = 23,562. Read more in GCF vs. LCM.
Practice
Find GCF(391, 299). Steps: 391 = 299 × 1 + 92; 299 = 92 × 3 + 23; 92 = 23 × 4 + 0. The answer is 23. For another method that also explains why numbers share factors, see prime factorization.
Further reading from official sources
- Factors and multiples (Grade 6 math) – Khan Academy
