AMC10 2020 A

AMC10 2020 A · Q24

AMC10 2020 A · Q24. It mainly tests GCD & LCM, Chinese remainder / simultaneous congruences (basic).

Let $n$ be the least positive integer greater than 1000 for which $\gcd(63, n + 120) = 21$ and $\gcd(n + 63, 120) = 60$. What is the sum of the digits of $n$?

让 $n$ 为大于 1000 的最小正整数，使得 $\gcd(63, n + 120) = 21$ 且 $\gcd(n + 63, 120) = 60$。$n$ 的各位数字之和是多少？

(A) 12 12

(B) 15 15

(D) 21 21

(E) 24 24

Answer

Correct choice: (C)

正确答案：（C）

Solution

Answer (C): The condition $\gcd(n+63,120)=60$ is true if and only if $n+63$ is divisible by $60$ but not $120$, which is equivalent to $n \equiv 57 \pmod{60}$ and $n \equiv 117 \pmod{120}.$ Similarly, the condition $\gcd(63,n+120)=21$ is true if and only if $n+120$ is divisible by $21$ but not $63$, which is equivalent to $n \equiv 6 \pmod{21}$ and $n \equiv 27 \text{ or } 48 \pmod{63}.$ From the congruences $n \equiv 117 \pmod{120}$ and $n \equiv 6 \pmod{21}$ it follows that $n \equiv 237 \pmod{840}$. Thus $n=237+840k$ for some integer $k$, and because $n$ was specified to be greater than $1000$, $k$ must be at least $1$. The condition $n \equiv 57 \pmod{60}$ holds for all such $n$. However, the condition $n \equiv 27$ or $48 \pmod{63}$ does not hold when $k=1$ and $n=1077$, but it does hold when $k=2$ and $n=1917$. The requested sum of digits of $n$ is $1+9+1+7=18$.

答案（C）：条件$\gcd(n+63,120)=60$当且仅当$n+63$能被$60$整除但不能被$120$整除，这等价于 $n \equiv 57 \pmod{60}$ 以及 $n \equiv 117 \pmod{120}.$ 同理，条件$\gcd(63,n+120)=21$当且仅当$n+120$能被$21$整除但不能被$63$整除，这等价于 $n \equiv 6 \pmod{21}$ 以及 $n \equiv 27 \text{ 或 } 48 \pmod{63}.$ 由同余式$n \equiv 117 \pmod{120}$和$n \equiv 6 \pmod{21}$可得$n \equiv 237 \pmod{840}$。因此对某个整数$k$，有$n=237+840k$。又因题目指定$n>1000$，所以$k\ge 1$。对所有这样的$n$，条件$n \equiv 57 \pmod{60}$都成立。然而，当$k=1$且$n=1077$时，条件$n \equiv 27$或$48 \pmod{63}$不成立；但当$k=2$且$n=1917$时成立。所求$n$的各位数字和为$1+9+1+7=18$。

Topics