Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 AMC 10B Problems/Problem 18"
Line 7: Line 7:
  
 
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>.
 
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
 
~lprado

Revision as of 00:53, 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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AMC_10B_Problems/Problem_18&oldid=233533"