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 ?
 A: 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.
A: 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.
