Finding the last two digits of $5312^{442}$ Suppose that you are asked to find the last $2$ digits of $5312^{442}$.


*

*We need to find what number between $0$ and $99$ that is congruent to our number modulo $100$.

*My first guess would be to check to see if I can use Euler's Theorem, but since $5312$ and $100$ are not coprime it would not be useful. 

*Would it be possible to convert the exponent to binary and use the successive squaring algorithm to solve: $5312^{442} \mod 100$? Are there any other (better) ways to go about this?
 A: As $5312\equiv12\pmod{100},5312^{442}\equiv12^{442}\pmod{100}$
Now as $(12,100)=4$  let us find $12^{442-1}\pmod{100/4}$
As $(12,25)=1,$ by Euler Theorem, $$12^{20}\equiv1\pmod{25}$$
As $441\equiv1\pmod{20},12^{441}\equiv12^1\pmod{25}$
$$\implies12\cdot12^{441}\equiv12\cdot12^1\pmod{12\cdot25}$$
$$\equiv144\pmod{300}\equiv144\pmod{100}\equiv44\pmod{100}$$
A: [quote] To start, you can immediately reduce 5312 modulo 100 so that you're solving $12^{442}$ instead.
Then, you solve this (mod 4) and (mod 25)


*

*(mod 4), it is pretty clear what the result would be

*(mod 25), you can use Euler's Theorem.
Then, combine the results back to (mod 100).
A: Well, you actually can use Euler's Theorem.  $\phi(100) = 40$ and so $12^{41} \equiv 12 \pmod{100}$:
$$5312^{442} \equiv (12^{41})^{10}12^{32} \equiv 12^{10}12^{32} \equiv 12^{42}\equiv 12^{41}12 \equiv 12^2 \equiv 44 \pmod{100}.$$
A: Note $\ \  ca\bmod cn\,=\, c\,(a\bmod n)\ $ as explained here, $ $ so
$\! \begin{align} 5312^{\large 442}\!\bmod 100\, 
&=\, 4\,(\color{}{12}^{\large 442}/4\bmod 25)\\  
&=\,4\,(\color{}{12}^{\large 2}/\,2^{\large 2}\, \bmod 25)\ \ {\rm by}\,\ 12^{\large 440}\!\equiv (12^{\large\color{#c00}{20}})^{\large 22}\!\equiv 1^{\large 22}\rm \ by\ Euler\ \phi(25)\!=\!\color{#c00}{20}\\
&=\,4\,(6^{\large 2} \bmod 25)\\
&=\, 4\,(11)
\end{align}$
