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 is . We can set up two cases, which depend on whether a number is relatively prime to .
If is relatively prime to , then because of Euler's Totient Theorem.
If is not relatively prime to , it must be have a factor of . Express as , where is some integer. Then .
Therefore, can only be congruent to or . Our answer is . ~lprado