GCD & LCM

What you need to know

• For positive integers $a, b$: $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab$. This extends to prime exponents: $\gcd$ takes the minimum exponent of each prime, $\operatorname{lcm}$ the maximum.
• Euclidean algorithm: $\gcd(a, b) = \gcd(b, a \bmod b)$; more generally $\gcd(a, b) = \gcd(a, b - ka)$ for any integer $k$.
• If $\gcd(a, b) = g$, then $a = gx$, $b = gy$ with $\gcd(x, y) = 1$, and $\operatorname{lcm}(a, b) = gxy$.
• $\gcd(a, b) = 1$ is called relatively prime (coprime). Consecutive integers are always coprime.
• $\operatorname{lcm}(a_1, \ldots, a_k)$ is the smallest positive integer divisible by all $a_i$; it is the period of anything that repeats with periods $a_1, \ldots, a_k$.
• The count of $n \le N$ coprime to a fixed $m$ can be found by inclusion–exclusion over the primes of $m$.

How AMC 10 tests it

• Word problems in disguise: events with periods $3, 4, 6, 7$ days coincide every $\operatorname{lcm}$ days; tiles or fence posts use $\gcd$.
• "Given $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$, how many pairs $(a,b)$?" or "what is $a + b$?" (usually problems 12–18).
• $\gcd$ of two large or symbolic numbers, such as $\gcd(2^{30}-1, 2^{18}-1)$ or $\gcd(n^2 + 1, n + 1)$, meant to be simplified by the Euclidean algorithm.
• Fractions in lowest terms: $\frac{a}{b}$ reduced has denominator $b/\gcd(a,b)$; count numerators with a given reduced denominator.

Standard approaches

1. Factor both numbers and take min/max exponents; this settles any concrete $\gcd$/$\operatorname{lcm}$ instantly.
2. For symbolic or huge inputs, subtract multiples: $\gcd(n^2+1, n+1) = \gcd(2, n+1)$.
3. Substitute $a = gx$, $b = gy$ with $\gcd(x,y) = 1$; the problem becomes a coprime-pair count.
4. Use $ab = \gcd \cdot \operatorname{lcm}$ whenever three of the four quantities are known.
5. For coprime ordered pairs with product $m$, each prime power of $m$ goes entirely to one side: $2^{\omega(m)}$ pairs, where $\omega(m)$ is the number of distinct primes.

Worked example

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

(A) $4$ (B) $6$ (C) $8$ (D) $12$ (E) $16$

Write $a = 6x$ and $b = 6y$ with $\gcd(x, y) = 1$. Then $\operatorname{lcm}(a, b) = 6xy = 360$, so $xy = 60 = 2^2 \cdot 3 \cdot 5$. Because $x$ and $y$ are coprime, each prime power $2^2$, $3$, $5$ must go entirely to $x$ or entirely to $y$: that is $2^3 = 8$ choices, giving the ordered pairs $(x, y) = (1, 60), (4, 15), (3, 20), (5, 12)$ and their reverses. Each yields a valid $(a, b)$, for example $(24, 90)$. The answer is $\boxed{\textbf{(C)}\ 8}$.

Pitfalls

• Using $\gcd \cdot \operatorname{lcm} =$ product for three or more numbers; the identity holds only for two.
• Forgetting the coprimality condition after factoring out $g$, which overcounts pairs.
• Confusing ordered and unordered pairs; $(a, b)$ and $(b, a)$ count separately unless stated otherwise.
• Reducing $\gcd(a, b)$ by subtracting the wrong direction, e.g., replacing $a$ with $a - b$ when $b > a$ and losing track of signs.

Traps that recur

• Accepting statement I by analogy with II without testing it; a = 1, b = 3 gives c = 57, which is divisible by 3. (2023 AMC 10B #18)
• Stopping at the first n > 1000 satisfying the divisibility parts (n = 1077, digit sum 15) without checking that the gcds are exactly 21 and 60. (2020 AMC 10A #24)
• Assuming gcd(d,a) is just some multiple of 6 and picking 72, 84, 90 or 96, which would force extra factors of 2 or 3 that contradict the given gcds. (2018 AMC 10A #22)
• Forgetting that x and y must be coprime, so that xy = 9 wrongly admits (3,3) (which has gcd 63, not 21) and yields 3 ordered pairs instead of 2. (2018 AMC 10B #23)