Difference between revisions of "2024 AMC 10B Problems/Problem 18"

m (Protected "2024 AMC 10B Problems/Problem 18" ([Edit=Allow only administrators] (expires 04:59, 14 November 2024 (UTC)) [Move=Allow only administrators] (expires 04:59, 14 November 2024 (UTC))))
Line 1: Line 1:
 +
==Solution 1==
 +
First note that the totient function of <math>125</math> is <math>100</math>. We can set up two cases, which depend on whether a number is relatively prime to <math>125</math>.
  
 +
If <math>n</math> is relatively prime to <math>125</math>, then <math>n^{100} \equiv 1 \pmod{125}</math> because of Euler's Totient Theorem.
 +
 +
If <math>n</math> is not relatively prime to <math>125</math>, it must be have a factor of <math>5</math>. Express <math>n</math> as <math>5m</math>, where <math>m</math> is some integer. Then <math>n^{100} \equiv (5m)^{100} \equiv 5^{100}\cdot m^{100} \equiv 125 \cdot 5^{97} \cdot m^{100} \equiv 0 \pmod{125}</math>.
 +
 +
Therefore, <math>n^{100}</math> can only be congruent to <math>0</math> or <math>1 \pmod{125}</math>. Our answer is <math>\boxed{2}</math>.
 +
~lprado

Revision as of 00:51, 14 November 2024

Solution 1

First note that the 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 be 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}$. ~lprado