Online Course Discussion Forum

2021 8 Week Prep Course for the AMC 10 Question 1

 
 
Picture of Daniel Zhu
2021 8 Week Prep Course for the AMC 10 Question 1
by Daniel Zhu - Wednesday, December 2, 2020, 5:24 PM
 
What's a quick way to solve this problem and other problems like this? 


How I solved it was I looked at each exponent of 23 and tried to find a pattern but I would assume that would be too time-consuming on the actual AMC.

 
Picture of David Reynoso
Re: 2021 8 Week Prep Course for the AMC 10 Question 1
by David Reynoso - Wednesday, December 2, 2020, 6:37 PM
 

Try using Euler's Theorem (the extension of Fermat's Little Theorem for when the mod is not prime) that says $$a^{\phi(n)} \equiv 1 \pmod{n},$$ where $\phi(n)$ is Euler's totient function (number of positive integers smaller than $n$ that are relatively prime with $n$) and $\gcd(a,n) = 1$.

Picture of Daniel Zhu
Re: 2021 8 Week Prep Course for the AMC 10 Question 1
by Daniel Zhu - Thursday, December 3, 2020, 9:54 PM
 
Got it, thank you!
Picture of Joy Xu
Re: 2021 8 Week Prep Course for the AMC 10 Question 1
by Joy Xu - Sunday, December 6, 2020, 11:35 AM
 

I'm also struggling with this problem. I can't seem to find a pattern by looking at the powers of 23 mod 100, or figure out how to use Euler's Theorem. I've tried putting in 100 and 10 for n and 23 for a but I can't figure out how to get the 2323 into the exponent. I'm not really familiar with this theorem and how to use it, so do you have any hints?

Picture of Joy Xu
Re: 2021 8 Week Prep Course for the AMC 10 Question 1
by Joy Xu - Sunday, December 6, 2020, 12:52 PM
 

Oh wait never mind I was able to find a pattern with the powers of 23, but I still don't know how to use Euler's Theorem for this problem.