Finding the last two digits of $5312^{442}$

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

Solutions Collecting From Web of "Finding the last two digits of $5312^{442}$"

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

[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).

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

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