# how to use euler's theorem

If we have $a$ and $p$ where $p$ is prime, how do we use Euler's Theorem to calculate $a\pmod{p}$ when $a$ is a very large number? Any numerical example (for instance, $10^{300}\pmod{13}$) would help.

-
I think you mean how to use Euler's theorem to calculate $a^n \bmod p$. This has been asked (or at least answered) multiple times on this site before, but I can't find it now. Anyway, the short answer is that you reduce a mod p, and $n$ mod $p-1$ (or $\phi(p)$ in the case when $p$ is not prime). For instance, for $10^{305} \bmod {13}$, we calculate $305 \bmod {12}$ to get $305 \equiv 5 \pmod {12}$, i.e., $305 = 12k + 5$ for some $k$. So modulo $13$, we have $10^{305} = 10^{12k + 5} = (10^{12})^k \cdot 10^5 \equiv 1^k \cdot 10^5 \equiv 10^5 \pmod {13}$. And the last part you calculate directly. –  ShreevatsaR Nov 16 '11 at 3:48
Possible duplicates: math.stackexchange.com/questions/44533/… , math.stackexchange.com/questions/26722/calculating-ab-mod-c And these aren't even the ones I referred to as having seen earlier. –  ShreevatsaR Nov 16 '11 at 4:03
add comment