GCF calculator

Type two or more whole numbers, separated by commas or spaces, such as 48, 36 or 24 36 60. The greatest common factor appears straight away, with the working below and the least common multiple beside it. Up to 10 numbers work, each up to a trillion.

For two numbers the working shows both ways of finding it, the prime factors, sorted in a Venn diagram, and Euclid's method of repeated division as a check. They always agree.

A factor of a number divides it exactly. The factors of 12 are 1, 2, 3, 4, 6 and 12; the factors of 18 are 1, 2, 3, 6, 9 and 18. The ones they have in common are 1, 2, 3 and 6, and the greatest of those, 6, is the greatest common factor. It's also called the highest common factor (HCF), mostly in the UK, and the greatest common divisor (GCD) by mathematicians and programmers. All three are the same number.

Simplifying a fraction is the usual use. Divide the top and bottom of 36/48 by their GCF, 12, and you get 3/4 in one step, already in lowest terms. It also answers sharing problems: the largest equal groups that 48 pencils and 36 rubbers can both be split into, with none left over, is 12 groups.

Write each number as a product of primes, so 48 = 2⁴ × 3 and 36 = 2² × 3². Then take the primes they share, each to the lowest power it has in any of them. Both have 2, at least twice, and 3, at least once, so the GCF is 2² × 3 = 12.

The Venn diagram shows the same thing. Each number's primes go in its circle, and primes the two share go in the overlap. Multiply the overlap for the GCF. Multiply everything in both circles for the least common multiple. If the overlap is empty the GCF is 1, and the numbers are called coprime.

For big numbers, factoring is slow, and Euclid's method from around 300 BC is much faster. Divide the larger number by the smaller and keep the remainder, so 48 = 1 × 36 + 12. Then divide the smaller number by that remainder, giving 36 = 3 × 12 + 0. When the remainder is 0, the last number you divided by, 12, is the GCF.

It works because any number that divides both 48 and 36 also divides their difference, and so the remainder. The pair shrinks at every step but keeps the same common factors, until one divides the other exactly.