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

Revision as of 01:10, 3 November 2025

The following problem is from both the 2024 AMC 10B #18 and 2024 AMC 12B #14, so both problems redirect to this page.

Problem

How many different remainders can result when the $100$ th power of an integer is divided by $125$ ?

$\textbf{(A) } 1 \qquad\textbf{(B) } 2 \qquad\textbf{(C) } 5 \qquad\textbf{(D) } 25 \qquad\textbf{(E) } 125$

Solution 1

First note that the Euler's 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 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

~edit by Elephant200

Solution 2 (Euler Totient)

We split the cases into:

1. If $x$ is not a multiple of $5$ : we get $x^{100} \equiv 1 \pmod{125}$

2. If $x$ is a multiple of $5$ : Clearly the only remainder provides $0$

Therefore, the remainders can only be $0$ or $1$ , which gives the answer $\boxed{\textbf{(B) } 2}$ .

~mitsuihisashi14 ~BS2012 (Minor corrections) ~andliu796

Sidenote: Proof of Euler's Theorem

Euler's Theorem states that $a^{\phi(n)}\equiv 1\pmod{n}$ , where $\phi(n)$ is Euler's totient function, which counts the number of positive integers $x$ such that $1\le x \le n$ and $\gcd(x,n)=1$ . Note that this only works for positive integer $a$ such that $\gcd(a,n)=1.$

Consider the set of distinct positive integers $S=\{x_1,x_2,\ldots x_{\phi(n)}\}$ such that $1\le x_i\le n$ and $\gcd(x_i,n)=1.$ Multiply all terms by $a$ to create $aS=\{ax_1,ax_2,\ldots ax_{\phi(n)}\}.$ First, we prove that $\gcd(ax_i,n)=1$ for any $x_i$ using contradiction. Let $p$ be a prime such that $p \mid ax_i$ and $p \mid n.$ This means that either $p \mid a$ or $p \mid x_i,$ which is not possible since both $\gcd(a,n)$ and $\gcd(x_i,n)=1.$ Next we show that no two elements in set $aS$ are congruent modulo $n.$ Let $x_i$ and $x_j$ exist such that $ax_i\equiv ax_j \pmod{n}.$ Multiplying both sides by $a^{-1}$ (which exists) gives $x_i\equiv x_j\pmod{n}.$ This means that if $x_i \not\equiv x_j \pmod{n},$ then $ax_i \not\equiv ax_j \pmod{n}.$ Now we multiply all terms in each set, and note that each residue appears exactly once in both sets, so we have: $a^{\phi(n)}\cdot \prod_{i=1}^{\phi(n)} x_i \equiv \prod_{i=1}^{\phi(n)} x_i \pmod{n}.$ Because each $x_i$ has the property that $\gcd(x_i,n)=1,$ we must have that $\gcd(\prod_{i=1}^{\phi(n)} x_i,n)=1.$ Then multiplying both sides by the inverse of product thereof gives $a^{\phi(n)}\equiv 1\pmod{n}.$ $\blacksquare$

~nevergonnagiveup

Solution 3 (No Totient)

Note that

$(5+n)^{100} = {100 \choose 0} 5^{100} + {100 \choose 1} 5^{99} n + {100 \choose 2} 5^{98} n^2 + \cdots + {100 \choose 97} 5^3 n^{97} + {100 \choose 98} 5^2 n^{98} + {100 \choose 99} 5 n^{99} + {100 \choose 100} n^{100}.$

Taking this mod $125$ , we can ignore most of the terms except the for the last $3$ :

${100 \choose 98} 5^2 n^{98} + {100 \choose 99} 5 n^{99} + {100 \choose 100} n^{100} \equiv 4950 \cdot 5^2 n^{98} + 100 \cdot 5 n^{99} + n^{100} \equiv n^{100} \pmod {125},$

so $(5+n)^{100} \equiv n^{100}$ . Substituting $-n$ for $n$ , we get $(5-n)^{100} \equiv n^{100}$ . Therefore, the remainders when divided by $125$ repeat every $5$ integers, so we only need to check the $100$ th powers of $0, 1, 2, 3, 4$ . But we have that $(5-1)^{100} \equiv 1^{100}$ and $(5-2)^{100} \equiv 2^{100}$ , so we really only need to check $0, 1, 2$ . We know that $0, 1$ produce different remainders, so the answer to the problem is either $2$ or $3$ . But $3$ is not an answer choice, so the answer is $\boxed{\textbf{(B) } 2}$ .

Solution 4 (Totient)

Euler's Totient Function, $\phi(n)$ returns $n\cdot\left(1-\dfrac{1}{x}\right)$ as a product of each prime divisor of $n$ .

Euler's Totient Theorem states that the answer is 2. Therefore the answer is 2.

Solution 5 (Binomial Theorem)

~Kathan

Error creating thumbnail: Unable to save thumbnail to destination

Solution 8

Firstly, I interpreted the problem algebraically. In other words, let ${x}$ be an integer. Since we're raising it to the ${100}$ th power and ${100}$ is even, we don't have to worry about negative values of ${x}$ . Now, we break ${125}$ into three factors of ${5}$ . I first considered this when we're dividing by ${5}$ . Okay so we can write the problem as below:

$x^{100}\equiv r \bmod{5}$ . Now, in the world of mod(5), everything is much easier to figure out. Take $x\equiv 0 \bmod{5}$ . Now, obviously $x^{100}$ will bring up a remainder of ${0}$ if ${x}$ itself is a multiple of 5. Now, $x\equiv 1 \bmod{5}$ . In this case, notice how $1^{100}$ is congruent to 1 in the mod(5) world. So in this case, we would have a remainder of 1. Considering $x\equiv 2 \bmod{5}$ , it's a little more tricky. Notice $2^{100}$ is equal to $1024^{10}$ and ${1024}$ is 1 less than a multiple of 5. So ${1024}$ will be congruent to $-1 \bmod{5}$ and raising it to the power of 10 will bring up a remainder of 1 yet again. Similarly, is $x\equiv 3 \bmod{5}$ or $x\equiv 4 \bmod{5}$ , you would notice both these cases will bring up a remainder of 1 again. So in the mod(5) world, we seem to only have remainders of ${0}$ and ${1}$ . Interesting! Therefore, since ${125}$ is just ${3}$ factors of ${5}$ , we may say that in mod(125), we would have the same exact remainders namely ${0}$ and ${1}$ . Therefore, we would only have ${2}$ possible remainders. This brings an answer of $\boxed{\textbf{(B)} \; 2}$ .

~ilikemath247365

Video Solution 1 by Pi Academy (Fast and Easy ⚡🚀)

https://youtu.be/c6nhclB5V1w?feature=shared

~ Pi Academy

Video Solution 2 (Fast!)

https://www.youtube.com/watch?v=S7l_Yv2Sd7E

Video Solution 3 by TheBeautyofMath(no totient)

https://youtu.be/KhD5-zDNoKM

~IceMatrix

@@ Line 58: / Line 58: @@
 Euler's Totient Function, <math>\phi(n)</math> returns <math>n\cdot\left(1-\dfrac{1}{x}\right)</math> as a product of each prime divisor of <math>n</math>.
-Euler's Totient Theorem states that if <math>{a}</math> is an integer and <math>p</math> is a positive integer relatively prime to <math>a</math>, then <math>{a}^{\phi (p)}\equiv 1 \pmod {p}</math>.
+Euler's Totient Theorem states that the answer is 2. Therefore the answer is 2.
-In this case, <math>p=125</math>, which is convenient because <math>125</math> only has one prime factor, <math>5</math>, therefore <math>\phi(125)=100</math>, so <cmath>a^{100}\equiv1\pmod{125}</cmath>where <math>\gcd(a,125)=1</math>. Every single number that isn't a multiple of <math>5</math> is relatively prime to <math>125</math>, therefore we have two cases:
-) <math>a\%5\neq0\implies a^{100}\equiv1\pmod{125}</math>
-) <math>a\%5=0\implies a^{100}=5^3\cdot x\implies a^{100}\equiv0\pmod{125}</math>
-The answer is <math>\boxed{\text{(B) }2}</math> ~Tacos_are_yummy_1
 ==Solution 5 (Binomial Theorem)==

2024 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 17	Followed by Problem 19
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

2024 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 13	Followed by Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

Page

Toolbox

Search