Thursday, April 28, 2016

elementary number theory - How do I compute $a^b,bmod c$ by hand?



How do I efficiently compute $a^b\,\bmod c$:




  • When $b$ is huge, for instance $5^{844325}\,\bmod 21$?


  • When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, for instance $5^{69}\,\bmod 101$?

  • When $(a,c) \neq 1$, for instance $6^{103}\,\bmod 14$?



Are there any other tricks for evaluating exponents in modular arithmetic?






This is being asked in an effort to cut down on duplicates, see here: Coping with *abstract* duplicate questions.




and here: List of Generalizations of Common Questions


Answer



Wikipage on modular arithmetic is not bad.




  • When $b$ is huge, and $a$ and $c$ are coprime, Euler's theorem applies:
    $$
    a^b \equiv a^{b \, \bmod \, \phi(c)} \, \bmod c
    $$
    For the example at hand, $\phi(21) = \phi(3) \times \phi(7) = 2 \times 6 = 12$. $ 844325 \bmod 12 = 5$, so $5^5 = 5 \times 25^2 \equiv 5 \times 4^2 = 80 \equiv 17 \mod 21$.



  • When $a$ and $c$ are coprime, but $0$$
    \begin{eqnarray}
    5^4 \equiv 5 \times 5^3 \equiv 5 \times 24 \equiv 19 &\pmod{101}\\
    19^4 \equiv (19^2)^2 \equiv 58^2 \equiv (-43)^2 \equiv 1849 \equiv 31 &\pmod{101} \\
    31^4 \equiv (31^2)^2 \equiv (961)^2 \equiv 52^2 \equiv 2704 \equiv 78 &\pmod{101} \\
    5^{69} \equiv 5 \times 5^4 \times ((5^4)^4)^4 \equiv 5 \times 19 \times 78 \equiv 5 \times 19 \times (-23)\\
    \equiv 19 \times (-14) \equiv -266 \equiv 37 & \pmod{101}
    \end{eqnarray}
    $$



  • When $a$ and $c$ are not coprime, let $g = \gcd(a,c)$. Let $a = g \times d$ and $c = g \times f$, then, assuming $b > 1$:
    $$
    a^b \bmod c = g^b \times d^b \bmod (g \times f) = ( g \times (g^{b-1} d^b \bmod f) ) \bmod c
    $$
    In the example given, $\gcd(6,14) = 2$. So $2^{102} \times 3^{103} \mod 7$, using Euler'r theorem, with $\phi(7) = 6$, and $102 \equiv 0 \mod 6$, $2^{102} \times 3^{103} \equiv 3 \mod 7$, so $6^{103} \equiv (2 \times 3) \equiv 6 \mod 14 $.



No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...