Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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$. –  André Nicolas Aug 11 '13 at 5:41
    
Yes, you're absolutely right. Since we know $\pm1$ are solutions, they must also be all the solutions. –  Alexander Chen Aug 11 '13 at 6:34
add comment

2 Answers

up vote 0 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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