GCF calculator (greatest common factor)
Give the GCF calculator 84 and 126 and the greatest common factor is 42: the largest whole number that divides both with nothing left over. Euclid's algorithm finds it in two steps.
Greatest common factor
- Least common multiple
- 252
- Numbers
- 84, 126
- Prime factorizations
- 84 = 2^2 x 3 x 7 126 = 2 x 3^2 x 7
- GCF takes the lowest power of each shared prime
- 2 x 3 x 7 = 42
- LCM takes the highest power of every prime
- 2^2 x 3^2 x 7 = 252
- Euclid's algorithm The last non-zero remainder's divisor is the GCF: 42. This needs no factorization at all, which is why it works on numbers far too large to factor.
- 126 = 1 x 84 + 42 84 = 2 x 42 + 0
- GCF x LCM = the product True for exactly two numbers and not for three or more. It is how the LCM is computed here, which avoids ever building the product first and overflowing.
- 42 x 252 = 10,584 = 84 x 126
- Reduced ratio Dividing every number by the GCF of 42 gives the simplest whole-number ratio.
- 2 : 3
- The fraction 84/126 reduced Reducing a fraction is the GCF's most common use.
- 2/3
- Adding fractions with these denominators The LCM's most common use. The product of the denominators also works but leaves more reducing to do.
- use 252 as the common denominator
- GCF is also called the greatest common divisor, highest common factor, GCD or HCF. They are all the same thing.
- Two numbers with a GCF of 1 are called coprime or relatively prime. They need not be prime themselves: 8 and 9 are coprime.
How the GCF and LCM Calculator works
The greatest common factor (GCF) of two numbers is the largest whole number that divides both of them exactly. It goes by several names, including greatest common divisor (GCD) and highest common factor (HCF), and they all mean the same number. For 84 and 126 it is 42.
There are three ways to find it, and they suit different sizes of number.
Listing factors is the method most people learn first. The factors of 84 are 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42 and 84. The factors of 126 are 1, 2, 3, 6, 7, 9, 14, 18, 21, 42, 63 and 126. The ones on both lists are 1, 2, 3, 6, 7, 14, 21 and 42, and the greatest is 42. It works, and it is slow and easy to get wrong past two or three digits, because missing one factor can mean missing the answer.
Prime factorization is tidier. 84 = 2^2 x 3 x 7 and 126 = 2 x 3^2 x 7. Take each prime that appears in both, at the lower of its two powers: 2^1, 3^1 and 7^1. Their product, 2 x 3 x 7, is 42. Taking the higher powers, and the primes that appear in only one number, is the least common multiple instead. It is a mix-up worth watching for.
Euclid's algorithm needs no factoring at all. Divide the larger number by the smaller and keep the remainder: 126 = 1 x 84 + 42. Then divide the previous divisor by that remainder: 84 = 2 x 42 + 0. When the remainder reaches zero, the last divisor is the GCF, so 42 again. This is the method to use for big numbers, and it is how software does it.
Two quick checks catch most wrong answers. The GCF can never be larger than the smaller number, and it must divide both numbers exactly: 84 / 42 = 2 and 126 / 42 = 3. If one number is a multiple of the other, the GCF is simply the smaller one, so the GCF of 42 and 126 is 42. If two numbers share no prime at all, the GCF is 1 and they are called coprime.
The GCF is what reduces a fraction to lowest terms in one step: 84/126, divided top and bottom by 42, is 2/3, and because 42 is the greatest common factor, nothing more will cancel. It also answers grouping questions. 84 pens and 126 pencils make at most 42 identical kits, each with 2 pens and 3 pencils. A floor 84 by 126 cm is covered by 42 cm square tiles with none cut, 2 by 3 of them.
For three or four numbers, take the GCF of the first two and then the GCF of that with the next. Adding 90 to the example gives the GCF of 42 and 90, which is 6. The page takes whole numbers only, ignores a 0 in the optional boxes, and has nothing to say about decimals, where "common factor" has no standard meaning.
GCF and LCM Calculator FAQ
What is the GCF of 84 and 126?
42. In primes, 84 = 2^2 x 3 x 7 and 126 = 2 x 3^2 x 7, and the shared primes at their lower powers are 2 x 3 x 7 = 42.
Is GCF the same as GCD and HCF?
Yes. Greatest common factor, greatest common divisor and highest common factor are three names for the same number. Different countries and textbooks prefer different ones.
How does Euclid's algorithm find the GCF?
Divide the larger number by the smaller, then keep dividing the last divisor by the last remainder until the remainder is zero. The last divisor is the GCF. For 126 and 84: 126 = 1 x 84 + 42, then 84 = 2 x 42 + 0, so the GCF is 42.
What does a GCF of 1 mean?
That the numbers share no factor except 1, which makes them coprime. Neither has to be prime: 8 and 9 have a GCF of 1.