# 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

1. 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$.

2. You can always prevent the numbers from getting too big by reducing, using the modulus, whenever the numbers exceed the modulus.

• I'd just like to point out that repeated squaring is not necessarily the fastest way to do this. The more general "addition-chain exponentiation" (en.wikipedia.org/wiki/Addition-chain_exponentiation) can sometimes require less multiplications. However, it's a lot harder to figure out which multiplications to do. May 2, 2011 at 0:14

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.

• And what would you do if you couldn't factor the exponent? May 2, 2011 at 0:11
• Precisely what I did with the exponent 7?
– dstt
May 2, 2011 at 0:16
• OK. Then why bother factoring? Does it actually make anything better? May 2, 2011 at 0:24
• If you have a small factor and your calculator can handle it, then it usually makes things faster. It might also happen, that $3781^7$ is small mod 31847, so that your calculator can still handle that to the power 11... I usually start by factoring for these reasons.
– dstt
May 2, 2011 at 0:33

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.

• I think the answer will be 7458 based on this method. May 3, 2011 at 1:21

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. :)