# Primitive Root Theorem

• Nov 28th 2008, 08:42 AM
mndi1105
Primitive Root Theorem
Let m be an integer with m >2. If a primitive root modulo m exists, prove that the only incongruent solutions of the congruence x^2=1 mod m are x=1 mod m and x= -1 mod m.
• Nov 28th 2008, 09:27 AM
ThePerfectHacker
Quote:

Originally Posted by mndi1105
Let m be an integer with m >2. If a primitive root modulo m exists, prove that the only incongruent solutions of the congruence x^2=1 mod m are x=1 mod m and x= -1 mod m.

If $x^2\equiv 1(\bmod m)$ then write $x\equiv r^y$ where $r$ is a primitive root.
Therefore, $r^{2y}\equiv r^0 (\bmod m)\implies 2y\equiv 0(\bmod \phi(m) )$.
Thus, what can you conclude?