elementary number theory - 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?

Answer

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