Skip to content
MasterMath

GCF Calculator

The greatest common factor of two or three numbers, with the prime factorisations that produce it — and the lowest common multiple thrown in.

Greatest common divisor

—

Greatest common divisor—
Lowest common multiple—
Factorisations—
Are they coprime?—

How this was worked out

    The rule

    GCF = product of the shared primes, each with its lowest exponent

    Why it works

    The greatest common divisor is the largest number that divides all of them exactly. Factoring each into primes makes it obvious: take only the primes they all share, each raised to the smallest exponent that appears.

    How to do it by hand

    1. Factor every number into primes
    2. Keep only the primes that appear in all of them
    3. Give each the smallest exponent it has anywhere
    4. Multiply those together

    What is worth knowing

    Euclid's algorithm finds the GCD without factoring at all: divide, keep the remainder, repeat until it reaches zero. It is over two thousand years old, and it is still what computers use, because factoring large numbers is hard and this is not. The GCD is what simplifies fractions to lowest terms in one step, and it also gives the LCM for free through the identity GCD × LCM = the product of the two numbers — an identity that holds for two numbers and, importantly, not for three.

    Frequently asked questions

    What is the greatest common factor?

    The largest number that divides all the given numbers exactly. It is what reduces a fraction to lowest terms.

    How does Euclid's algorithm work?

    Divide the larger by the smaller, keep the remainder, and repeat until the remainder is zero. The last non-zero remainder is the GCD.

    What does coprime mean?

    That the numbers share no factor other than 1, so their GCD is 1. They need not be prime themselves: 8 and 9 are coprime.

    Is GCD × LCM always the product?

    For two numbers, yes. For three or more the identity does not hold.