I'm trying to follow an example. It states that if $p$ is an odd prime such that $p \equiv 1 \hspace{1mm} (\mathrm{mod} \hspace{1mm} 4)$, and $r$ is a primitive root modulo $p^k$, then $$r^{\frac{p-1}{2}p^{k-1}} \equiv -1 \hspace{1mm} (\mathrm{mod} \hspace{1mm} p^k). $$
I'm confused about this. First of all, if $p \equiv 1 \hspace{1mm} (\mathrm{mod} \hspace{1mm} 4)$, then $p-1 = 4t$ and $r^{(p-1)/2} = r^{2t}$ and then $r^{\frac{p-1}{2}p^{k-1}} = (r^{p^{k-1}})^{2t} $ and I don't see how that could be a negative number.
Meanwhile, $r$ is a primitive root modulo $p^k$, so $r^{\phi(p^k)} \equiv 1 \hspace{1mm} (\mathrm{mod} \hspace{1mm} p^k) $ and $\phi(p^k) = p^k – p^{k-1}$, so shouldn't we have $r^{\frac{p-1}{2}p^{k-1}} = r^{\frac{p^k – p^{k-1}}{2}} = r^{\phi(p^k)/2} \equiv (1)^{1/2} = 1 $?
(Note that $\phi(n)$ is Euler's phi-function.)
Best Answer
$r$ is a primitive root mod $p^k$. This means that $r^{\phi(p^k)}\equiv 1 \bmod p^k$, and this is the least exponent for which this equality holds (so notably $r^{\phi(p^k)/2}\not\equiv 1\bmod p^k$). One must therefore have that $r^{\phi(p^k)/2}\equiv -1\bmod p^k$, as desired.