This is my question:
Find the last 2 digits of $123^{562}$
I don't even understand where to begin on this problem. I know I'm supposed to use Euler's theorem but I have no idea how or why. Any help? Thanks
decimal-expansionelementary-number-theoryexponentiationmodular arithmetic
This is my question:
Find the last 2 digits of $123^{562}$
I don't even understand where to begin on this problem. I know I'm supposed to use Euler's theorem but I have no idea how or why. Any help? Thanks
Best Answer
To find the last two digits of our huge number, we need to find what number between $0$ and $99$ our number is congruent to modulo $100$.
We have $\varphi(100)=40$, Since $123$ is relatively prime to $100$, we have, by Euler's Theorem, that
$$123^{40}\equiv 1 \pmod{100}.$$
It follows that $123^{560}=(123^{40})^{14}\equiv 1\pmod{100}$.
Now $123^{562}=123^{560}123^2$. And mpodulo $100$ we can replace $123$ by $23$. So the problem comes down to evaluating $23^2$ modulo $100$, that is, finding the last two digits of $23^2$.