How to use this calculator
- 1 Type two to twenty whole numbers, separated by commas or spaces.
- 2 Use whole numbers from 1 up to 1,000,000,000,000. Decimals and zero are not accepted.
- 3 Read the greatest common factor. For two numbers, the summary shows Euclid’s method step by step.
What is the greatest common factor?
A common factor is a number that divides two or more numbers exactly. The greatest common factor is the biggest of those. It is also called the greatest common divisor (GCD), or the highest common factor (HCF) in some countries.
For example, the factors of 12 are 1, 2, 3, 4, 6 and 12. The factors of 18 are 1, 2, 3, 6, 9 and 18. The shared factors are 1, 2, 3 and 6, so the greatest common factor is 6.
The GCF is never bigger than the smallest number in the list. Every number in the list is a multiple of it. To list every factor of one number, use the factor calculator.
| Number | Factors | Shared factors |
|---|---|---|
| 12 | 1, 2, 3, 4, 6, 12 | 1, 2, 3, 6 |
| 18 | 1, 2, 3, 6, 9, 18 | Greatest shared: 6 |
Euclid’s method for big numbers
Listing factors works for small numbers, but it is slow for big ones. Euclid’s method is faster. Divide the larger number by the smaller, and keep the remainder. Then repeat with the smaller number and the remainder. When the remainder reaches 0, the last nonzero remainder is the GCF.
Take 48 and 180. Since 180 = 3 × 48 + 36, the next step uses 48 and 36. Then 48 = 1 × 36 + 12, so the next step uses 36 and 12. Finally 36 = 3 × 12 + 0. The last nonzero remainder is 12, so the GCF is 12.
The calculator shows these steps for two numbers. It uses the same method for every pair, even with very large inputs.
More than two numbers
To find the GCF of three or more numbers, combine them two at a time. Find the GCF of the first two, then find the GCF of that answer and the next number. Keep going until the list is used up.
For 12, 18 and 24, the GCF of 12 and 18 is 6. Then the GCF of 6 and 24 is also 6. So the GCF of all three is 6.
Using the GCF in everyday maths
The GCF is useful when you simplify a fraction. Divide the top and bottom by the GCF. For 18/24, the GCF is 6, so the fraction becomes 3/4. You can check the simplified fraction with the fraction calculator.
It also helps with sharing. Suppose you have 12 red balls and 18 blue balls, and you want identical gift bags with the same mix in each bag. The most bags you can make is 6, with 2 red and 3 blue in each one.
If you need the opposite, the smallest number that every value divides into, use the LCM calculator.
Relatively prime numbers
If the GCF of two numbers is 1, the numbers are called relatively prime, or coprime. They share no factor except 1. For example, 15 and 28 are relatively prime, even though neither is prime.
Relatively prime numbers are useful in fractions. A fraction is already in its simplest form when its top and bottom are relatively prime. For example, 5/8 cannot be simplified further.
The formula
Euclid’s method for two numbers
gcf(a, b) = gcf(b, a mod b), and gcf(a, 0) = a
- a, b
- the two numbers, with a at least as large as b
- a mod b
- the remainder when a is divided by b
More than two numbers
gcf(a, b, c) = gcf(gcf(a, b), c)
- gcf(a, b)
- the result of the previous pair, which then pairs with the next number
Worked example
GCF of 48 and 180
- 1.Divide 180 by 48: 180 = 3 × 48 + 36.
- 2.Divide 48 by 36: 48 = 1 × 36 + 12.
- 3.Divide 36 by 12: 36 = 3 × 12 + 0.
- 4.The last nonzero remainder is 12.
The greatest common factor of 48 and 180 is 12.
Frequently asked questions
What is the difference between GCF and LCM?
The greatest common factor is the largest number that divides every value in the list. The least common multiple is the smallest number that every value divides into. Use the LCM calculator for that.
What does it mean when the GCF is 1?
The numbers share no factor other than 1. They are called relatively prime, or coprime. For example, 17 and 31 are both prime, so their GCF is 1.
Why does Euclid’s method work?
Any number that divides both a and b also divides the remainder a − b × q. So the pair (a, b) and the pair (b, remainder) have the same common factors, and the process keeps shrinking the numbers until the remainder is 0.
Is the GCF the same as the GCD or HCF?
Yes. GCF, GCD and HCF are different names for the same number. Use whichever name your class or textbook uses.
Sources
Last reviewed by the GridCalculators team.