2018 AMC 10A Problem 22

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}$.

A gcd is computed prime by prime using minimum exponents, so a chain of gcd conditions is really a set of inequalities on exponents. Whenever two consecutive gcds show different exponents for the same prime, the shared variable must carry the larger one and the other variable is pinned exactly. The numerical window $70$ to $100$ then leaves exactly one candidate once the forbidden extra factors of $2$ and $3$ are ruled out.

• 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.
• Concluding only that $\gcd(d,a)$ is divisible by $6$ (true) without pinning the exponents exactly, so that $72 = 2^3 \cdot 3^2$ is wrongly left as a candidate.