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}$$
No comments:
Post a Comment