4

Can anyone tell me how to find the remainder of $\frac{4^{101}}{101}$ without using Fermat's little theorem ?

I tried doing $$4^{101} \equiv 2^{202} \equiv (5\cdot 101 + 7)^{22} \cdot 2^{4} \equiv 7^{22} \cdot 2^4 \mod 101$$ but after this I can't really get much further.

Tacet
  • 1,879
questioner
  • 392
  • 4
    Use the binary method for exponentiation (Wikipedia). – André Nicolas Dec 06 '14 at 20:26
  • 1
    Maybe start with $4^5=2^{10}$ modulo $101$, then square it and take the modulus, and repeat the square and take the modulus process, save the result at $4^{20}$, multiply that by the result at $4^{80}$, multiply by one more $4$ and take the modulus... This is called modular exponentiation. – abiessu Dec 06 '14 at 20:28

1 Answers1

5

This is how I would simplify it $$4^{101}=2^{202}\\2^{10}=1024\equiv 14\pmod{101}\\(2^{10})^2\equiv14^{2}\equiv-6\pmod{101}\\(2^{20})^5\equiv-6^5\equiv-216\cdot36\equiv-14\cdot36\equiv-504\equiv-1\pmod{101}\\(2^{100})^2\equiv 1\pmod{101}$$

kingW3
  • 13,496