Finding the last two digits $123^{562}$

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

Solution 1:

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

Solution 2:

Notice that the last two digits are the remainder of the division by $100$.

So you should be arguing in $\mathbf{Z}_{100}$, the ring of integers modulo $100$, and your problem becomes calculating \begin{equation} 23^{562} \pmod{100}. \end{equation}

Now the class of $23$ is invertible in $\mathbf{Z}_{100}$, as $23$ and $100$ are coprime.

And you know by Euler-Fermat that if $(a, n) = 1$, then \begin{equation} a^{\varphi(n)} \equiv 1 \pmod{n}. \end{equation}

Over to you...

Solution 3:

I think it will be 29 . You can do it in this way...... $123^{562}=23^{562}=(562*3^{561}*20+3^{562})=29$ mod 100 because $3^{560}=81^{140}=(140*80*1+1)$ mod 100 so $3^{561}=03$ and $3^ {562}=09$ mod 100 . In all the steps i have used binomial theorem.