Skip to main content

2020 AMC 10A Problem 24

Problem 24 of 25HarderNumber Theory

Let nn be the least positive integer greater than 10001000 for which gcd⁡(63,n+120)=21andgcd⁡(n+63,120)=60. \begin{gathered} \gcd(63,n+120)=21\\ \text{and}\\ \gcd(n+63,120)=60. \end{gathered} What is the sum of the digits of n?n?

Answer choices

Show solution

Solution

The first gcd condition gives n+120≡0(mod21)n+120\equiv0\pmod{21}, so n≡6(mod21)n\equiv6\pmod{21}, but n+120n+120 must not be divisible by 6363. The second gives n+63≡0(mod60)n+63\equiv0\pmod{60}, so n≡57(mod60)n\equiv57\pmod{60}, but n+63n+63 must not be divisible by 120120. Solving n≡6(mod21)n\equiv6\pmod{21} and n≡57(mod60)n\equiv57\pmod{60} gives n≡237(mod420)n\equiv237\pmod{420}. The candidates above 10001000 are 1077,1497,1917,…1077,1497,1917,\ldots. The first fails the first gcd condition, the second fails the second gcd condition, and 19171917 works. The digit sum is 1818. Thus, C is the correct answer.
AoPS wiki

Tagged: greatest common divisor · Chinese Remainder Theorem · modular arithmetic

More practice