# Finding the last two digits

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

-
– barto Aug 20 '15 at 11:48

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

-
Nicolas: Shouldn't that be $123^{40}\equiv 1 \pmod{100}.$ ? – Souvik Dey Jan 30 '13 at 8:05
@SouvikDey: Thank you for catching it. – André Nicolas Jan 30 '13 at 8:45
where is 40 came from? I don't understand it very well – user94634 Sep 13 '13 at 6:02
It is from the formula for $\varphi(n)$. Recall that $\varphi(ab)=\varphi(a)\varphi(b)$ if $a$ and $b$ are relatively prime, so $\varphi(100)=\varphi(4)\varphi(25)$. And for any prime power $p^k$, we have $\varphi(p^k)=(p-1)p^{k-1}$. – André Nicolas Sep 13 '13 at 12:42

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 $$23^{562} \pmod{100}.$$

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 $$a^{\varphi(n)} \equiv 1 \pmod{n}.$$

Over to you...

-

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.

-