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.

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