Show $r^{\frac{\phi(n)}{2}} \equiv -1$ mod $n$ for a primitive root $r$.

Question

I know that if n has a primitive root, then $x^2 \equiv 1$ has $x \equiv \pm1$ as solutions. This can then be used to show that $r^{\frac{\phi(n)}{2}} \equiv -1$ because $r$ has order $\phi(n)$, and out of the two choices it cannot be 1.

But I later found out that the proof I had about $x^2 \equiv 1 \implies$ $x \equiv 1$ or $-1$ assumed exactly the fact that r raised to the half of its order is -1.

The result $r^{\frac{\phi(n)}{2}} \equiv -1$ seems extremely obvious, but I don't know where to start and I see it being assumed everywhere.

One idea I have is to use Euler's theorem to show that $x \equiv \pm1$ for mod $p^t$ and mod $2, 4$. Then, use the Chinese remainder theorem to somehow reconstruct the solution to modulo $n$. This basically exhausts all the cases in which n has a primitive root.

Is this the correct direction at solving it?

Answer 1

We want to prove that if $n\gt 2$ has a primitive root, then the only solutions of $x^2\equiv 1\pmod{n}$ are $x\equiv \pm 1\pmod{n}$. Certainly $x\equiv \pm 1\pmod{n}$ are solutions, and since $n\gt 2$ they are distinct.

Let $g$ be a primitive root of $n$, and let $x=g^k$ be a solution of our congruence, where $k$ is one of $0$ to $\varphi(n)-1$. Then $g^{2k}\equiv 1 \pmod{n}$. It follows that $\varphi(n)$ divides $2k$. But $2k\lt 2\varphi(n)$. The only possibilities are $k=0$ and $2k=\varphi(n)$. The second possibility says that $k=\varphi(n)/2$.

Answer 2

I found a more intuitive way of looking at the problem.

Given r is a primitive root mod $n$, we know $[r, r^2, r^3, \ldots, r^{\frac{\phi(n)}{2}}, \ldots, r^{\phi(n)}]$ is the reduced residue system.

If $-1$ do not appear exactly at the center (which is $\frac{\phi(n)}{2}$), we get a contradiction where the cyclic group generated by $r$ must terminate at some point earlier than the $\phi(n)$th term, thus $r$ cannot be a primitive root.