The GCD (greatest common divisor, also called the greatest common factor) is the largest integer that divides every given number with no remainder. The LCM (least common multiple) is the smallest positive integer that is a multiple of all of them at once. Both show up constantly: adding fractions with different denominators needs the LCM; reducing a fraction to lowest terms needs the GCD; problems about things that repeat in cycles need the LCM; problems about splitting into equal parts need the GCD.

There are three methods, and each one is the fastest in a different situation. It pays to know all three and pick by the size of the numbers.

The idea behind it: prime factors

Every integer greater than 1 can be written in exactly one way as a product of primes (the fundamental theorem of arithmetic). Think of the primes as building blocks. A divisor of a number can only use blocks the number has, and no more copies than it has. A multiple must contain at least all of the number’s blocks.

That gives the two rules. To divide every number, the GCD may only use primes that appear in all of them, with at most the smallest exponent. To be a multiple of every number, the LCM needs every prime that appears, each with the largest exponent.

25221262633213771252 = 2² · 3² · 7
Factoring 252 with the ladder: 252 = 2² · 3² · 7

Method 1: prime factorization

Break each number into primes and compare exponents.

  • GCD: product of the shared primes, each with the smallest exponent.
  • LCM: product of all primes that appear, each with the largest exponent.

With 12 and 18: 12 = 2² · 3 and 18 = 2 · 3². The GCD takes 2¹ · 3¹ = 6. The LCM takes 2² · 3² = 36. Check: 6 × 36 = 216 and 12 × 18 = 216.

Method 2: the ladder (simultaneous division)

Write the numbers side by side and divide all of them by primes in increasing order, in one table, until every column reaches 1. When a prime doesn’t divide some number, that number is simply copied down.

NumbersPrime divisor
12, 18, 302 (divides all)
6, 9, 152
3, 9, 153 (divides all)
1, 3, 53
1, 1, 55
1, 1, 1done

The LCM is the product of all the divisors: 2 · 2 · 3 · 3 · 5 = 180. The GCD is the product of only the divisors that divided every number in the same row: 2 · 3 = 6. This is the handiest method for three or more small numbers.

Method 3: the Euclidean algorithm

With big numbers, factoring is slow. Euclid relies on a simple fact: if r is the remainder of a divided by b, then the common divisors of a and b are exactly those of b and r. So:

gcd⁡(a,b)=gcd⁡(b, r),a=q⋅b+r\gcd(a, b) = \gcd(b,\ r), \quad a = q \cdot b + r

Keep dividing until the remainder is zero; the last divisor you used is the GCD. Example: 84 = 2 × 36 + 12, then 36 = 3 × 12 + 0. The remainder hit zero, so gcd(84, 36) = 12.

Shortcut: the LCM from the GCD

For two positive numbers, the LCM times the GCD equals the product of the numbers. So once Euclid gives you the GCD, the LCM is one calculation away:

lcm⁡(a,b)=a⋅bgcd⁡(a,b)\operatorname{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}

With 84 and 36: 84 × 36 = 3,024, and 3,024 ÷ 12 = 252. Tip: divide before you multiply (84 ÷ 12 = 7 and 7 × 36 = 252) to keep the numbers small.

Worked example: a 252 cm by 198 cm floor

A rectangular floor measures 252 cm by 198 cm and will be covered with identical square tiles, as large as possible, with no tile cut. What is the side of each tile, and how many tiles are needed?

  1. Name what is asked. The side must fit a whole number of times along both sides of the floor: it is a common divisor. The largest one is the GCD.
  2. Run Euclid. 252 = 1 × 198 + 54; 198 = 3 × 54 + 36; 54 = 1 × 36 + 18; 36 = 2 × 18 + 0. The last divisor is 18, so gcd(252, 198) = 18.
  3. Cross-check with factoring. 252 = 2² · 3² · 7 and 198 = 2 · 3² · 11. Shared primes with the smallest exponent: 2 · 3² = 18. It matches.
  4. Count the tiles. Along one side fit 252 ÷ 18 = 14 tiles; along the other, 198 ÷ 18 = 11. Total: 14 × 11 = 154 tiles of 18 cm.
  5. Check. 14 and 11 share no divisor other than 1, so no larger tile works. And by the shortcut, lcm(252, 198) = 252 × 198 ÷ 18 = 2,772; indeed 2,772 = 2² · 3² · 7 · 11, which uses every prime with its largest exponent. The product 18 × 2,772 = 49,896 equals 252 × 198 = 49,896.

Typical problems: which one to use

Cycles lining up call for the LCM. Two buses leave together at 8:00 a.m., one every 12 minutes and the other every 18. Each bus’s departure times are multiples of its interval, and they line up again at the first common multiple: lcm(12, 18) = 36. They leave together again at 8:36 a.m.

Splitting into equal parts calls for the GCD. Two ribbons of 84 cm and 36 cm will be cut into equal pieces, as long as possible, with nothing left over. The length is gcd(84, 36) = 12 cm, and the number of pieces is 84 ÷ 12 + 36 ÷ 12 = 7 + 3 = 10.

Fractions call for the LCM of the denominators. To add 5/12 + 7/18, the least common denominator is lcm(12, 18) = 36: 5/12 = 15/36 and 7/18 = 14/36, so the sum is 29/36.

Common mistakes

  1. Putting primes that are not shared into the GCD. With 12 = 2² · 3 and 20 = 2² · 5, neither 3 nor 5 goes into the GCD; it is 2² = 4.
  2. Swapping the exponents. The GCD uses the smallest, the LCM the largest. Swapping them gives numbers that don’t divide or aren’t multiples.
  3. Using lcm · gcd = a · b with three numbers. The identity only holds for two. With 2, 4 and 8, the LCM is 8 and the GCD is 2, and 8 × 2 = 16, far from 2 × 4 × 8 = 64.
  4. In the ladder, multiplying every divisor for the GCD. Only the rows where the prime divided all the numbers count.
  5. Mixing up what the problem wants. Ask yourself: do I want a number that fits into all of them (GCD, smaller than the data) or one that contains all of them (LCM, larger than the data)? The GCD is never above the smallest number; the LCM is never below the largest.

Frequently asked questions

When do I use the LCM and when the GCD in word problems?

Use the LCM when events repeat and you want to know when they coincide, or when you need a common denominator. Use the GCD when you want to split quantities into equal parts as large as possible.

What is the GCD of two coprime numbers?

It is 1, by definition. In that case the LCM is their product, as in lcm(8, 15) = 120.

Does lcm · gcd = a · b hold for three numbers?

Not in general. For 2, 4 and 8, the LCM is 8 and the GCD is 2, with product 16, but 2 · 4 · 8 = 64.

Which method is fastest?

For small numbers, the ladder gives the LCM and the GCD in one go. For two large numbers, Euclid finds the GCD in a few divisions and the LCM follows from a · b ÷ gcd.