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?
 A: 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$$
A: Hint: use a binomial expansion of
$$
(10 - 1)^{56}
$$
A: 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$.
A: $\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.
A: 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)
