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

Latest revision as of 01:37, 17 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$

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 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 ~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 $1$ and $0$ , which gives the answer $\boxed{(B)2}$ .

~mitsuihisashi14 ~BS2012 (Minor corrections) ~andliu766

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

Solution 5 (Binomial Theorem)

~Kathan

Solution 7 (Guess)

(Do not use this solution unless you are low on time or do not know how to solve this problem.) Notice that all the answer choices are odd and have some relationship to the number $5$ except for $2$ . $2$ doesn't seem to fit in with the other answer choices, so the test writers likely put it there because they had to. You can assume that it is the answer: $\boxed{\textbf{(B)} 2}$ .

Written by ChristianZhang

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

@@ Line 34: / Line 34: @@
 ~BS2012 (Minor corrections)
 ~andliu766
+==Sidenote: Proof of Euler's Theorem==
+Euler's Theorem states that <math>a^{\phi(n)}\equiv 1\pmod{n}</math>, where <math>\phi(n)</math> is Euler's totient function, which counts the number of positive integers <math>x</math> such that <math>1\le x \le n</math> and <math>\gcd(x,n)=1</math>. Note that this only works for positive integer <math>a</math> such that <math>\gcd(a,n)=1.</math>
+Consider the set <math>S=\{x_1,x_2,\ldots x_{\phi(n)}\}</math> such that <math>1\le x_i\le n</math> and <math>\gcd(x_i,n)=1.</math> Multiply all terms by <math>a</math> to create <math>aS=\{ax_1,ax_2,\ldots ax_{\phi(n)}\}.</math> First, we prove that <math>\gcd(ax_i,n)=1</math> for any <math>x_i</math> using contradiction. Let <math>p</math> be a prime such that <math>p \mid ax_i</math> and <math>p \mid n.</math> This means that either <math>p \mid a</math> or <math>p \mid x_i,</math> which is not possible since both <math>gcd(a,n)</math> and <math>gcd(x_i,n)=1.</math>  Next we show that no two elements in set <math>aS</math> are congruent modulo <math>n.</math> Let <math>x_i</math> and <math>x_j</math> exist such that <math>ax_i\equiv ax_j \pmod{n}.</math> Multiplying both sides by <math>a^{-1}</math>(which exists) gives <math>x_i\equiv x_j\pmod{n}.</math> This means that if <math>x_i \not\equiv x_j \pmod{n},</math> then <math>ax_i \not\equiv ax_j \pmod{n}.</math> Now we multiply all terms in each set, and note that each residue appears exactly once in both sets, so we have: <cmath>a^{\phi(n)}\cdot \prod_{i=1}^{\phi(n)} x_i \equiv \prod_{i=1}^{\phi(n)} x_i \pmod{n}.</cmath> Because each <math>x_i</math> has the property that <math>\gcd(x_i,n)=1,</math> we must have that <math>\gcd(\prod_{i=1}^{\phi(n)} x_i,n)=1.</math> Then multiplying both sides by the inverse of product thereof gives <math>a^{\phi(n)}\equiv 1\pmod{n}.</math> <math>\blacksquare</math>
+~nevergonnagiveup
 ==Solution 3 (No Totient)==
@@ Line 64: / Line 72: @@
 ~Kathan
 [[Image: 2024_AMC_12B_P18.jpeg|thumb|center|600px|]]
-==Sidenote: Proof of Euler's Theorem==
-Euler's Theorem states that <math>a^{\phi(n)}\equiv 1\pmod{n}</math>, where <math>\phi(n)</math> is Euler's totient function, which counts the number of positive integers <math>x</math> such that <math>1\le x \le n</math> and <math>\gcd(x,n)=1</math>. Note that this only works for positive integer <math>a</math> such that <math>\gcd(a,n)=1.</math>
-Consider the set <math>S=\{x_1,x_2,\ldots x_{\phi(n)}\}</math> such that <math>1\le x_i\le n</math> and <math>\gcd(x_i,n)=1.</math> Multiply all terms by <math>a</math> to create <math>aS=\{ax_1,ax_2,\ldots ax_{\phi(n)}\}.</math> First, we prove that <math>\gcd(ax_i,n)=1</math> for any <math>x_i</math> using contradiction. Let <math>p</math> be a prime such that <math>p \mid ax_i</math> and <math>p \mid n.</math> This means that either <math>p \mid a</math> or <math>p \mid x_i,</math> which is not possible since both <math>gcd(a,n)</math> and <math>gcd(x_i,n)=1.</math>  Next we show that no two elements in set <math>aS</math> are congruent modulo <math>n.</math> Let <math>x_i</math> and <math>x_j</math> exist such that <math>ax_i\equiv ax_j \pmod{n}.</math> Multiplying both sides by <math>a^{-1}</math>(which exists) gives <math>x_i\equiv x_j\pmod{n}.</math> This means that if <math>x_i \not\equiv x_j \pmod{n},</math> then <math>ax_i \not\equiv ax_j \pmod{n}.</math> Now we multiply all terms in each set, and note that each residue appears exactly once in both sets, so we have: <cmath>a^{\phi(n)}\cdot \prod_{i=1}^{\phi(n)} x_i \equiv \prod_{i=1}^{\phi(n)} x_i \pmod{n}.</cmath> Because each <math>x_i</math> has the property that <math>\gcd(x_i,n)=1,</math> we must have that <math>\gcd(\prod_{i=1}^{\phi(n)} x_i,n)=1.</math> Then multiplying both sides by the inverse of product thereof gives <math>a^{\phi(n)}\equiv 1\pmod{n}.</math> <math>\blacksquare</math>
-~nevergonnagiveup
 ==Solution 7 (Guess)==

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