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.

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