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.

I have a confusion regarding power computation in modular arithmetic

Lets say I want to compute

$(7^5)^4 \pmod {17}$

there are many ways to compute this and I get different answers with each method and dont know which one is right

Method#1:

If I compute $5*4$ first that will be $20$ and take mod with $17$ it will be $3$ which means we have

$7^3 = 343$ ... which mod with $17$ results in $3$

Method#2:

If I compute $7^5$ first that will be $16807$ which is $11 \pmod {17}$, now we have

$11^4$ which is $14641 \pmod {17} =4$

Which one is correct and Why ?

share|improve this question
2  
The expression should be interpreted as $7^{(5^4)}$, not as $(7^5)^4$, so the first method is wrong. I don't understand the second method. By Fermat's little theorem, you need to compute $5^4 \bmod 16$. –  Qiaochu Yuan May 9 '12 at 17:20
    
Are you computing $(7^5)^4$ or $7^{(5^4)}$? –  Alex Becker May 9 '12 at 17:21
1  
I had errors in method 2 i have edited the post now.. can you look again ? –  Abid May 9 '12 at 17:22
    
@AlexBecker I want to compute the first 1 that is (7^5)^4 –  Abid May 9 '12 at 17:24
1  
You need to compute with exponents mod 16, not 17, since $\rm\:n\not\equiv 0\Rightarrow n^{16}\equiv 1\pmod{17}.\:$ Therefore $\rm\:n^{j+16\:k}\equiv n^j\:(n^{16})^k\equiv n^j 1^k \equiv n^j,\:$ i.e. $\rm\:n^{J}\equiv n^{J\ mod 16}.$ –  Bill Dubuque May 9 '12 at 17:26
show 3 more comments

2 Answers

up vote 1 down vote accepted

When we calculate something "modulo $m$", what we're really doing is arithmetic in the quotient ring $\mathbb Z / m \mathbb Z$, whose elements consist of the congruence classes $[a] := \{a + km \operatorname{|} k \in \mathbb Z\}$, with the arithmetic operations $+$ and $\cdot$ defined on those classes as $[a] + [b] := [a + b]$ and $[a] \cdot [b] := [a \cdot b]$. Given those definitions, we can easily check that they are consistent, in the sense that the values of $[a] + [b]$ and $[a] \cdot [b]$ do not depend on which elements $a$ and $b$ of those congruence classes we choose to represent them.

The catch is that exponentiation is not one of the ring operations defined on $\mathbb Z / m \mathbb Z$; as you've noticed, there's no way to define a binary operator $\land$ on $\mathbb Z / m \mathbb Z$ such that, given two congruence classes $[a]$ and $[b]$ in $\mathbb Z / m \mathbb Z$ and their respective representatives $a$ and $b$, $[a] \land [b] = [a ^ b]$ regardless of the choice of representatives.

Rather, we should view modular exponentiation as a (right) external binary operation on $\mathbb Z / m \mathbb Z$ over $\mathbb Z$, i.e. as a map $\land : (\mathbb Z / m \mathbb Z) \times \mathbb Z \to \mathbb Z / m \mathbb Z$ defined as $[a] \land b = [a]^b := [a^b]$, where $a \in [a] \in \mathbb Z / m \mathbb Z$ and $b \in \mathbb Z$. We can then check that this definition indeed satisfies all the laws we would expect it to, such as, in particular, that $([a]^b)^c = [a]^{b \cdot c}$.

What about Bill Dubuque's answer, then? Well, as he correctly notes, if $p$ is prime (as 17 indeed is), then Fermat's little theorem implies that $[a]^{p-1} = [a]^0 = [1]$ for all $[a] \in \mathbb Z / p \mathbb Z$. Thus, in this case, we may equally well view the exponentiation operator as being defined on $\mathbb Z / p \mathbb Z$ over $\mathbb Z / (p-1) \mathbb Z$. This can simplify calculations, as we may then reduce exponents modulo $p-1$ before applying them.

share|improve this answer
add comment

The mistake is using the wrong modulus when reducing exponents. By Fermat's little Theorem

$$\rm mod\ p\!:\ n\not\equiv 0\:\Rightarrow\: n^{p-1}\equiv 1\:\Rightarrow\:n^{j+k(p-1)}\equiv n^j (n^{p-1})^k \equiv n^j 1^k \equiv n^j$$

Therefore $\rm\quad\ \ mod\ p\!:\ n\not\equiv 0\:\Rightarrow\ n^J\equiv n^{(J\ mod\ p-1)},\ $ where $\rm\:p\:$ is any prime integer.

share|improve this answer
add comment

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.