AMC 10B/12B 2024 (Problem 18/14)How many different remainders can result when the 100100100th power of an integer is divided by 125125125?(A) 1\text{(A)}\;1(A)1(B) 2\text{(B)}\;2(B)2(C) 5\text{(C)}\;5(C)5(D) 25\text{(D)}\;25(D)25(E) 125\text{(E)}\;125(E)125Related TopicsToolkit 51 — Euler's Totient Function φ(n)Toolkit 52 — Euler's TheoremHints (6)Hint 1Calculate φ(125)\varphi(125)φ(125).Hint 2φ(125)=125(1−15)=125−25=100\varphi(125)=125\left(1-\frac{1}{5}\right)=125-25=100φ(125)=125(1−51)=125−25=100Hint 3If 5∣a⇒a100≡?(mod125)5\mid a\quad\Rightarrow\quad a^{100}\equiv ?\pmod{125}5∣a⇒a100≡?(mod125)Hint 4If 5∣a⇒a100≡0(mod125)5\mid a\quad\Rightarrow\quad a^{100}\equiv 0\pmod{125}5∣a⇒a100≡0(mod125)Hint 5If 5∤a⇒a100≡?(mod125)5\nmid a\quad\Rightarrow\quad a^{100}\equiv ?\pmod{125}5∤a⇒a100≡?(mod125)Hint 6By Euler's Theorem, if 5∤a⇒a100≡1(mod125)5\nmid a\quad\Rightarrow\quad a^{100}\equiv 1\pmod{125}5∤a⇒a100≡1(mod125)Final Answer(B) 2