GCF Calculator

What the greatest common factor means

A factor is a whole number that divides another number with nothing left over. The factors of 24 are 1, 2, 3, 4, 6, 8, 12 and 24. The factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36. Put the lists side by side and the numbers that appear in both are 1, 2, 3, 4, 6 and 12.

The greatest common factor is the largest number on that shared list, which is 12. Textbooks also call it the greatest common divisor, or GCD, and write it as GCF(24, 36) = 12. The calculator on this page does the same job for two or three numbers and shows the working, not just the answer.

Two details trip people up. First, "greatest" means largest in value, not the number that shows up most often. Second, every pair of whole numbers has at least one common factor, because 1 divides everything. When 1 is the only shared factor, the numbers are called coprime or relatively prime. 9 and 28 are coprime: 9 is 3 x 3 and 28 is 2 x 2 x 7, so the two lists share nothing.

Zero is a special case. Every number divides zero, so the GCF of 0 and any number n is n. The calculator asks for numbers of 1 or more, which is the range that comes up in school work and in most real problems.

Three ways to find it, and when each one is faster

There is no single method. The right one depends on how big the numbers are and how easily they break into primes.

Listing works because it needs no arithmetic beyond division. Its weakness is that students stop at the first shared factor they spot. For 24 and 36, 2 is shared and 4 is shared, but neither is the answer. You have to walk the whole list or you will report a common factor instead of the greatest one.

Prime factorization is the method taught in most US middle schools. The catch is that it only helps when factoring is easy. Try 1,078 and 462 by hand and you will spend a while on the primes. The Euclidean algorithm skips factoring entirely, which is why it is the method computers use. Whitman College's number theory chapter walks through the same steps with a proof.

Worked example: the GCF of 48 and 180

Start by breaking both numbers into primes. 48 divides by 2 four times, which leaves 3, so 48 = 2 x 2 x 2 x 2 x 3 = 2^4 x 3. For 180, take out 2 twice to get 45, then 3 twice to get 5, so 180 = 2^2 x 3^2 x 5.

Only 2 and 3 appear in both rows, and each one is used as many times as the number that has fewer of them. 48 has four 2s but 180 has only two, so you keep two 2s. 48 has one 3 and 180 has two, so you keep one 3. The 5 in 180 is dropped because 48 has no 5.

Multiply what is left: 2^2 x 3 = 4 x 3 = 12. To confirm that 12 is the greatest and not just a common factor, divide both numbers by it. 48 / 12 = 4 and 180 / 12 = 15, and 4 and 15 share no factor larger than 1. If a larger common factor existed, those two quotients would still have something in common.

The practical payoff is the fraction 48/180. Divide the top and bottom by 12 and it becomes 4/15, which is about 0.2667. Nothing smaller than 12 will clear both numbers in one step, so 4/15 is the reduced form.

Worked example: three numbers at once

Three numbers work the same way. Take 84, 126 and 210. In prime form, 84 = 2^2 x 3 x 7, 126 = 2 x 3^2 x 7, and 210 = 2 x 3 x 5 x 7.

Every row contains at least one 2, one 3 and one 7, so all three share 2 x 3 x 7 = 42. The extra powers and the 5 sit in only one or two of the numbers, so they cannot be part of the shared factor. Divide each number by 42 to check: 84 gives 2, 126 gives 3 and 210 gives 5.

If you prefer to work two at a time, the result is the same. GCF(84, 126) = 42, then GCF(42, 210) = 42, because 210 is a multiple of 42. That chain rule holds in general: the GCF of three numbers equals the GCF of the first two, taken with the third.

A tiling job shows why the answer matters. A floor measures 84 inches by 126 inches and you want square tiles of one size with no cutting. The largest square that fits is 42 inches on a side, and you need 2 tiles across by 3 tiles down, so 6 tiles. Tiles of 21 inches would also fit, but you would need 4 by 6, or 24 tiles, and pay for four times as many.

The Euclidean algorithm, step by step

The Euclidean algorithm finds the GCF without ever factoring a number. Divide the larger number by the smaller and write down the remainder. Then divide the old divisor by that remainder. Keep going until the remainder is 0. The last nonzero remainder is the GCF.

Two divisions finish a pair that would take a page of prime factoring. Check the answer by dividing: 1,078 / 154 = 7 and 462 / 154 = 3, so 154 divides both, and 7 and 3 share nothing.

Why it works comes down to one fact. If a number divides both a and b, it also divides a - b, and therefore it divides the remainder when a is divided by b. So the set of common factors never changes from one step to the next, and the last nonzero remainder carries all of them.

For 48 and 180 the same method runs as 180 = 3 x 48 + 36, then 48 = 1 x 36 + 12, then 36 = 3 x 12 + 0, which lands on 12 in three steps. Long division by hand is often quicker than hunting for primes once the numbers pass a few hundred. Wolfram MathWorld gives the formal definition plus the extended version that also finds the multipliers.

How the GCF and the LCM fit together

The least common multiple, or LCM, is the smallest number that both original numbers divide into. The two ideas are linked by a rule that is easy to check: for any two positive whole numbers, the GCF times the LCM equals the product of the numbers.

So once you have the GCF, the LCM comes free: 48 x 180 = 8,640, and 8,640 / 12 = 720. That is faster than listing multiples of 180 until one is also a multiple of 48.

The pair of answers describes different jobs. The GCF splits things into the largest identical groups. The LCM lines up repeating events. If one machine cycles every 48 minutes and another every 180 minutes, they line up again after 720 minutes, which is 12 hours, not after 48 or 180.

With three numbers the product rule does not hold, because the LCM of three numbers is not the product divided by their GCF. Use the chain: LCM(a, b, c) = LCM(LCM(a, b), c).

Where this shows up outside math class

Most people meet the GCF through a fraction that needs simplifying, but the same arithmetic answers a few practical questions.

Woodworking and sewing use the tile idea constantly. If a pattern repeats every 84 stitches and a border every 126, the design lines up every 42 stitches, so 42 is the repeat length to build around. Buying material in 42 inch units wastes less than buying in 84 inch units.

The kit example is the classic classroom word problem, and it is also how a warehouse splits a mixed pallet. You have three counts and you want identical boxes with nothing left over. The GCF is the largest number of boxes that can be packed evenly.

Mistakes and edge cases

Most wrong answers come from four habits.

Stopping at the first shared factor. For 24 and 36, 2 is a common factor, and so is 4, but the answer is 12. Listing has to be complete, or you should use prime factorization instead.

Mixing up GCF and LCM. The GCF is smaller than or equal to the smaller number. The LCM is larger than or equal to the larger number. If your GCF is bigger than both inputs, you computed the LCM.

Forgetting that 1 always works. A GCF of 1 is a real answer, not a failure. It means the numbers are coprime, which is normal for consecutive numbers: 35 and 36 share nothing but 1.

Feeding in decimals. The GCF is defined for whole numbers. If a problem has 4.8 and 18, scale both by 10 first, find the GCF of 48 and 180, which is 12, then scale back to 1.2.

Negative numbers are handled by ignoring the sign, since -12 divides 48 just as 12 does. Zero is the odd one: GCF(0, n) = n for any positive n, and GCF(0, 0) is undefined. The calculator on this page ignores a third box left at 0 so you can use it for two numbers without clearing the field.