GCD & LCM

What you need to know

• gcd times lcm. The gcd (greatest common divisor) is the biggest number dividing both $a$ and $b$; the lcm (least common multiple) is the smallest positive number both divide. For positive integers, $\gcd(a,b)\cdot\text{lcm}(a,b) = a\cdot b$.
• With prime factorizations, the gcd takes the smaller exponent of each prime and the lcm takes the larger. Example: $24 = 2^3\cdot3$ and $90 = 2\cdot3^2\cdot5$ have gcd $2\cdot3 = 6$ and lcm $2^3\cdot3^2\cdot5 = 360$, and $6\cdot360 = 24\cdot90 = 2160$.
• Euclidean Algorithm. $\gcd(a,b) = \gcd(b,r)$, where $r$ is the remainder when $a$ is divided by $b$. Repeat until the remainder is $0$. Example: $\gcd(252,105) = \gcd(105,42) = \gcd(42,21) = \gcd(21,0) = 21$.
• Subtracting multiples. More generally, $\gcd(a,b) = \gcd(a,b-ka)$ for any integer $k$, because a number that divides $a$ and $b$ also divides $b-ka$, and the other way round. Example: $\gcd(35,91) = \gcd(35,91-2\cdot35) = \gcd(35,21) = 7$.
• Pulling out the gcd. If $\gcd(a,b) = g$, write $a = gx$ and $b = gy$. Then $x$ and $y$ share no factor except $1$, and $\text{lcm}(a,b) = gxy$. Example: $24 = 6\cdot4$ and $90 = 6\cdot15$, so the lcm is $6\cdot4\cdot15 = 360$.
• Relatively prime (or coprime) means the gcd is $1$. Consecutive integers are always relatively prime, since a common divisor would also divide their difference, $1$.
• Things that repeat. $\text{lcm}(a_1, \dots, a_k)$ is the smallest positive number that all of $a_1, \dots, a_k$ divide. So things that repeat every $a_1$, …, $a_k$ days all line up again every lcm days. Example: buses every $4$, $6$, and $10$ minutes leave together every $\text{lcm}(4,6,10) = 60$ minutes.
• Counting numbers relatively prime to $m$. For the numbers from $1$ to $N$, use the Principle of Inclusion-Exclusion (PIE) on the primes of $m$. Example: from $1$ to $30 = 2\cdot3\cdot5$: $30-(15+10+6)+(5+3+2)-1 = 8$.

How AMC 10 tests it

• Word problems in disguise: events with periods of $3$, $4$, $6$, $7$ days line up every lcm days; tiles or fence posts use the gcd.
• "Given $\gcd(a,b)$ and $\text{lcm}(a,b)$, how many pairs $(a,b)$?" or "what is $a+b$?" (usually problems 12–18).
• The gcd of huge numbers or expressions, such as $\gcd(2^{30}-1, 2^{18}-1)$ or $\gcd(n^2+1, n+1)$, meant to be simplified with the Euclidean Algorithm.
• Fractions in lowest terms: $\frac{a}{b}$ reduces to denominator $\frac{b}{\gcd(a,b)}$; count the numerators that give a certain reduced denominator.

Standard approaches

1. Factor both numbers and take the smaller or larger exponent of each prime. This settles any gcd or lcm of actual numbers.
2. For expressions or huge numbers, subtract multiples. Example: $n^2+1 = (n+1)(n-1)+2$, so $\gcd(n^2+1, n+1) = \gcd(2, n+1)$: $2$ if $n$ is odd, $1$ if $n$ is even. Likewise $2^{30}-1-2^{12}(2^{18}-1) = 2^{12}-1$, and continuing gives $\gcd(2^{30}-1, 2^{18}-1) = 2^6-1 = 63$.
3. Write $a = gx$ and $b = gy$ with $\gcd(x,y) = 1$; the problem becomes counting relatively prime pairs.
4. Use $ab = \gcd\cdot\text{lcm}$ whenever three of the four are known. Example: if $\gcd(a,12) = 4$ and $\text{lcm}(a,12) = 48$, then $a = \frac{4\cdot48}{12} = 16$.
5. For ordered pairs of relatively prime numbers with product $m$, each prime power of $m$ goes entirely to one side. If $m$ has $k$ different prime factors, that gives $2^k$ pairs. Example: $12 = 2^2\cdot3$ gives $2^2 = 4$ pairs: $(1,12)$, $(4,3)$, $(3,4)$, $(12,1)$.

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$

Step 1: pull out the gcd. Write $a = 6x$ and $b = 6y$. Then $x$ and $y$ share no factor except $1$; otherwise the gcd would be bigger than $6$.

Step 2: use the lcm. $\text{lcm}(a,b) = 6xy = 360$, so $xy = 60 = 2^2\cdot3\cdot5$.

Step 3: split the primes. Since $x$ and $y$ share no factor, each of $2^2 = 4$, $3$, and $5$ goes entirely to $x$ or entirely to $y$. (If each got one $2$, both would be even.) That is $2^3 = 8$ choices: $(x,y) = (1,60)$, $(4,15)$, $(3,20)$, $(5,12)$, and these four reversed.

Step 4: check one. $(4,15)$ gives $(a,b) = (24,90)$, with gcd $6$ and lcm $360$.

The answer is $\boxed{\textbf{(C)}\ 8}$.

Pitfalls

• Using "gcd $\times$ lcm $=$ product" for three or more numbers; it holds only for two. Example: for $2$, $4$, $8$, gcd $\times$ lcm $= 2\cdot8 = 16$, but the product is $64$.
• Forgetting that $x$ and $y$ must share no factor after you pull out $g$, which overcounts. Example: above, $(x,y) = (2,30)$ gives $(a,b) = (12,180)$, whose gcd is $12$, not $6$.
• Mixing up ordered and unordered pairs; $(a,b)$ and $(b,a)$ count separately unless the problem says otherwise.
• Subtracting the wrong way in the Euclidean Algorithm, such as replacing $a$ with $a-b$ when $b$ is bigger, and losing track of minus signs. Subtract the smaller from the larger.

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)