Greatest Common Factor Calculator (GCF, HCF, GCD)
Enter two to six whole numbers. You will see their greatest common factor, the Euclid's algorithm steps, the prime factor method, all the common factors, and the fraction in lowest terms.
Last reviewed
Greatest common factor of 48, 180
12
2² × 3
- Common factors
- 1, 2, 3, 4, 6, 12
- Coprime?
- no
- 48/180 in lowest terms
- 4/15
Euclid's algorithm for 180 and 48
- 180 = 3 × 48 + 36
- 48 = 1 × 36 + 12
- 36 = 3 × 12 + 0
The last divisor with a remainder of 0 is 12.
By prime factors
- 48 = 2⁴ × 3
- 180 = 2² × 3² × 5
Primes shared by all, to the lowest power: 2² × 3.
The greatest common factor is also called the highest common factor or greatest common divisor. Dividing two numbers by it reduces their fraction to lowest terms.
What the greatest common factor is
The greatest common factor (GCF) of two or more whole numbers is the largest whole number that divides every one of them exactly. It goes by other names: the highest common factor (HCF) in British usage, and the greatest common divisor (GCD) in number theory and in computing. They are the same thing.
For 48 and 18, the factors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24, 48 and the factors of 18 are 1, 2, 3, 6, 9, 18. The common ones are 1, 2, 3 and 6, and the greatest is 6.
Method 1: Euclid’s algorithm
Listing factors is slow for big numbers. Euclid’s algorithm, written down over two thousand years ago, finds the GCF without factoring anything. The idea is that the GCF of a and b is the same as the GCF of b and the remainder when a is divided by b.
- Divide the larger number by the smaller and note the remainder.
- Replace the larger number by the smaller, and the smaller by the remainder.
- Repeat until the remainder is 0. The last divisor is the GCF.
48 and 18:
| Step | Division | Remainder |
|---|---|---|
| 1 | 48 = 2 × 18 + 12 | 12 |
| 2 | 18 = 1 × 12 + 6 | 6 |
| 3 | 12 = 2 × 6 + 0 | 0 |
The last non-zero remainder, and the last divisor, is 6.
1,071 and 462: 1,071 = 2 × 462 + 147; 462 = 3 × 147 + 21; 147 = 7 × 21 + 0. The GCF is 21. This pair is the usual textbook example, and it takes three steps. The algorithm is fast: the number of steps grows only with the number of digits, so even a quadrillion takes under a hundred.
Method 2: prime factors
Write each number as a product of primes (use the prime factorization calculator), then multiply the primes that appear in all the numbers, each to the lowest power it has.
- 48 = 2⁴ × 3
- 18 = 2 × 3²
- Shared: 2 (lowest power 2¹) and 3 (lowest power 3¹). GCF = 2 × 3 = 6.
Another pair: 360 = 2³ × 3² × 5 and 84 = 2² × 3 × 7. Shared primes are 2 and 3, to the powers 2 and 1, so the GCF is 2² × 3 = 12. The page shows both methods side by side so you can check one against the other.
More than two numbers
Find the GCF of the first two, then of that answer and the third, and so on. For 12, 18 and 24: GCF(12, 18) = 6, and GCF(6, 24) = 6, so the GCF is 6. The page shows the Euclid steps for every pair along the way. Note that three numbers can have a GCF of 1 even when each pair shares a factor: 6, 10 and 15 have GCF 1, though 6 and 10 share 2, 10 and 15 share 5, and 6 and 15 share 3.
Uses of the GCF
- Simplifying fractions. Divide the top and bottom by their GCF to get lowest terms. 48/18 has GCF 6, so it is 8/3. The page does this for two numbers.
- Dividing things into equal groups. 48 apples and 18 oranges can be shared into at most 6 identical baskets, each with 8 apples and 3 oranges.
- Tiling and cutting. The largest square tile that fits a 48 by 18 unit floor exactly has side 6.
- Ratios. The GCF reduces a ratio such as 48:18 to 8:3. See the proportion calculator.
Coprime numbers
If the GCF is 1 the numbers are coprime (or relatively prime): their only shared factor is 1. 17 and 5 are coprime, and so are 8 and 15, which are not themselves prime. A fraction whose numerator and denominator are coprime is already in lowest terms.
GCF and LCM
The GCF and the least common multiple are linked. For two numbers, GCF × LCM = a × b. For 48 and 18: 6 × 144 = 864 = 48 × 18. So once you have the GCF, the LCM is a × b ÷ GCF. The least common multiple calculator uses this.
Common mistakes
- Mixing up GCF and LCM. The GCF is a number that goes into both (and is no larger than the smaller). The LCM is a number both go into (and is no smaller than the larger).
- Taking the highest power of shared primes. For the GCF take the lowest.
- Missing that 1 is always a common factor. If nothing else is shared, the GCF is 1, not “none”.
- Stopping Euclid’s algorithm one step early. The answer is the last divisor, before the remainder 0.
- Using decimals. The GCF is for whole numbers. Convert a decimal to a fraction first.
Related calculators
- Least common multiple calculator.
- Factor calculator and prime factorization calculator.
- Common factor calculator, which also gives the LCM and every common factor.
- Fraction calculator and proportion calculator.
How it is calculated
The numbers are read as exact whole numbers. Euclid’s algorithm is applied to the first two, and then to that result and each further number, recording every division. Separately, each number is split into prime powers by trial division, and the primes common to all are taken to their lowest exponent. The two methods give the same value, and the common factors are the factors of the GCF. For two numbers the fraction is divided top and bottom by the GCF.
Frequently asked questions
What is the greatest common factor?
The largest whole number that divides every number in a set exactly. The GCF of 48 and 18 is 6, because 6 divides both and nothing larger does. It is also called the highest common factor (HCF) or greatest common divisor (GCD).
How do I find the GCF with Euclid's algorithm?
Divide the larger number by the smaller and keep the remainder. Repeat with the smaller number and the remainder until the remainder is 0. The last divisor is the GCF. For 48 and 18: 48 = 2×18 + 12, 18 = 1×12 + 6, 12 = 2×6 + 0, so the GCF is 6.
How do I find the GCF by prime factors?
Write each number as a product of primes and multiply the primes they share, each to the lowest power it has. 48 = 2⁴ × 3 and 18 = 2 × 3², so the GCF is 2 × 3 = 6.
What does it mean if the GCF is 1?
The numbers are coprime, or relatively prime: they share no factor other than 1. 17 and 5 are coprime, and so are 8 and 15, even though 8 and 15 are not prime.
How does the GCF simplify a fraction?
Divide the top and bottom by their GCF. 48/18 has GCF 6, so it becomes 8/3, which is in lowest terms.
Can the GCF be found for more than two numbers?
Yes. Find the GCF of the first two, then of that result and the third, and so on. The GCF of 12, 18 and 24 is 6. The page shows the Euclid steps for each pair.
Related calculators
- Least Common Multiple CalculatorEnter two to six whole numbers.
- Factor CalculatorEnter a whole number to list all its factors and factor pairs.
- Prime Factorization CalculatorEnter a whole number.
- Common Factor CalculatorEnter two to six whole numbers.
- Fraction CalculatorEnter two fractions, mixed numbers, whole numbers or decimals and choose an operation.
- Proportion CalculatorChoose which of a, b, c or d is missing, enter the other three, and see the answer with the cross-multiplication worked out.
- Roman Numeral ConverterType a number to get its Roman numeral, or type a Roman numeral to get the number.