Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Related: How do I compute $a^b\,\bmod c$ by hand? – barto Aug 20 '15 at 11:48
up vote 6 down vote accepted

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

share|cite|improve this answer
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 \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...

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.