LCM and GCD: fast methods (prime factorization, ladder and Euclid)

The GCD (greatest common divisor) is the largest integer that divides all the given numbers. The LCM (least common multiple) is the smallest positive integer that is a multiple of all of them. Both show up in fractions, repeating-event problems and splitting into equal parts.

Method 1: prime factorization

Break each number into prime factors.

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

Worked example: 12 and 18

1. $12 = 2^2 \cdot 3$ and $18 = 2 \cdot 3^2$.
2. $\text{gcd} = 2^1 \cdot 3^1 = 6$.
3. $\text{lcm} = 2^2 \cdot 3^2 = 36$.
4. Check: $6 \cdot 36 = 216 = 12 \cdot 18$.

Method 2: the ladder (simultaneous division)

Divide all the numbers by primes in order, in one table, until every entry is 1. The product of all divisors is the LCM; the product of the divisors that divided every number at once is the GCD.

Worked example: 12, 18 and 30

1. $\text{lcm} = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 180$.
2. $\text{gcd} = 2 \cdot 3 = 6$.

Method 3: the Euclidean algorithm

For large numbers, factoring is slow. Euclid uses the fact that $\text{gcd}(a, b) = \text{gcd}(b, r)$, where $r$ is the remainder of $a \div b$. Repeat until the remainder is zero; the last divisor is the GCD.

Worked example: gcd(84, 36)

1. $84 = 2 \cdot 36 + 12$.
2. $36 = 3 \cdot 12 + 0$.
3. The remainder is zero: $\text{gcd}(84, 36) = 12$.

Shortcut: the LCM from the GCD

For two positive numbers:

With the previous example: $\text{lcm}(84, 36) = \dfrac{84 \cdot 36}{12} = 7 \cdot 36 = 252$.

Typical word problems

Worked example: two buses leave together at 8:00, one every 12 minutes and the other every 18 minutes. When do they leave together again?

1. Repeating events that coincide: LCM.
2. $\text{lcm}(12, 18) = 36$.
3. They leave together again at 8:36.

Worked example: ribbons of 84 cm and 36 cm must be cut into equal pieces, as long as possible, with nothing left over. How long is each piece, and how many pieces are there?

1. Largest equal part that divides both: GCD.
2. $\text{gcd}(84, 36) = 12$ cm.
3. Pieces: $84 \div 12 + 36 \div 12 = 7 + 3 = 10$.

Common mistakes

1. Including primes in the GCD that are not shared by every number.
2. Using $\text{lcm} \cdot \text{gcd} = a \cdot b$ with three or more numbers.
3. Mixing up which one the problem asks for: coincidence calls for the LCM; equal parts call for the GCD.