2018 AMC 10A Problem 22

The greatest common divisor (gcd) of two numbers takes each prime as many times as the number with fewer copies of it has. So follow the primes $2$ and $3$ around the chain $a, b, c, d$.

1. Break the gcds into primes.
$$24 = 2^3 \cdot 3, \qquad 36 = 2^2 \cdot 3^2, \qquad 54 = 2 \cdot 3^3.$$
2. Follow the $2$s.
- $\gcd(a, b) = 24$ has three $2$s, so $a$ and $b$ each have at least three $2$s.
- $\gcd(b, c) = 36$ has only two $2$s. Since $b$ has at least three, $c$ must have exactly two.
- $\gcd(c, d) = 54$ has only one $2$. Since $c$ has two, $d$ must have exactly one.
- So $d$ has exactly one $2$ and $a$ has at least three. Their gcd has exactly one $2$.
3. Follow the $3$s.
- $\gcd(b, c) = 36$ has two $3$s, so $b$ has at least two.
- $\gcd(a, b) = 24$ has only one $3$. Since $b$ has at least two, $a$ must have exactly one.
- $\gcd(c, d) = 54$ has three $3$s, so $d$ has at least three.
- So $a$ has exactly one $3$ and $d$ has at least three. Their gcd has exactly one $3$.
4. So $\gcd(d, a) = 6 \times (\text{a number with no factor } 2 \text{ or } 3)$. Check the multiples of $6$ between $70$ and $100$:

Only $78 = 6 \cdot 13$ is allowed.
5. Conclude. $\gcd(d, a) = 78$ divides $a$, so $13$ divides $a$.

Such numbers really exist, for example $a = 312$, $b = 72$, $c = 108$, $d = 702$.

The answer is $\boxed{\textbf{(D)}\ 13}$.

A gcd works one prime at a time: it keeps the smaller count of each prime. When two gcds next to each other in the chain disagree about how many $2$s (or $3$s) there are, the number they share has the larger count and the other number is pinned down exactly. Once the counts of $2$ and $3$ are fixed, the range $70$ to $100$ leaves only one choice.

Factor the given gcds: $24 = 2^3 \cdot 3$, $36 = 2^2 \cdot 3^2$, $54 = 2 \cdot 3^3$. The gcd's exponent of a prime is the smaller of the two exponents, so track $2$ and $3$ through the chain $a, b, c, d$.

Powers of $2.$ $\gcd(a,b)$ has $2^3$ but $\gcd(b,c)$ has only $2^2$, so $b$ has at least $2^3$ and $c$ has exactly $2^2$. Then $\gcd(c,d)$ having $2^1$ forces $d$ to have exactly $2^1$. Meanwhile $a$ has at least $2^3$. So $\gcd(d,a)$ has exactly $2^1$.

Powers of $3.$ $\gcd(b,c)$ has $3^2$ but $\gcd(a,b)$ has only $3^1$, so $b$ has at least $3^2$ and $a$ has exactly $3^1$. Also $\gcd(c,d) = 3^3$ means $d$ has at least $3^3$. So $\gcd(d,a)$ has exactly $3^1$.

Hence $\gcd(d,a) = 6k$ with $k$ coprime to $6$. The multiples of $6$ strictly between $70$ and $100$ are $72, 78, 84, 90, 96$, and dividing by $6$ gives $12, 13, 14, 15, 16$. Only $13$ is coprime to $6$, so $\gcd(d,a) = 78 = 2 \cdot 3 \cdot 13$, and $13$ divides $a$.

(Such numbers exist, e.g. $a = 2^3 \cdot 3 \cdot 13$, $b = 2^3 \cdot 3^2$, $c = 2^2 \cdot 3^3$, $d = 2 \cdot 3^3 \cdot 13$.)

The answer is $\boxed{\textbf{(D)}\ 13}$.