Modulo arithmetic with big numbers? I need to calculate $3781^{23947} \pmod{31847}$. Does anyone know how to do it? I can't do it with regular calculators since the numbers are too big. Is there any other easy solutions?
Thanks
 A: *

*You can always compute $a^n$ by repeated squaring and multiplication, e.g., to get $a^{13}$, you square $a$, multiply the result by $a$, square twice, and multiply again by $a$. The exact sequence of operations is visible in the binary expansion of $n$. 

*You can always prevent the numbers from getting too big by reducing, using the modulus, whenever the numbers exceed the modulus. 
A: 23947=7*11*311. Then $$3781^{23947} = (3781^7)^{11\times 311}$$ Then reduce $3781^7$ modulo 31847 and keep going. Since $3781^7$ is probably too big, you might have to compute it as $$3781\times 3781^6=3781\times (3781^2)^3$$ where again you reduce mod 31847 wherever possible.
A: I'm not sure if there is a good trick to use. I think the best way to go about it would be to compute it is to write $23947 = 2^{14} + 2^{12} + 2^{11} + 2^{10} + 2^8 + 2^7 + 2^3 + 2 + 1$ and compute $3781^{2^n} \mod 31847$ by repeatedly squaring and taking the modulus. We can then multiply these values $\mod 31847$ to compute the desired value. WolframAlpha says the answer is 6479.
A: Check out Chapter 1 of Dasgupta, Papadimitriou, Vazarani which describes this and other basic arithmetic on large integers.  The version linked above is a preprint of the current edition, but it's free. :)
