How to Find the Greatest Common Factor
In The Art of Computer Programming, computer scientist Donald Knuth called Euclid's method for finding the greatest common factor "the granddaddy of all algorithms," because it's the oldest nontrivial algorithm that has survived to the present day.
It appeared in Euclid's Elements around 300 BC. Today, the same few lines of logic run inside the software that secures internet connections. And for everyday math, like simplifying fractions or cutting materials into equal pieces, it's often the fastest method of all.
You Don't Need Any Factors to Find the Greatest Common Factor
The name suggests you must list or find factors. The fastest method doesn't. Euclid's algorithm uses only division with remainders, and it works even for enormous numbers whose factors nobody could find.
What Is the GCF?
The greatest common factor (GCF), also called the greatest common divisor (GCD) or highest common factor, is the largest whole number that divides two or more numbers without a remainder.
For 12 and 18:
- Factors of 12: 1, 2, 3, 4, 6, 12
- Factors of 18: 1, 2, 3, 6, 9, 18
Common factors: 1, 2, 3, 6. The greatest is 6.
Method 1: List the Factors
Best for small numbers.
Example: GCF of 24 and 36
24: 1, 2, 3, 4, 6, 8, 12, 24
36: 1, 2, 3, 4, 6, 9, 12, 18, 36
The largest shared factor is 12.
Method 2: Prime Factorization
Best for medium numbers or several numbers at once.
- Write each number as a product of primes.
- Take each prime that appears in all of them, with the lowest exponent.
- Multiply.
Example: GCF of 48 and 180
48 = 2⁴ × 3
180 = 2² × 3² × 5
Shared primes: 2 (lowest power 2²) and 3 (lowest power 3¹). The 5 isn't shared.
GCF = 2² × 3 = 12
Find factorizations with the prime factorization tool. See How to Find Prime Factors.
Method 3: Euclid's Algorithm
Best for large numbers.
The rule: the GCF of two numbers is the same as the GCF of the smaller number and the remainder when you divide the larger by the smaller. Repeat until the remainder is 0. The last non-zero remainder is the GCF.
gcd(a, b) = gcd(b, a mod b)
Example: GCF of 252 and 105
| Step | Division | Remainder |
|---|---|---|
| 1 | 252 ÷ 105 = 2 remainder 42 | 42 |
| 2 | 105 ÷ 42 = 2 remainder 21 | 21 |
| 3 | 42 ÷ 21 = 2 remainder 0 | 0 |
GCF = 21.
Why it works: any number dividing both 252 and 105 also divides 252 − 2 × 105 = 42. So the pair (105, 42) has exactly the same common factors as (252, 105). Each step shrinks the numbers while preserving the answer. Try it with the GCF calculator.
An Insider Reference: Lamé's Bound
How many steps can Euclid's algorithm take? In 1844, French mathematician Gabriel Lamé proved it never needs more than five times the number of digits in the smaller number. For two 100-digit numbers, that's at most 500 steps, trivial for a computer.
The slowest case occurs with consecutive Fibonacci numbers, like 89 and 55, where every quotient is 1. Lamé's result is often described as one of the first analyses of an algorithm's efficiency. See The Mathematics of Algorithms.
Everyday Uses of the GCF
Simplifying Fractions
Divide the numerator and denominator by their GCF:
48/180 → GCF 12 → 4/15
Dividing Into Equal Groups
You have 48 red and 180 blue marbles and want identical bags with no leftovers. The largest number of bags is the GCF, 12, with 4 red and 15 blue in each.
Cutting Materials
Two boards, 252 cm and 105 cm, must be cut into equal pieces as long as possible. The longest piece is 21 cm.
Tiling
The largest square tile that exactly covers a 48 × 180 cm area without cutting is 12 cm. See Real-Life Uses of LCM and GCF.
Two Concepts Worth Knowing
Relatively Prime
Two numbers are relatively prime (or coprime) if their GCF is 1, like 8 and 15. They share no prime factors. Coprime numbers are essential in RSA encryption.
GCF and LCM Together
For any two positive integers:
GCF(a, b) × LCM(a, b) = a × b
For 12 and 18: 6 × 36 = 216 = 12 × 18. So once you know the GCF, the LCM is one division away. See How to Find the Least Common Multiple.
Quick Answer: How Do You Find the Greatest Common Factor?
For small numbers, list the factors of each and pick the largest shared one. For larger numbers, write each as a product of primes and multiply the shared primes using their lowest powers. For very large numbers, use Euclid's algorithm: repeatedly replace the larger number with the remainder of dividing it by the smaller until the remainder is 0.
Try Them Yourself
- GCF Calculator: find the GCF of any numbers
- LCM Calculator: the partner calculation
- Prime Factorization Tool: factor numbers for Method 2
- Division Tables: quotients and remainders for Euclid's algorithm
- Number Theory Formulas: divisibility rules and identities
- Euclid and the Birth of Mathematical Proof: where the algorithm came from
Use Euclid's algorithm to find the GCF of 1,071 and 462. Count your steps, then check the answer with the GCF calculator.