2024 AMC 10B Problems/Problem 18: Difference between revisions

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

@@ 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

Page

Toolbox

Search

2024 AMC 10B Problems/Problem 18: Difference between revisions

Revision as of 00:51, 14 November 2024

Solution 1