Take the 2-minute tour ×
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.

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

share|improve this question
    
How do I make this community wiki? I couldn't find the option, so I flagged it for moderator attention... –  user7530 Nov 11 '11 at 22:07
    
fermat's little theorem –  geraldgreen Nov 11 '11 at 22:37
    
It may be laborious when $c$ is huge, but $b$ being huge should be no problem. –  Michael Hardy Nov 11 '11 at 22:45

4 Answers 4

up vote 9 down vote accepted

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 \equiv = 5 \times 25^2 \equiv 5 \times 1^2 = 5 \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 $.

share|improve this answer

Let's try $5^{844325} \mod 21$: $$ \begin{align} 5^0 & & & \equiv 1 \\ 5^1 & & &\equiv 5 \\ 5^2 & \equiv 25 & & \equiv 4 \\ 5^3 & \equiv 4\cdot 5 & & \equiv 20 \\ 5^4 & \equiv 20\cdot 5 & & \equiv 16 \\ 5^5 & \equiv 16\cdot 5 & & \equiv 17 \\ 5^6 & \equiv 17\cdot 5 & & \equiv 1 \end{align} $$ So multiplying by $5$ six times is the same as multiplying by $1$. We want to multiply by $5$ a large number of times: $844325$. How many times do we multiply by $5$ six times? The number of times $6$ goes into $844325$ is $140720$ with a remainder of $5$. That remainder is what matters. Multiply by $5^6$ exactly $140720$ times and that's the same as multiplying by $1$ that many times. Then multiply by $5$ just $5$ more times, and get $17$.

So $5^{844325} \equiv 17 \mod 21$.

share|improve this answer
    
You may want to check my arithmetic, but this method will do it when you get that right. –  Michael Hardy Nov 11 '11 at 23:05
    
This method won't be so nice when $(5,21)\neq 1$... –  ae0709 Nov 11 '11 at 23:53
3  
@aengle: it will be similar: for example for $6^{844325} \mod 21$ you would look at $6^0 \equiv 1$, $6^1 \equiv 6$, $6^2 \equiv 15$, $6^3 \equiv 6$, $6^4 \equiv 15$, so with a period of $2$. The number of times $2$ goes into $844325$ is $422162$ with a remainder of $1$. So $6^{844324} \equiv 15 \mod 21$ and thus $6^{844325} \equiv 6 \mod 21$. –  Henry Nov 12 '11 at 1:38

In general, squared exponentiation is used, this is $O(\log(b) \cdot \log(n))$ if multiplication $\bmod n$ is $O(\log (n))$.

powmod(a,b,n){
    res=1;
    fact=a;
    while(b>0){
        res=(res*(b%2)==1?fact:1)%n;
        fact=(fact*fact)%n;
        b=floor(b/2);
    }
}

when $b$ is huge (much larger than $n$) you can (attempt) to find the rank of the ring ($\varphi(n)$) and find the remainder of $b \pmod {\varphi(n)}$ because $a^b \bmod n= a^{b \mod \varphi(n)} \bmod n$ (for $21$, it is $(3-1) \cdot (7-1)=12$) this requires finding the prime factors of $n$.

In general the rank for $n = \prod{(p_i)^{k_i-1} \cdot (p_i-1)}$ with $p_i^{k_i}$ the prime factors of $n$.

share|improve this answer

For the first question: use $a^{\Phi(c)}=1 \mod c$, where $\Phi(c)$ is the number of coprimes to $c$ below $c$. For $c=21=7\cdot 3$ we have $\Phi(c)=(7-1)\cdot(3-1)=12$

second question: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and so on. Decompose the exponent into powers of 2 and combine them using $a^n\cdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}\cdot a^4\cdot a^1$

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.