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

Revision as of 12:05, 14 November 2024

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$

Fast Solution

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

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

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 125: Clearly the only remainder provides 0

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

~mitsuihisashi14

Solution 3

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 if ${a}$ is an integer and $p$ is a positive integer relatively prime to $a$ , then ${a}^{\phi (p)}\equiv 1 \pmod {p}$ .

In this case, $p=125$ , which is convenient because $125$ only has one prime factor, $5$ , therefore $\phi(125)=100$ , so $a^{100}\equiv1\pmod{125}$ where $\gcd(a,125)=1$ . Every single number that isn't a multiple of $5$ is relatively prime to $125$ , therefore we have two cases:

1) $a\%5\neq0\implies a^{100}\equiv1\pmod{125}$ 2) $a\%5=0\implies a^{100}=5^3\cdot x\implies a^{100}\equiv0\pmod{125}$

The answer is $\boxed{\text{(B) }2}$ ~Tacos_are_yummy_1

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

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

~ Pi Academy

@@ Line 45: / Line 45: @@
 so <math>(5+n)^{100} \equiv n^{100}</math>. Substituting <math>-n</math> for <math>n</math>, we get <math>(5-n)^{100} \equiv n^{100}</math>. Therefore, the remainders when divided by <math>125</math> repeat every <math>5</math> integers, so we only need to check the <math>100</math>th powers of <math>0, 1, 2, 3, 4</math>. But we have that <math>(5-1)^{100} \equiv 1^{100}</math> and <math>(5-2)^{100} \equiv 2^{100}</math>, so we really only need to check <math>0, 1, 2</math>. We know that <math>0, 1</math> produce different remainders, so the answer to the problem is either <math>2</math> or <math>3</math>. But <math>3</math> is not an answer choice, so the answer is <math>\boxed{\textbf{(B) } 2}</math>.
+==Solution 4 (Totient)==
+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>.
+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
 ==Video Solution 1 by Pi Academy (Fast and Easy ⚡🚀)==

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