GCF Calculator (Greatest Common Factor)
Type two or more whole numbers to find the largest number that divides them all, with Euclid’s algorithm and the prime factors shown.
Two to 12 numbers, separated by commas or spaces.
GCF of 48, 180
12
12 is the largest number that divides 48, 180 exactly.
- GCF in primes
- 2² × 3
- LCM of the two
- 720
How to find the greatest common factor
The greatest common factor (GCF), also called the greatest common divisor (GCD) or highest common factor (HCF), is the largest whole number that divides each of the numbers exactly. For 48 and 180 it is 12: 48 = 12 × 4 and 180 = 12 × 15, and 4 and 15 share no further factor.
Euclid’s algorithm finds it with a few divisions. Divide the larger number by the smaller and keep the remainder: 180 = 3 × 48 + 36. Then divide the old divisor by the remainder: 48 = 1 × 36 + 12, and 36 = 3 × 12 + 0. When the remainder reaches 0, the last divisor (12) is the GCF. It works because any number dividing both 180 and 48 must also divide the remainder 36, and so on down.
The prime factor method gives the same answer and shows why: 48 = 2⁴ × 3 and 180 = 2² × 3² × 5. Take each prime that appears in every number, at its lowest power: 2² × 3 = 12. For three or more numbers, find the GCF of the first two, then the GCF of that with the next.
gcd(a, b) = gcd(b, a mod b), gcd(a, 0) = a
- Euclid set out this method around 300 BC, which makes it one of the oldest algorithms still in everyday use. Source: Euclid’s Elements, Book VII, Proposition 2 (D. E. Joyce’s edition).
- Consecutive Fibonacci numbers, such as 144 and 233, are the slowest pairs for Euclid’s algorithm: every quotient is 1 (Lamé, 1844). Source: Wikipedia, Euclidean algorithm.
GCF of common pairs
The greatest common factor of each pair, how many division steps Euclid’s algorithm needs, and what is left after dividing it out.
| Numbers | GCF | Euclid steps | Divided by the GCF |
|---|---|---|---|
| 12 and 18 | 6 | 2 | 2 and 3 |
| 24 and 36 | 12 | 2 | 2 and 3 |
| 48 and 180 | 12 | 3 | 4 and 15 |
| 56 and 98 | 14 | 3 | 4 and 7 |
| 84 and 126 | 42 | 2 | 2 and 3 |
| 75 and 100 | 25 | 2 | 3 and 4 |
| 270 and 192 | 6 | 4 | 45 and 32 |
| 1,071 and 462 | 21 | 3 | 51 and 22 |
| 1,001 and 770 | 77 | 3 | 13 and 10 |
| 17 and 31 | 1 | 5 | 17 and 31 |
Show all 13 rowsShow fewer
| 9 and 28 | 1 | 2 | 9 and 28 |
| 144 and 233 | 1 | 11 | 144 and 233 |
| 1,024 and 768 | 256 | 2 | 4 and 3 |
Frequently Asked Questions
Are GCF, GCD and HCF the same thing?
Yes. Greatest common factor, greatest common divisor and highest common factor are three names for the same number; GCD is common in computing and HCF in British schools.
What does a GCF of 1 mean?
The numbers are coprime (relatively prime): they share no prime factor. 8 and 15 are coprime even though neither is prime, so 8/15 cannot be simplified.
What is the GCF used for?
Simplifying fractions (divide top and bottom by the GCF), splitting things into the largest equal groups (48 pens and 180 pencils make at most 12 identical packs), and finding the LCM, since GCF × LCM = a × b for two numbers.