OneTaskBy Tim King · Updated
GCF Calculator
Greatest Common Factor (HCF, GCD) With Euclid's Algorithm Steps
OneTask is free, with no sign-up, and built by one person.
If this tool saved you time, a coffee helps keep new ones coming.
How the GCF Calculator works
This GCF calculator finds the greatest common factor of two or more whole numbers, also known as the highest common factor (HCF) or greatest common divisor (GCD). For two numbers it shows each step of Euclid's algorithm. It also divides each number by the GCF, says whether they are coprime and gives the least common multiple.
The greatest common factor is the largest number that divides each of your numbers exactly. It is the tool for simplifying fractions and ratios, since dividing top and bottom by the GCF gives lowest terms in one step. It also solves sharing problems, such as cutting two lengths of wood into the longest equal pieces with nothing left over. GCF, HCF and GCD are three names for the same idea.
How the GCF calculator works
The formula is Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), repeated until the remainder is 0. The last non-zero remainder is the answer. For more than two numbers the calculator folds them in one at a time, so gcd(a, b, c) = gcd(gcd(a, b), c). Big integers keep long numbers exact. The LCM then follows from a × b ÷ gcd(a, b).
First example. gcd(48, 180): 180 = 3 × 48 + 36, 48 = 1 × 36 + 12, 36 = 3 × 12 + 0, so the GCF is 12.
Second example. gcd(24, 36, 60): gcd(24, 36) = 12, then gcd(12, 60) = 12, so the GCF is 12.
How many equal pieces? Cutting 48 cm and 180 cm boards into the longest equal pieces gives 12 cm pieces: 4 from the first and 15 from the second.
Greatest common factor of common pairs, with the fraction each pair reduces to
| Numbers | GCF | Fraction | Simplified |
|---|---|---|---|
| 12, 18 | 6 | 12/18 | 2/3 |
| 8, 12 | 4 | 8/12 | 2/3 |
| 15, 25 | 5 | 15/25 | 3/5 |
| 14, 21 | 7 | 14/21 | 2/3 |
| 16, 24 | 8 | 16/24 | 2/3 |
| 18, 24 | 6 | 18/24 | 3/4 |
| 20, 30 | 10 | 20/30 | 2/3 |
| 24, 36 | 12 | 24/36 | 2/3 |
| 27, 36 | 9 | 27/36 | 3/4 |
| 30, 45 | 15 | 30/45 | 2/3 |
| 36, 48 | 12 | 36/48 | 3/4 |
| 42, 56 | 14 | 42/56 | 3/4 |
| 48, 180 | 12 | 48/180 | 4/15 |
| 54, 72 | 18 | 54/72 | 3/4 |
| 60, 84 | 12 | 60/84 | 5/7 |
| 64, 96 | 32 | 64/96 | 2/3 |
| 72, 120 | 24 | 72/120 | 3/5 |
| 81, 108 | 27 | 81/108 | 3/4 |
| 90, 150 | 30 | 90/150 | 3/5 |
| 100, 75 | 25 | 100/75 | 4/3 |
| 252, 105 | 21 | 252/105 | 12/5 |
| 1071, 462 | 21 | 1071/462 | 51/22 |
| 17, 31 | 1 | 17/31 | 17/31 |
Tips and pitfalls
- Coprime numbers have GCF 1. 8 and 15 share no factor, even though neither is prime.
- GCF is never bigger than the smallest number. If it is, recheck the working.
- Use it before the LCM. LCM(a, b) = a × b ÷ GCF(a, b) is faster than listing multiples.
- Separate with commas or spaces. Type as many numbers as you need, such as 12, 18, 30.
Sources: Greatest common divisor.
Checked against: GCF of 48 and 18 = 6
FAQ
How do you find the greatest common factor?
List each number's prime factorisation and multiply the primes they share, using the lowest power of each. For 72 = 2³ × 3² and 120 = 2³ × 3 × 5, the shared part is 2³ × 3 = 24. Euclid's algorithm gets the same answer faster for large numbers.
Is GCF the same as HCF and GCD?
Yes. Greatest common factor is common in American schools, highest common factor in British ones, and greatest common divisor in higher maths and programming. All three name the largest whole number that divides every number in the set without a remainder.
What is Euclid's algorithm?
It finds the GCF by repeated division. Divide the larger number by the smaller, keep the remainder, then divide the smaller number by that remainder, and so on. When the remainder hits 0, the last divisor is the GCF. It is over 2,000 years old and still the fastest method.
How do you use the GCF to simplify a fraction?
Divide the numerator and denominator by their GCF. For 48/180, the GCF is 12, so the fraction simplifies to 4/15 in one step. The Divided by the GCF line in the results shows the reduced numbers for any set you enter.
What does coprime mean?
Two numbers are coprime when their GCF is 1, so they share no factor except 1. 9 and 28 are coprime even though neither is prime. A fraction whose top and bottom are coprime is already in its lowest terms, so it cannot be simplified further.
See also: all Number Theory tools, Arithmetic, Algebra and Geometry, Statistics, Trigonometry and Calculus.
Related tools
LCM Calculator
Least common multiple of two or more numbers, with the working.
Factor Calculator
All the factors, factor pairs and prime factorisation of a number.
Fraction Calculator
Add, subtract, multiply and divide fractions, with the working shown.
Ratio Calculator
Simplify a ratio, split an amount in it, or scale it up.
Decimal To Fraction Calculator
Decimals to simplified fractions, recurring decimals and inch fractions included.