Modular exponentiation by hand (abmodca^b\bmod c)

How do I efficiently compute abmodc:

  • When b is huge, for instance 5844325mod21?
  • When b is less than c but it would still be a lot of work to multiply a by itself b times, for instance 569mod101?
  • When (a,c)1, for instance 6103mod14?

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 and here.

Answer

Wikipage on modular arithmetic is not bad.

  • When b is huge, and a and c are coprime, Euler’s theorem applies:
    ababmodϕ(c)modc
    For the example at hand, ϕ(21)=ϕ(3)×ϕ(7)=2×6=12.

    \Rightarrow 844325 \bmod 12 = 5,\ \text{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<b<\phi(c), repeated squaring (or using other compositions of powers) is the fastest way to go (manually):

    \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 .

Attribution
Source : Link , Question Author : user7530 , Answer Author : upe

Leave a Comment