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+1200(mod21)n+120\equiv0\pmod{21}, so n6(mod21)n\equiv6\pmod{21}, but n+120n+120 must not be divisible by 6363. The second gives n+630(mod60)n+63\equiv0\pmod{60}, so n57(mod60)n\equiv57\pmod{60}, but n+63n+63 must not be divisible by 120120. Solving n6(mod21)n\equiv6\pmod{21} and n57(mod60)n\equiv57\pmod{60} gives n237(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.

More practice

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

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.