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"

(→‎Sidenote: Proof of Euler's Theorem)
m (→‎Solution 2 (Euler Totient))
 
(4 intermediate revisions by one other user not shown)
Line 29: Line 29:
 
Clearly the only remainder provides <math>0</math>
 
Clearly the only remainder provides <math>0</math>
  
−
Therefore, the remainders can only be <math>1</math> and <math>0</math>, which gives the answer <math>\boxed{(B)2}</math>.
+
Therefore, the remainders can only be 0 and 1, which gives the answer <math>\boxed{(B)2}</math>.
  
 
~mitsuihisashi14
 
~mitsuihisashi14
 
~BS2012 (Minor corrections)
 
~BS2012 (Minor corrections)
−
~andliu766
+
~andliu796
 +
 
 +
==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)==
 
==Solution 3 (No Totient)==
Line 64: Line 72:
 
~Kathan
 
~Kathan
 
[[Image: 2024_AMC_12B_P18.jpeg|thumb|center|600px|]]
 
[[Image: 2024_AMC_12B_P18.jpeg|thumb|center|600px|]]
−
 
−
==Solution 6(Euler's theorem)==
 
−
We have that <math>125=5^3,</math> so the only prime factor of <math>125</math> is <math>5.</math> Let the integer be <math>x,</math> then we have two cases:
 
−
 
−
The first is if <math>x \equiv 5 \pmod{125},</math> then <math>x^{100}\equiv 5^{100} \equiv 0 \pmod{125}.</math>
 
−
 
−
~nevergonnagiveup
 
−
 
−
The second is if <math>x \not\equiv 5 \pmod{125},</math> in which we can conclude that <math>\gcd(x,125)=1.</math> Using Euler's theorem(proven below),
 
−
we have that <math>x^{\phi(125)}\equiv 1 \pmod{125}.</math> The clever part about this is that <math>\phi(125)=100,</math> since for every <math>5</math> positive integers starting from <math>1</math>, <math>4</math> are coprime with <math>125</math>(since it only has <math>5</math> as a prime factor). Then <math>\frac{4}{5}\cdot 125 =100,</math> so <math>x^{100}\equiv 1\pmod{125}</math> in this case. Therefore there are only <math>\boxed{2}</math> possible remainders.
 
−
 
−
==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)==
 
==Solution 7 (Guess)==

Latest revision as of 13:04, 23 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 0 and 1, which gives the answer $\boxed{(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 $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

2024 AMC 12B P18.jpeg

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

See also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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