Greatest Common Factor Calculator

What is the Greatest Common Factor (GCF)?

The greatest common factor of two or more whole numbers is the largest whole number that divides each of them with no remainder. It goes by several names: greatest common divisor (GCD), highest common factor (HCF) and greatest common measure. The GCF of 12 and 18 is 6, because 6 divides both and no larger number does. If two numbers share no factor except 1, such as 8 and 15, their GCF is 1 and they are called coprime or relatively prime.

The GCF is most often used to reduce fractions to lowest terms, to split things into the largest equal groups, and to factor algebraic expressions.

Prime Factorization Method

Break each number into its prime factors, then multiply together the primes that all of the numbers share, using each shared prime the smallest number of times it appears in any of them.

For the default values: 330 = 2 × 3 × 5 × 11, 75 = 3 × 5 × 5, 450 = 2 × 3 × 3 × 5 × 5 and 225 = 3 × 3 × 5 × 5. The only primes common to all four are 3 and 5, and each appears at least once in every number, so the GCF is 3 × 5 = 15. In exponent form, take the lowest power of every prime that appears in all the factorizations.

This method shows clearly why the answer is what it is, but factoring large numbers is slow, so for big values the Euclidean algorithm is preferred.

Euclidean Algorithm

Euclid described this method around 300 BC, and it remains one of the oldest algorithms still in everyday use. It rests on one fact: any number that divides both a and b also divides the remainder when a is divided by b. So the GCF of a and b is the same as the GCF of b and that remainder. Replacing the pair with smaller and smaller numbers eventually produces a remainder of zero, and the last non-zero remainder is the GCF.

Take 330 and 75. Dividing 330 by 75 gives 4 with a remainder of 30. Now find the GCF of 75 and 30: 75 ÷ 30 is 2 remainder 15. Next, 30 ÷ 15 is 2 remainder 0. The remainder is zero, so the GCF of 330 and 75 is 15. The table in the results shows each of these steps.

For more than two numbers, apply the algorithm repeatedly: GCF(a, b, c) = GCF(GCF(a, b), c). Since GCF(330, 75) = 15, and 15 divides 450 and 225 evenly, the GCF of all four numbers is 15.

The algorithm is remarkably fast: the number of steps grows only with the number of digits, not the size of the numbers, so even numbers hundreds of digits long are handled in a moment. An older version uses repeated subtraction instead of division, replacing the larger number with the difference until the two are equal; it reaches the same answer but can take many more steps. The extended Euclidean algorithm also finds integers x and y with ax + by = GCF(a, b), which is the basis of modular inverses used in RSA encryption.

Frequently asked questions