Math Core

Two buses leave the station together, one every $12$ minutes and one every $18$ . When do they leave together again? A rectangle must be cut into the largest possible equal squares. How big are the squares? The first question asks for a least common multiple and the second for a greatest common divisor. Contest writers disguise these two ideas in many costumes.

Definitions

Definition

GCD and LCM

The greatest common divisor $\gcd(a, b)$ is the largest whole number that divides both $a$ and $b$ . (MATHCOUNTS often calls it the greatest common factor, GCF.)

The least common multiple $\operatorname{lcm}(a, b)$ is the smallest positive whole number that is a multiple of both $a$ and $b$ .

Using prime factorizations

Write both numbers as products of primes.

For the GCD, take each common prime to the smaller power.
For the LCM, take every prime that appears to the larger power.

Worked example: Factorization method

Find $\gcd(168, 180)$ and $\operatorname{lcm}(168, 180)$ .

$168 = 2^3 \cdot 3 \cdot 7$ and $180 = 2^2 \cdot 3^2 \cdot 5$ .

GCD: smaller powers of the common primes $2$ and $3$ : $2^2 \cdot 3 = 12$ .
LCM: larger power of every prime: $2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$ .

Notice that $12 \times 2520 = 30{,}240 = 168 \times 180$ . That's not a coincidence. For each prime, the GCD takes one of the two exponents and the LCM takes the other, so together they use every prime factor of $a$ and $b$ exactly once.

The product rule

For any two positive integers, $\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b.$

Common mistake

The product rule works for two numbers only. For three numbers, $\gcd(a,b,c) \cdot \operatorname{lcm}(a,b,c)$ is usually not $abc$ . For example, $\gcd(2,4,8) \cdot \operatorname{lcm}(2,4,8) = 2 \cdot 8 = 16$ , but $2 \cdot 4 \cdot 8 = 64$ .

The Euclidean algorithm

Factoring large numbers is slow. Luckily, any number that divides both $a$ and $b$ also divides $a - b$ . So $\gcd(a, b) = \gcd(b, a - b)$ , and you can subtract (or take remainders) repeatedly until the numbers are small.

Worked example: Euclidean algorithm

Find $\gcd(391, 667)$ .

\begin{aligned} \gcd(391, 667) &= \gcd(391, 276) && 667 - 391 = 276 \\ &= \gcd(115, 276) && 391 - 276 = 115 \\ &= \gcd(115, 46) && 276 = 2 \cdot 115 + 46 \\ &= \gcd(23, 46) && 115 = 2 \cdot 46 + 23 \\ &= 23 && 46 = 2 \cdot 23 \end{aligned}

Indeed, $391 = 17 \cdot 23$ and $667 = 23 \cdot 29$ .

Spotting GCD vs. LCM in word problems

"Together again," "at the same time," "repeating cycles" point to the LCM.
"Largest equal groups," "biggest square tiles," "cut into equal pieces with none left over" point to the GCD.

Worked example: Pairs with a given GCD and LCM

How many ordered pairs of positive integers $(a, b)$ have $\gcd(a, b) = 6$ and $\operatorname{lcm}(a, b) = 72$ ?

Write $a = 6x$ and $b = 6y$ where $x$ and $y$ share no common factor. Then $\operatorname{lcm}(a, b) = 6xy = 72$ , so $xy = 12 = 2^2 \cdot 3$ . Since $x$ and $y$ share no prime, the whole $2^2$ goes to one of them and the $3$ goes to one of them. The choices are $(x, y) = (1, 12), (12, 1), (4, 3), (3, 4)$ .

That gives 4 ordered pairs: $(6, 72), (72, 6), (24, 18), (18, 24)$ .

Tip

The trick of writing $a = gx$ , $b = gy$ with $\gcd(x, y) = 1$ turns almost every "given the GCD and LCM" problem into a counting problem about $x$ and $y$ .