GCF and LCM Calculator

What the GCF and LCM are

The greatest common factor (GCF) of some whole numbers is the largest number that divides all of them with no remainder. It is also called the greatest common divisor (GCD) or highest common factor (HCF). The factors of 12 are 1, 2, 3, 4, 6 and 12; of 18, 1, 2, 3, 6, 9 and 18; the largest they share is 6.

The least common multiple (LCM) is the smallest positive number that every one of them divides into. Multiples of 12 are 12, 24, 36, 48…; of 18, 18, 36, 54…; the first they share is 36.

You use the GCF to simplify a fraction (divide the top and bottom by it) and to split things into the largest equal groups. You use the LCM to find a common denominator and to work out when repeating events line up again. Listing factors or multiples works for small numbers; the two methods below work for any size.

Two methods: prime factors and Euclid’s algorithm

Prime factors. Write each number as a product of primes. The GCF takes the primes that appear in every number, each to the lowest power it has; the LCM takes every prime that appears anywhere, each to the highest power.

Euclid’s algorithm. Divide the larger number by the smaller and keep the remainder. Then divide the previous divisor by that remainder, and repeat until the remainder is 0. The last non-zero remainder is the GCF. It needs no factoring, so it stays fast for very large numbers. The LCM then follows from the GCF:

a, b

two positive whole numbers

p

a prime number (2, 3, 5, 7, 11…)

For three or more numbers, apply either method one number at a time: GCF(a, b, c) = GCF(GCF(a, b), c), and likewise for the LCM.

Worked example: 12, 18 and 30

Prime factors. 12 = 2² × 3, 18 = 2 × 3², 30 = 2 × 3 × 5. The primes in all three are 2 and 3, each at least to the first power, so the GCF is 2 × 3 = 6. Taking every prime at its highest power gives the LCM: 2² × 3² × 5 = 180.

Euclid’s algorithm. For 18 and 12: 18 ÷ 12 = 1 remainder 6, then 12 ÷ 6 = 2 remainder 0, so GCF(12, 18) = 6. Bring in 30: 30 ÷ 6 = 5 remainder 0, so the GCF of all three is 6. For the LCM: LCM(12, 18) = 12 × 18 ÷ 6 = 36, then LCM(36, 30) = 36 × 30 ÷ 6 = 180.

Two numbers: 48 and 180. 180 ÷ 48 = 3 remainder 36; 48 ÷ 36 = 1 remainder 12; 36 ÷ 12 = 3 remainder 0. The GCF is 12 and the LCM is 48 × 180 ÷ 12 = 720. For any two numbers GCF × LCM equals their product: 12 × 720 = 8,640 = 48 × 180.

Things worth knowing

• A GCF of 1 means “relatively prime”. 8 and 15 share no prime factor, so their GCF is 1 and their LCM is simply 8 × 15 = 120. Neither number has to be prime itself.
• GCF × LCM = product works only for two numbers. For 12, 18 and 30 the product is 6,480 but GCF × LCM is 6 × 180 = 1,080.
• Common denominators. The least common denominator of 5/12 and 7/18 is LCM(12, 18) = 36. The fraction calculator finds it for you when adding or subtracting, and the ratio calculator divides by the GCF to simplify ratios such as 12:18 to 2:3.
• The LCM grows quickly. Ten numbers near a trillion can have an LCM more than 100 digits long, so the calculator works in exact whole-number arithmetic with no size limit on the result.

Limits of this calculator

It accepts 2 to 10 positive whole numbers, each up to one trillion (10¹²). Zero is left out on purpose: every number divides 0, so GCF(a, 0) = a, while the LCM involving 0 is not useful. Negative numbers have the same GCF and LCM as their absolute values, so enter them without the sign. Prime factorization uses trial division, which for numbers up to 10¹² needs at most about a million divisions and runs instantly.