# Does $a^{\phi(p^k)/2} \equiv -1 \pmod {p^k}$ imply $a$ is a primitive root modulo $p$, where $p$ is an odd prime and $k$ an integer $\ge 2$?

Suppose $a$ is a primitive root $\pmod p$.

Does $$a^{\phi(p^k)/2} \equiv -1 \pmod {p^k}$$ imply $a$ is a primitive root modulo $p^k$, where $p$ is an odd prime and $k$ an integer $\ge 2$ ?

I've been trying to look for a counter-example.

Let $p=7, k=2, a=31$. Then $a\equiv3\pmod7$, so $31$ is a primitive root modulo $7$. Here $\phi(p^k)=\phi(7^2)=42$, so $\phi(p^k)/2=21$.
But $31^{21}\equiv-1\pmod{49}$ and $31^6\equiv1\pmod{49}$, so your assumption is satisfied, but $31$ is not a primitive root modulo $49$.
If you want $0<a<p$, then Wieferich primes give you other examples. For example with $p=1093$ we know that $a=2$ is a primitive root. Also it can be checked that $$2^{p(p-1)/2}\equiv-1\pmod{p^2}.$$ This is because by Lagrnage's theorem $2^{p(p-1)}\equiv1\pmod{p^2}$, so $x=2^{p(p-1)/2}$ satisfies $x^2\equiv1\pmod{p^2}$. This congruence has only the two solutions $x\equiv\pm1\pmod{p^2}$. We can rule out $+1$ because $2$ is primitive, and $p(p-1)/2$ is not a multiple of $p-1$. But the Wieferich condition means exactly that $2$ is not primitive modulo $p^2$.
• Why not just take $a = -1$ with $p^k=9$? Commented Jun 8, 2014 at 11:37
• Wieferich is overkill here as we don't need to restric to the case $a=2$. Commented Jun 8, 2014 at 12:03