AMC10 2022 A

AMC10 2022 A · Q19

AMC10 2022 A · Q19. It mainly tests GCD & LCM, Remainders & modular arithmetic.

Define $L_n$ as the least common multiple of all the integers from $1$ to $n$ inclusive. There is a unique integer $h$ such that \[\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{17}=\frac{h}{L_{17}}\] What is the remainder when $h$ is divided by $17$?

定义 $L_n$ 为从 $1$ 到 $n$ 所有整数的最小公倍数。存在唯一整数 $h$ 使得 \[\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{17}=\frac{h}{L_{17}}\] $h$ 除以 $17$ 的余数是多少？

(A) 1 1

(B) 3 3

(D) 7 7

(E) 9 9

Answer

Correct choice: (C)

正确答案：（C）

Solution

Notice that $L_{17}$ contains the highest power of every prime below $17$ since higher primes cannot divide $L_{17}$. Thus, $L_{17}=16\cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17$. When writing the sum under a common fraction, we multiply the denominators by $L_{17}$ divided by each denominator. However, since $L_{17}$ is a multiple of $17$, all terms will be a multiple of $17$ until we divide out $17$, and the only term that will do this is $\frac{1}{17}$. Thus, the remainder of all other terms when divided by $17$ will be $0$, so the problem is essentially asking us what the remainder of $\frac{L_{17}}{17} = L_{16}$ divided by $17$ is. This is equivalent to finding the remainder of $16 \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13$ divided by $17$. We use modular arithmetic to simplify our answer: This is congruent to $-1 \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \pmod{17}$. Evaluating, we get: \begin{align*} (-1) \cdot 9 \cdot 35 \cdot 11 \cdot 13 &\equiv (-1) \cdot 9 \cdot 1 \cdot 11 \cdot 13 \pmod{17} \\ &\equiv 9 \cdot 11 \cdot (-13) \pmod{17} \\ &\equiv 9 \cdot 11 \cdot 4\pmod{17} \\ &\equiv 2 \cdot 11 \pmod{17} \\ &\equiv 5\pmod{17} \end{align*} Therefore the remainder is $\boxed{\textbf{(C) } 5}$.

注意 $L_{17}$ 包含 $17$ 以下每个质数的最高幂，因为更高的质数不能整除 $L_{17}$。因此，$L_{17}=16\cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17$。将和写成公分母分数时，我们将每个分母乘以 $L_{17}$ 除以该分母。然而，由于 $L_{17}$ 是 $17$ 的倍数，所有项除以 $17$ 前都是 $17$ 的倍数，唯一做到这一点的项是 $\frac{1}{17}$。因此，其他所有项除以 $17$ 的余数为 $0$，问题本质上是求 $\frac{L_{17}}{17} = L_{16}$ 除以 $17$ 的余数，即求 $16 \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13$ 除以 $17$ 的余数。我们使用模运算简化答案：这模 $17$ 合同于 $-1 \cdot 9 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \pmod{17}$。计算得到： \begin{align*} (-1) \cdot 9 \cdot 35 \cdot 11 \cdot 13 &\equiv (-1) \cdot 9 \cdot 1 \cdot 11 \cdot 13 \pmod{17} \\ &\equiv 9 \cdot 11 \cdot (-13) \pmod{17} \\ &\equiv 9 \cdot 11 \cdot 4\pmod{17} \\ &\equiv 2 \cdot 11 \pmod{17} \\ &\equiv 5\pmod{17} \end{align*} 因此余数是 $\boxed{\textbf{(C) } 5}$。

Topics