Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

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.

share|improve this question
3  
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
2  
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
1  

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.