# The residue of $9^{56}\pmod{100}$

How can I complete the following problem using modular arithmetic?

Find the last two digits of $9^{56}$.

I get to the point where I have $729^{18} \times 9^2 \pmod{100}$. What should I do from here?

• I wouldn't do it quite like that. There are various better methods. Try the first few powers of $9$ - do you see a pattern? – Mark Bennet May 2 '15 at 17:57
• @user31415 $729^{18} = (9^3)^{18} = 9^{54}$ – Joffan May 2 '15 at 18:17

Another way :

Let $[n]$ be the right-most two digits of $n$. Then, note that $$[9^2]=81,[9^3]=29,[9^4]=61,[9^5]=49,[9^6]=41,$$$$[9^7]=69,[9^8]=21,[9^9]=89,[9^{10}]=\color{red}{01}.$$

Hence, $[9^{56}]=[9^{6}]=41$.

Hint: use a binomial expansion of $$(10 - 1)^{56}$$

• Another hint: the last two terms. – mathreadler May 2 '15 at 18:48
• Can you expand your hint into a proper answer? – Joffan May 4 '15 at 5:10

If you don't insist on using a clever method, it actually isn't too hard to just do by hand. When you write out the first few powers of $9$ modulo $100$, you will find (just remember the last two digits in each step) that: $$9^6\equiv 41\mod 100$$

And:

$$9^{10}\equiv 1\mod 100$$

Now we see that:

$$9^{56}=(9^{10})^5\cdot 9^6\equiv 41\mod 100$$

$\bmod 4\!:\ 9^{56}\equiv 1^{56}\equiv 1\,\Rightarrow\, 9^{56}=4m+1$.

$$\bmod 25\!:\ 9^{56}\stackrel{(1)}\equiv 9^{56\pmod{\phi(25)}}\equiv 9^{56\pmod {20}}\equiv 9^{-4}\equiv \left(\frac{1}{81}\right)^2$$

$$\equiv \left(\frac{1+5\cdot 25}{6+3\cdot 25}\right)^2\equiv \left(\frac{126}{6}\right)^2\equiv 21^2\equiv (-4)^2\equiv 16\equiv 4m+1$$

$$\iff 4m\equiv 15\equiv 40\iff m\equiv 10\iff m=25l+10$$

$9^{56}=4(25l+10)+1=100l+41$. In $(1)$ I used Euler's theorem.

By Carmichael's function, the order of any residue of $100$ divides, and is a maximum of, $20$ (the same as for $25$). We see that $9$ is a square, so the maximum order of $9 \bmod 100$ is $10$ (or divides $10$ if it is less). This gives

$$9^{56}\equiv 9^6 \bmod 100$$

Then we can simply multiply a few small powers:

$$9^2 \equiv 81,\quad 9^4 \equiv 61, \quad 9^6 \equiv 41 \equiv 9^{56}$$

(This result also shows - since $9^6 \not\equiv 9$ - that the order of $9 \bmod 100$, not being $2$ or $5$, must be $10$, as others have shown by direct calculation)