# 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?

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