1
$\begingroup$

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 ?

  • 0
    See Alex's link to the Wikipedia page on Fermat's Little Theorem. Perhaps you are confusing the form $\rm\:mod\ p\!:\ n^p\equiv n\:$ vs. $\rm\:n^{p-1}\equiv 1\ if\ n\not\equiv 0.\:$2012-05-09

2 Answers 2

1

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.

1

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.