# Power computation in modulo

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 ?

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

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.

-

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.

-