Ultimate Calculator
Math guide

GCF and LCM explained

Find the greatest common factor and least common multiple by listing, prime factorization or Euclid's algorithm, with worked examples.

The greatest common factor (GCF) of two numbers is the largest number that divides both exactly. The least common multiple (LCM) is the smallest number that both divide into exactly. For 12 and 18, the GCF is 6 and the LCM is 36.

The GCF is also called the greatest common divisor (GCD) or highest common factor (HCF). They all mean the same thing.

Method 1: listing

For small numbers, write out the factors or multiples and compare.

GCF of 12 and 18.

  • Factors of 12: 1, 2, 3, 4, 6, 12
  • Factors of 18: 1, 2, 3, 6, 9, 18

The common factors are 1, 2, 3 and 6. The greatest is 6.

LCM of 12 and 18.

  • Multiples of 12: 12, 24, 36, 48, ...
  • Multiples of 18: 18, 36, 54, ...

The first number on both lists is 36.

Method 2: prime factorization

Break each number into prime factors. Then:

  • For the GCF, take each prime that appears in every number, using the lowest power.
  • For the LCM, take each prime that appears in any number, using the highest power.

Worked example: 48 and 180.

  • 48 = 2⁴ × 3
  • 180 = 2² × 3² × 5
PrimePower in 48Power in 180GCF uses (lowest)LCM uses (highest)
2422²2⁴
31233²
501not included5

GCF = 2² × 3 = 12. LCM = 2⁴ × 3² × 5 = 16 × 9 × 5 = 720.

If you need the factorizations, the prime factorization calculator produces them for any whole number.

Method 3: Euclid's algorithm

For large numbers, factoring is slow. Euclid's algorithm finds the GCF using only division with remainders. It relies on the fact that any number dividing both a and b also divides the remainder when a is divided by b.

  1. Divide the larger number by the smaller and note the remainder.
  2. Replace the larger number with the smaller, and the smaller with the remainder.
  3. Repeat until the remainder is 0. The last nonzero remainder is the GCF.

Worked example: GCF of 1,071 and 462.

  • 1,071 ÷ 462 = 2 remainder 147
  • 462 ÷ 147 = 3 remainder 21
  • 147 ÷ 21 = 7 remainder 0

The GCF is 21.

The same steps on 180 and 48 give remainders 36, 12 and 0, so the GCF is 12, matching the prime factorization method.

Getting the LCM from the GCF

For any two positive whole numbers, the GCF times the LCM equals the product of the numbers. So once you have the GCF, the LCM takes one more step.

LCM(a, b) = a × b ÷ GCF(a, b)
  • LCM(48, 180) = 48 × 180 ÷ 12 = 8,640 ÷ 12 = 720.
  • LCM(1,071, 462) = 1,071 × 462 ÷ 21 = 1,071 × 22 = 23,562.

The GCF and LCM calculator does both in one pass and accepts more than two numbers.

More than two numbers

Work in pairs. To find the GCF of 12, 18 and 30, first GCF(12, 18) = 6, then GCF(6, 30) = 6. For the LCM, first LCM(12, 18) = 36, then LCM(36, 30) = 180.

The product shortcut works only for two numbers at a time. 12 × 18 × 30 ÷ 6 is 1,080, which is not the LCM.

What they are used for

  • Simplifying fractions (GCF). Divide the top and bottom by their GCF. 48/180 simplifies by 12 to 4/15.
  • Common denominators (LCM). To add 5/12 + 7/18, use the LCM of 36: 15/36 + 14/36 = 29/36. The fraction calculator does this automatically.
  • Repeating schedules (LCM). One bus leaves every 12 minutes and another every 18. If they leave together now, they next leave together in 36 minutes.
  • Equal groups and tiling (GCF). The largest square tile that exactly covers a 48 cm by 180 cm panel has a 12 cm side. You would need 4 × 15 = 60 tiles.

Special cases

  • If the GCF is 1, the numbers are called coprime, and their LCM is simply their product. For 8 and 15, the GCF is 1 and the LCM is 120.

Common mistakes

  • Mixing up the two. The GCF is never larger than the smaller number. The LCM is never smaller than the larger number.
  • Swapping lowest and highest powers. Lowest shared powers give the GCF. Highest powers give the LCM.
  • Including unshared primes in the GCF. The 5 in 180 does not belong in the GCF of 48 and 180.
  • Assuming the LCM is the product. 12 × 18 = 216 is a common multiple, but the least one is 36.
  • Stopping Euclid's algorithm too early. Continue until the remainder is 0, then take the previous remainder.

Common questions

What is the difference between GCF and LCM?

The GCF is the largest number that divides all the given numbers, while the LCM is the smallest number that all of them divide into. For 12 and 18 the GCF is 6 and the LCM is 36.

How does Euclid’s algorithm work?

Divide the larger number by the smaller, then repeat with the smaller number and the remainder until the remainder is zero. The last nonzero remainder is the GCF.

How do I find the LCM if I know the GCF?

Multiply the two numbers and divide by their GCF. For 48 and 180, 48 × 180 ÷ 12 = 720.