2020 AMC 10A Problem 24

Translate each gcd. $\gcd(63, n + 120) = 21$ with $63 = 3^2 \cdot 7$ means $21 \mid n + 120$ but $9 \nmid n + 120$. $\gcd(n + 63, 120) = 60$ with $120 = 2^3 \cdot 15$ means $60 \mid n + 63$ but $8 \nmid n + 63$.

Divisibility parts: $n \equiv -120 \equiv 6 \pmod{21}$ and $n \equiv -63 \equiv 57 \pmod{60}$. Write $n = 57 + 60k$; then $57 + 60k \equiv 15 + 18k \equiv 6 \pmod{21}$, so $18k \equiv 12 \pmod{21}$, i.e. $6k \equiv 4 \pmod 7$, giving $k \equiv 3 \pmod 7$. So $n \equiv 57 + 180 = 237 \pmod{420}$.

Candidates above $1000$: $1077, 1497, 1917, \dots$. Check the exclusions:

• $n = 1077$: $n + 120 = 1197$, digit sum $18$, divisible by $9$. Then $\gcd(63, 1197) = 63$. Rejected.
• $n = 1497$: $n + 120 = 1617$ (digit sum $15$, fine), but $n + 63 = 1560 = 8 \cdot 195$, so $\gcd(1560, 120) = 120$. Rejected.
• $n = 1917$: $n + 120 = 2037$, digit sum $12$, not divisible by $9$; $n + 63 = 1980$, and $980 = 8 \cdot 122.5$ is not a multiple of $8$. Both gcds are exactly $21$ and $60$. Accepted.

Digit sum of $1917$: $1 + 9 + 1 + 7 = 18$.

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

"$\gcd(a, b) = d$" is two statements: $d$ divides $b$, and the extra prime power in $a$ beyond $d$ does not. The divisibility parts combine into a single congruence mod $\operatorname{lcm}(21, 60) = 420$, producing a short list of candidates; the exclusion parts then act as a filter. With only three candidates to test, the filter is faster than encoding it algebraically.

• 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.
• Checking "not divisible by $9$" but forgetting "not divisible by $8$," which accepts $1497$ (digit sum $21$, choice (D)).