AMC10 2024 B

AMC10 2024 B · Q18

AMC10 2024 B · Q18. It mainly tests Remainders & modular arithmetic, Powers & residues.

How many different remainders can result when the $100$th power of an integer is divided by $125$?

整数的$100$次幂除以$125$可能得到多少种不同的余数？

(A) 1 1

(B) 2 2

(D) 25 25

(E) 125 125

Answer

Correct choice: (B)

正确答案：（B）

Solution

First note that the Euler's totient function of $125$ is $100$. We can set up two cases, which depend on whether a number is relatively prime to $125.$ If $n$ is relatively prime to $125$, then $n^{100} \equiv 1 \pmod{125}$ because of Euler's Totient Theorem. If $n$ is not relatively prime to $125$, it must have a factor of $5$. Express $n$ as $5m$, where $m$ is some integer. Then $n^{100} \equiv (5m)^{100} \equiv 5^{100}\cdot m^{100} \equiv 125 \cdot 5^{97} \cdot m^{100} \equiv 0 \pmod{125}$. Therefore, $n^{100}$ can only be congruent to $0$ or $1 \pmod{125}$. Our answer is $\boxed{2}$.

首先注意到$125$的欧拉函数是$100$。我们可以分为两种情况，取决于该数是否与$125$互质。如果$n$与$125$互质，则由欧拉定理，$n^{100} \equiv 1 \pmod{125}$。如果$n$与$125$不互质，则它必有$5$的因子。将$n$表示为$5m$，其中$m$是某个整数。然后$n^{100} \equiv (5m)^{100} \equiv 5^{100}\cdot m^{100} \equiv 125 \cdot 5^{97} \cdot m^{100} \equiv 0 \pmod{125}$。因此，$n^{100}$模$125$只能是$0$或$1$。答案是$\boxed{2}$。

Topics