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?

  • $\begingroup$ You may know the general theorem that if $m$ is a positive integer that has a primitive root, and $a$ and $m$ are relatively prime, then the congruence $x^k\equiv a \pmod{m}$ has a solution iff $a^{\varphi(m)/\gcd(\varphi(m),k)}\equiv 1\pmod{m}$, and that if there is a solution there are $\gcd(k,\varphi(m))$ solutions. This is the case $a=1$, $k=2$. $\endgroup$ – André Nicolas Aug 11 '13 at 5:41
  • $\begingroup$ Yes, you're absolutely right. Since we know $\pm1$ are solutions, they must also be all the solutions. $\endgroup$ – Alexander Chen Aug 11 '13 at 6:34

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.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.