Modular arithmetic of really big numbers

Question

Does anybody know how can i compute mods of really big numbers? Is there a program that can make the task easier? I have to compute for example $101^{24}$$97^{25}$mod493 .

Answer 1

Chinese Remainder Thereom and possibly Eulers Theorem. Those numbers aren't actually that big if you have the right tools.

$493 =17*29$.

$101^{24}*97^{25}\pmod {17} \equiv $

$(-1)^{24}*12^{25}\pmod {17}\equiv $

$12^{16+9}\pmod {17}\equiv$

$12^9 \equiv 4^9 3^9\equiv 16*16*16*16*4*27^3\equiv (-1)^4*4*10^3\equiv$

$4000\equiv 5 \pmod {17}$.

And $101^{24}*97^{25}\pmod {29}\equiv$

$14^{24}*10^{25}\pmod {29}\equiv$

$14^{28-4}*10^{28-3}\equiv 14^{-4}*10^{-3}\pmod {29}$.

$2*14 = 28\equiv -1\pmod{29}$ so $-2*14\equiv 1\pmod {29}$. So $14^{-1}\equiv -2$

And $3*10\equiv 1 \pmod {29}$. So $10^{-1}\equiv 3$.

So $14^{-4}*10^{-3}\pmod {29}\equiv (-2)^4 *3^3\equiv 16*27\equiv 16*(-2)\equiv -32\equiv -3\equiv 26 \pmod {29}$.

So we need to solve $x\equiv 5\pmod {17}$ and $x \equiv -3 \pmod {29}$.

$5 + 17M = -3+29J$

$8 = 29J - 17M$

$29=17+12$

$12 = 29 - 17$

$17 = 12 +5 = (29-17)+5$

$5 = 2*17-29$

$12 = 2*5 + 2 = (4*17-2*29) + 2$.

$2 = (29-17) - (4*17-2*29) = 3*29 - 5*17$

$8 = 12*29 - 20*17$

And so $J=12$ and $M=20$ is a solutions and

$5+17*20 = -3 + 12*29 = 345$

And $101^{24}*97^{25}\equiv 345 \pmod {493}$