GCF Calculator

How to use the GCF calculator

The greatest common factor of a set of whole numbers is the largest number that divides all of them without remainder. It is what reduces a fraction to lowest terms in one step, what simplifies a ratio, and what tells you the largest identical group you can split several quantities into. Two methods find it, and they suit different sizes of number.

The first is prime factorisation. Break each number into primes, find the ones they have in common, and multiply those together. Twelve is 2 × 2 × 3 and eighteen is 2 × 3 × 3; both contain a 2 and a 3, and neither contains a second shared factor, so the answer is 6. This method shows why the answer is what it is, which makes it the one worth learning first.

The second method is the Euclidean algorithm, and it is enormously faster on large numbers because it never factorises anything. Divide the larger by the smaller and keep the remainder. Then divide the previous divisor by that remainder. Repeat until the remainder is zero, and the last non-zero remainder is the greatest common factor.

One property is worth knowing because it doubles as a check: every number that divides both inputs also divides their greatest common factor. So for 12 and 18 the common divisors are 1, 2, 3 and 6 — exactly the divisors of 6, and nothing else. If your candidate answer has a common divisor larger than itself, it was not the greatest.

The identity that ties GCF to LCM, and its limit

For any two whole numbers, the greatest common factor multiplied by the least common multiple equals the product of the numbers themselves. For 12 and 18 that is 6 × 36 = 216, and 12 × 18 = 216. It is a genuinely useful shortcut: find one and the other falls out of a single division.

That pairwise fold is also how this page computes the least common multiple of a longer list: take the LCM of the first two, then of that result and the third, and so on. It keeps every intermediate value at or below the final answer, whereas multiplying everything first can overflow before the division brings it back.

Greatest common denominator: the phrase, and what it means

Roughly a hundred and sixty thousand searches a month ask for the greatest, largest or highest common denominator. It is worth saying plainly that no such quantity exists under that name. Denominators are the bottoms of fractions, and the thing being asked for is one of two different quantities depending on what the fractions are doing.

The test is one question: are you reducing a single fraction, or combining two of them? Reducing wants the greatest common FACTOR, which this page computes. Combining wants the least common DENOMINATOR, which is the least common multiple of the two bottoms. They are different numbers and swapping them produces nonsense in both directions.

So if you arrived here typing greatest common denominator, you are in the right place when the job is simplifying, and one page across when the job is adding. The rule of thumb worth keeping: reducing goes DOWN and needs the largest shared factor, combining goes UP and needs the smallest shared multiple.

One more piece of vocabulary belongs here, because it is the same misnomer in reverse. Lowest common denominator is a real term and means the LCM of the denominators. Greatest common denominator is not a real term at all, and where it appears in print it is almost always standing in for greatest common factor.

Euclid's algorithm, still the fastest thing available

The method appears in the Elements, where Book VII Proposition 2 gives the construction for finding the greatest common measure of two numbers that are not relatively prime. It is one of the oldest algorithms still in everyday use, and nothing has replaced it — modern cryptography runs it on numbers hundreds of digits long.

Its speed comes from never needing to know the factors. Factorising a large number is genuinely hard — the difficulty is what much of public-key cryptography rests on — while Euclid finds the greatest common factor of two enormous numbers in a few dozen steps without discovering a single prime.

The formula, worked line by line

Two methods and one identity. The identity is the shortcut, the prime factorisation is the explanation, and Euclid is what you use when the numbers get large enough that factorising stops being practical.

It also explains why listing the common divisors is never wasted work. They are precisely the divisors of the answer, so producing them confirms the answer at the same time.

gcf = product of the primes shared by every number
Euclid: gcd(a, b) = gcd(b, a mod b), until the remainder is 0
gcf(a, b) × lcm(a, b) = a × b, for two numbers only
lcm(a, b) = a × b ÷ gcf(a, b)
common divisors of a and b = divisors of gcf(a, b)

When the answer is 1

Two numbers whose greatest common factor is 1 are called coprime, or relatively prime. It does not mean either of them is prime — 9 and 28 are coprime and neither is a prime number. It means they share no building blocks: 9 is 3 × 3 and 28 is 2 × 2 × 7, with nothing in common at all.

Where the standards put it

That second job is the one that carries into algebra. Factoring an expression means finding the greatest common factor of its terms and pulling it outside a bracket, which is the same operation performed on symbols instead of numbers.

Questions people ask