GCF Calculator

In mathematics, the greatest common factor (GCF), also known as the greatest common divisor, of two or more non-zero integers a and b is the largest positive integer by which all of them can be divided. It is written GCF(a, b). For example, GCF(32, 256) = 32.

The name says exactly what it is. A factor of a number divides it with nothing left over, a common factor divides all of your numbers, and the greatest common factor is the largest one that does.

Prime factorization method

There are multiple ways to find the greatest common factor. One involves computing the prime factorization of each integer, determining which factors they have in common, and multiplying those together.

Finding GCF(16, 88, 104): 16 = 2 × 2 × 2 × 2, 88 = 2 × 2 × 2 × 11, and 104 = 2 × 2 × 2 × 13. All three contain three copies of 2 and nothing else in common, so the GCF is 2 × 2 × 2 = 8.

Notice the counting. The 16 holds four 2s but the other two hold only three, so only three can be shared. The greatest common factor takes the lowest power of each prime present in every number, the exact mirror of the LCM taking the highest power of each prime present in any of them.

Prime factorization is only efficient for smaller integers. Larger values make both the factorization and the comparison of common factors far more tedious, which is why the second method exists.

Euclidean algorithm

The Euclidean algorithm is a far more efficient method than prime factorization. It uses a division algorithm combined with the observation that the greatest common divisor of two integers also divides their difference. The rules are:

In practice:

1. Given two positive integers a and b, where a is larger, subtract the smaller number b from the larger number a to arrive at the result c.
2. Continue subtracting b from a until the result c is smaller than b.
3. Use b as the new large number and subtract the final result c, repeating the process.
4. Once the remainder is 0, the GCF is the remainder from the step preceding the zero result.

Working GCF(268442, 178296) this way: 268442 − 178296 = 90146, then 178296 − 90146 = 88150, then 90146 − 88150 = 1996. From there 88150 − 1996 × 44 = 326, then 1996 − 326 × 6 = 40, then 326 − 40 × 8 = 6, then 6 − 4 = 2, and finally 4 − 2 × 2 = 0. The last non-zero value is 2, so GCF(268442, 178296) = 2.

Repeated subtraction is the original form, and subtracting a multiple at a time, as the middle lines do, is division with remainder written out longhand. Doing it directly, as this calculator does, replaces the larger number with the remainder of dividing it by the smaller. Those two six-figure numbers then resolve in a handful of divisions rather than hundreds of subtractions.

If more integers are present, apply the same process to the result and the next number. For GCF(268442, 178296, 66888), knowing that GCF(268442, 178296) is 2, the next step is GCF(66888, 2), which is also 2, giving a final answer of 2.

The algorithm appears in Euclid's Elements around 300 BC and is often described as the oldest algorithm still in everyday use. It is genuinely fast: the worst case is a pair of consecutive Fibonacci numbers, proved by Gabriel Lamé in 1844 in what is regarded as the first analysis of an algorithm's running time. Even then the number of steps grows with the number of digits, not with the size of the values.

Reading the worked example

For 330, 75, 450 and 225 the factorizations are 330 = 2 × 3 × 5 × 11, 75 = 3 × 5 × 5, 450 = 2 × 3 × 3 × 5 × 5, and 225 = 3 × 3 × 5 × 5.

The 3 appears in all four and so does the 5, each at least once. The 2 appears in 330 and 450 but not in 75 or 225, so it cannot be shared, and the same goes for the 11. Multiplying the factors common to every number gives 3 × 5 = 15.

The calculator marks those shared copies in each line, so you can see precisely which ones are being counted. The table underneath shows the same thing as a grid: each column is a prime, and the GCF row takes the smallest value in every column. Any column containing a dash contributes nothing at all, because one of your numbers has no copy of that prime.

Useful properties

The GCF is never larger than the smallest number in your list and is always at least 1. It equals the smallest input exactly when that number divides all the others, so GCF(6, 12, 18) is 6. When the GCF is 1 the numbers are called coprime, or relatively prime, which does not require any of them to be prime: 8 and 9 are coprime, since one is all 2s and the other all 3s.

For two numbers, GCD × LCM = a × b, so finding one immediately gives the other. There is also a deeper property, Bézout's identity, which says the GCF of a and b can always be written as ax + by for some integers x and y. For 12 and 18, the GCF of 6 can be written as 12 × (−1) + 18 × 1. The extended Euclidean algorithm finds those coefficients, and it is how modular inverses are computed during RSA key generation.

Where it gets used

Simplifying fractions is the most common use. Dividing the numerator and denominator by their GCF reduces the fraction to lowest terms in a single step: 84/210 has a GCF of 42, so it becomes 2/5 immediately rather than through several rounds of halving.

Dividing things into equal groups is the same question wearing different clothes. Sharing 24 pens and 36 pencils into identical packs with nothing left over allows at most GCF(24, 36) = 12 packs. Tiling a floor of 330 by 225 centimetres with the largest possible square tiles and no cutting needs a tile of GCF(330, 225) = 15 centimetres.

The GCF also underpins reducing ratios to simplest form, finding the fundamental period of combined signals, and, through the extended algorithm, a substantial amount of modern cryptography.

Notes on this calculator

Enter as many whole numbers as you like, separated by commas, spaces or new lines. The result panel gives the GCF along with the LCM, the shared prime factors and the number of distinct primes involved. The steps show every factorization with the shared copies marked, then the product that forms the answer.

With exactly two numbers, the Euclidean algorithm table also appears, listing each division, quotient and remainder down to the zero that ends it. That table is worth a look even when you already trust the answer, because it shows how few steps the method needs compared with factorising both numbers.