Large Modular Arithematic Exponentiation

Question

How do I calculate

• $2^{65536} \pmod{2^{31} -1}$
• $3^{256} \pmod{2^8 +1}$

Please help?

Answer 1

$(1)$

As $65536=2114\cdot31+2\pmod{31}$

$2^{65536}=2^{31\cdot2114+2}=(1+2^{31}-1)^{2114}\cdot2^2$

Now $(1+2^{31}-1)^{2114}=1+\sum_{r=1}^{2114}\binom{2114}r(2^{31}-1)^r\equiv1\pmod{2^{31}-1}$

$(2)$

Fortunately $2^8+1=257$ is prime, so we can safely use Fermat's Little Theorem