2020 AMC 10A Problem 24

Each gcd condition contains a "must divide" part and a "must not go further" part. Use the first parts to list candidates, then use the second parts to throw candidates out.

1. First condition. $63 = 3 \times 3 \times 7$. For $\gcd(63, n + 120)$ to be exactly $21 = 3 \times 7$, the number $n + 120$ must be a multiple of $21$ but not a multiple of $9$ (otherwise the gcd would be $63$).
2. Second condition. $120 = 8 \times 15$ and $60 = 4 \times 15$. For $\gcd(n + 63, 120)$ to be exactly $60$, the number $n + 63$ must be a multiple of $60$ but not a multiple of $8$ (otherwise the gcd would be $120$).
3. List numbers with $n + 63$ a multiple of $60$. Then $n$ is $60 - 63 = -3$ plus a multiple of $60$, so $n = 57, 117, 177, 237, \ldots$ (each $60$ more than the last).
4. Which of these make $n + 120$ a multiple of $21$? Check them: $57 + 120 = 177$ (no), $117 + 120 = 237$ (no), $177 + 120 = 297$ (no), $237 + 120 = 357 = 21 \times 17$ (yes). So $n = 237$ works for both "divides" parts.
5. The pattern repeats every $420$. Adding $420$ keeps $n + 63$ a multiple of $60$ and $n + 120$ a multiple of $21$, since $420 = 60 \times 7 = 21 \times 20$. And $420$ is the smallest step that does both. So the candidates above $1000$ are $237 + 840 = 1077$, then $1497$, then $1917$, and so on.
6. Test the "not further" parts.
- $n = 1077$: $n + 120 = 1197$. Its digits add to $18$, so it is a multiple of $9$. The gcd would be $63$. Throw it out.
- $n = 1497$: $n + 120 = 1617$, digits add to $15$, fine. But $n + 63 = 1560 = 8 \times 195$, a multiple of $8$. The gcd would be $120$. Throw it out.
- $n = 1917$: $n + 120 = 2037$, digits add to $12$, not a multiple of $9$. Good. $n + 63 = 1980$, and $1980 \div 8 = 247.5$, not a whole number. Good. So $n = 1917$.
7. The digits of $1917$ add to $1 + 9 + 1 + 7 = 18$.

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

"The gcd is exactly $d$" means $d$ divides the number, and the extra prime factors that would make the gcd bigger do not. The "divides" parts combine into one repeating list of candidates; the "does not divide" parts are easiest to use as a final check on just a few candidates.