GCF Calculator

What Is the Greatest Common Factor (GCF)?

The greatest common factor of two numbers is the biggest whole number that divides both of them exactly. Take 12 and 18. The factors of 12 are 1, 2, 3, 4, 6 and 12. The factors of 18 are 1, 2, 3, 6, 9 and 18. They share 1, 2, 3 and 6, and the biggest of those is 6. So GCF(12, 18) = 6.

You will meet the same idea under three names. GCF is what most US schools say, HCF (highest common factor) is the usual term in the UK and India, and GCD (greatest common divisor) shows up in college maths and in programming. They are the same number, so this calculator answers all three.

How to Use This GCF Calculator

1. Type your first number in the First number box and your second in the Second number box.
2. Press Calculate, or hit Enter on your keyboard.
3. Read the answer. You get the GCF, the LCM, the prime factorization of each number, the common factors and the Euclidean algorithm steps.

Use Paste to drop a number in from your clipboard, or tap one of the example pairs under the box to see how a finished answer looks.

Method 1: Find the GCF by Listing Factors

This is the method most teachers start with. Write every factor of each number, circle the ones that appear in both lists, and pick the biggest. Here it is for 24 and 36:

Listing is easy to follow and hard to get wrong, but it gets slow once the numbers pass about 100. For bigger numbers, jump to the next two methods.

Method 2: Find the GCF with Prime Factorization

Break each number into primes. Then look for the primes that appear in both numbers and multiply them, using the lowest power each time. Here is 84 and 126:

Look at the prime 2. It appears as 2² in 84 but only as 2¹ in 126, so you keep 2¹. The prime 3 is the other way round (3¹ in 84, 3² in 126), so you keep 3¹. The prime 7 is in both once. That gives 2 × 3 × 7 = 42.

If a prime is missing from even one of the numbers, it does not go in the GCF. If the numbers share no primes at all, the GCF is 1.

Method 3: The Euclidean Algorithm for Big Numbers

The Euclidean algorithm is over 2,000 years old and it is still what computers use. It never needs a factor list. You divide, keep the remainder, and repeat:

1. Divide the bigger number by the smaller one.
2. Keep the remainder.
3. Divide the old divisor by that remainder.
4. Stop when the remainder is 0. The last non-zero remainder is the GCF.

Why does it work? Any number that divides both a and b also divides the remainder, so the pair keeps exactly the same common factors while the numbers get smaller each round. When one of them hits 0, the other is what is left.

A bigger example: GCF(1071, 462)

Listing the factors of 1,071 would take a while. The algorithm takes three lines:

• 1,071 = 2 × 462 + 147
• 462 = 3 × 147 + 21
• 147 = 7 × 21 + 0

The remainder hits 0 on the third line, and the one before it was 21, so GCF(1071, 462) = 21.

How to Find the GCF of Three or More Numbers

Find the GCF of the first two numbers, then find the GCF of that answer and the next number. Keep going until you run out of numbers. For 12, 18 and 30:

• GCF(12, 18) = 6
• GCF(6, 30) = 6

So the GCF of 12, 18 and 30 is 6. You can check it with primes: 12 = 2² × 3, 18 = 2 × 3² and 30 = 2 × 3 × 5. The primes in all three are 2 and 3, each at power 1, and 2 × 3 = 6.

How the GCF and LCM Are Connected

The least common multiple (LCM) is the smallest number that both of your numbers divide into. For any two numbers, the GCF and LCM are tied together by one formula:

GCF(a, b) × LCM(a, b) = a × b

Check it with 24 and 36. The GCF is 12 and the LCM is 72, and 12 × 72 = 864, which is also 24 × 36. That means once you have the GCF, the LCM is just a × b ÷ GCF. This shortcut only works for two numbers at a time, so do not use it on three.

Use the GCF to Simplify Fractions

To reduce a fraction to lowest terms, divide the top and the bottom by their GCF. You do it in one step, with no repeated halving. Here is 48/180:

Since 4 and 15 share no factor other than 1, the fraction is fully simplified. If you divide by something smaller than the GCF, you end up with a fraction that still needs another round.

GCF Word Problems

The GCF answers questions that start with "what is the biggest group size that fits both?"

Sharing equally

A teacher has 48 pencils and 60 erasers and wants identical kits with nothing left over. What is the most kits she can make? GCF(48, 60) = 12, so she makes 12 kits, each with 4 pencils (48 ÷ 12) and 5 erasers (60 ÷ 12).

Tiling a floor

A floor measures 252 cm by 105 cm. What is the biggest square tile that covers it with no cutting? That is GCF(252, 105) = 21, so use 21 cm tiles. You need 12 along the long side and 5 along the short side, which is 60 tiles in total.

GCF Shortcuts Worth Remembering

• Coprime numbers have a GCF of 1. 17 and 31 are both prime, and 8 and 15 are coprime even though neither is prime.
• Consecutive numbers are always coprime. GCF(14, 15) = 1, and the same goes for any n and n + 1.
• If one number divides the other, the GCF is the smaller one. GCF(7, 21) = 7.
• If both numbers are even, the GCF is at least 2. If both end in 0 or 5, it is at least 5.
• The GCF is never bigger than the smaller of the two numbers.

Common GCF Mistakes to Avoid

• Mixing up GCF and LCM. The GCF is a factor, so it is small. The LCM is a multiple, so it is big.
• Taking the highest power. For the GCF you take the lowest power of each shared prime. The highest power is what you use for the LCM.
• Including a prime that is not shared. It must appear in every number, or it stays out.
• Stopping on the wrong line in Euclid's algorithm. The answer is the last non-zero remainder, not the 0.

Whichever method you use, type the same two numbers into the calculator at the top of the page to check your answer.