GCF calculator: greatest common factor (HCF) with working

This GCF calculator finds the greatest common factor of two to six whole numbers: the biggest number that divides into all of them exactly. The GCF is also called the HCF (highest common factor, the usual UK name) or the GCD (greatest common divisor). The GCF of 84 and 126 is 42, and the calculator shows how to get there by prime factors or by Euclid's algorithm.

It opens on 84 and 126. Type your own numbers, or open the full GCF calculator over this page with the button below.

Try it

GCF Calculator

Find the greatest common factor (HCF) step by step

Open the calculatorGo to its page

What the GCF calculator shows

• The GCF, labelled HCF (GCF), exact for whole numbers up to 1,000,000,000.
• The LCM (least common multiple) of the same numbers.
• The shared primes that multiply to give the GCF, or a note that the numbers are coprime when the GCF is 1.
• The simplest ratio of two numbers, found by dividing both by the GCF. For 84 and 126 it is 2 : 3.
• Full working by the method you choose: prime factors or Euclid's algorithm.
• A diagram: a Venn diagram of the primes for two or three numbers, a factor table for four to six, or Euclid's rectangle when you pick Euclid's algorithm for two numbers.
• Practice questions with a hint and worked solution.

How to use the GCF calculator

1. Type your numbers in Number 1 and Number 2. Press Add a number for up to six, and the cross beside a box to remove it.
2. Under Method, choose Prime factors or Euclid's algorithm in "Work it out by". The answer is the same, only the working changes.
3. Read the GCF at the top of the stage, with the LCM, the shared primes and, for two numbers, the simplest ratio beside it.
4. Follow the steps under the answer, and the diagram beside them.
5. To practise, press Random problem in the Practice section, type your answer and press Check answer.

What is the greatest common factor?

A factor of a number divides into it with no remainder. A common factor divides into all of the numbers, and the greatest common factor is the biggest one. For 16 and 20:

• Factors of 16: 1, 2, 4, 8, 16
• Factors of 20: 1, 2, 4, 5, 10, 20

The common factors are 1, 2 and 4, so GCF(16, 20) = 4. Every common factor divides into the GCF, and the GCF can never be bigger than the smallest number. Listing factors like this works for small numbers. For anything bigger, use one of the two methods the calculator uses.

How to find the GCF by prime factorization

Write each number as a product of primes (prime factorization, or prime factorisation in the UK). Take only the primes that are in every number, at the lowest power they appear, and multiply. For 84 and 126:

On a Venn diagram, the shared primes 2, 3 and 7 sit in the overlap and the leftover 2 and 3 sit outside it. The overlap multiplied together is the GCF, and that is the part the calculator shades. The prime factorization calculator draws a factor tree if you want to check one number's primes.

How to find the GCF with Euclid's algorithm

Euclid described this method in Book VII of his Elements, and it is still the fastest way to find the GCF of big numbers, because you never need their primes. It rests on one fact: the GCF of two numbers is also the GCF of the smaller number and the remainder when you divide.

1. Divide the larger number by the smaller and write down the remainder.
2. Replace the larger number with the smaller one, and the smaller one with the remainder.
3. Repeat until the remainder is 0. The last number you divided by is the GCF.

For 84 and 126 it takes two lines:

The remainder is 0 and the last divisor was 42, so the GCF is 42, the same as by primes.

Euclid's rectangle

Choose Euclid's algorithm with two numbers and the calculator draws the method. Picture an 84 by 126 rectangle. The largest square that fits is 84 by 84, which leaves an 84 by 42 strip. Two 42 by 42 squares fill that strip exactly, so 42 is the GCF. Each row of the algorithm is one size of square, and the smallest squares, which fit with nothing left over, have the GCF as their side. Very long, thin rectangles and ones with too many squares to see are not drawn, and you get the Venn diagram instead.

Worked examples you can check in the calculator

Example 1: GCF of three numbers

Find the GCF of 30, 45 and 75.

2 is not in 45 or 75, so it is left out. 3 and 5 are in all three, and the lowest power of each is 1. The GCF is 3 × 5 = 15. With Euclid's algorithm for three numbers, the calculator finds GCF(30, 45) = 15 first, then GCF(15, 75) = 15.

Example 2: GCF of large numbers

Find the GCF of 1071 and 462. Choose Euclid's algorithm in the calculator to see these lines:

The GCF is 21. Check: 1071 ÷ 21 = 51 and 462 ÷ 21 = 22, and 51 and 22 share no factor except 1.

Example 3: simplifying a fraction with the GCF

Simplify 48/180. Divide the top and bottom by their GCF and the fraction is in its simplest form in one step. GCF(48, 180) = 12, because 48 = 2⁴ × 3 and 180 = 2² × 3² × 5 share 2² × 3.

The calculator's simplest ratio shows the same thing: 48 : 180 simplifies to 4 : 15.

Example 4: a GCF word problem

A teacher has 36 pencils and 60 erasers to share into identical kits, with nothing left over. What is the greatest number of kits she can make, and what is in each?

The number of kits has to divide both 36 and 60, and you want the biggest, so find GCF(36, 60) = 12. That makes 12 kits, each with 36 ÷ 12 = 3 pencils and 60 ÷ 12 = 5 erasers. Words like "greatest", "largest" and "identical groups" point to the GCF. "Smallest" and "together again" point to the LCM instead.

Example 5: factoring out the GCF

In algebra, factoring an expression starts by taking out the GCF of the terms. For 24x + 40, GCF(24, 40) = 8, so:

Multiply out the bracket (parentheses in the US) to check. The factoring calculator does this for whole expressions, including the GCF of letters as well as numbers.

Try one

What the answer tells you

• A GCF of 1 means the numbers are coprime (relatively prime): they share no prime. 25 and 36 are coprime, though neither is prime.
• If one number divides the other, the smaller one is the GCF. GCF(15, 45) = 15.
• Dividing by the GCF leaves numbers that are coprime, which is why it gives a fraction or ratio in its simplest form.
• For two numbers, GCF × LCM = the product. For 84 and 126: 42 × 252 = 10,584 = 84 × 126. The LCM calculator guide uses this to find the LCM.

Common mistakes

• Taking the highest powers. That gives the LCM. The GCF takes the lowest power of each shared prime.
• Including primes that aren't in every number. In example 1, 2 divides 30 but not 45, so it can't be in the GCF.
• Stopping at a common factor. 6 divides 24 and 36, but 12 is the greatest. Dividing by a common factor that isn't the GCF leaves a fraction that still simplifies.
• Dividing the wrong way in Euclid's algorithm. Always divide the larger number by the smaller one, then carry the remainder forward.
• Thinking the GCF must be prime. It is often a product of primes, like 42 = 2 × 3 × 7.

GCF, HCF and GCD in school

In the US, the Common Core standards ask grade 6 students to find the greatest common factor of two whole numbers up to 100, and to use it with the distributive property, writing a sum like 36 + 8 as 4(9 + 2). In England, the national curriculum covers common factors in key stage 2 and the highest common factor by name at key stage 3. GCD is the name you will meet in computing and university maths, where Euclid's algorithm is a standard first algorithm.

Read next

Maths · NumberLCM calculator: least common multiple with stepsFind the LCM (least or lowest common multiple) of up to six numbers with prime factor steps, a Venn diagram, worked examples and a quick check.