if $m$ is an integer greater than 2, and a primitive root modulo $m$ exists, prove that the only incongruent solutions of $x^2 \equiv 1 \mod m$ are $x \equiv \pm 1 \mod m$.
I know that if a primitive root mod $m$ exists, then $m = 1, 2, 4, p^m,$ or $2p^m$, where p is an odd prime and $m$ is a positive integer. Obviously I can check the cases where $m = 1, 2, 4$ by hand but I am having trouble proving the other two cases.
Best Answer
$1,2,4$ can be dealt easily.
For $p^m$ divides $(x^2-1)=(x-1)(x+1)$
Now, $x+1-(x-1)=2\implies (x-1,x+1)$ divides $2$
So, either $p^m$ divides $(x-1)$ or $(x+1)$ resulting in exactly $2$ in-congruent solutions
If $2\cdot p^m$ divides $(x^2-1)=(x-1)(x+1)$
Clearly, $x$ is odd
So, $p^m$ divides $\frac{x-1}2\cdot\frac{x+1}2$
Now, $-\frac{x-1}2+\frac{x+1}2=1\implies (\frac{x+1}2,\frac{x-1}2)=1$
So, either $p^m$ divides $\frac{x-1}2$ or $\frac{x+1}2$ resulting in exactly $2$ in-congruent solutions
Alternatively, f $x^d\equiv1\pmod m$ and $m$ has a primitive root $a$
Taking Discrete logarithm, $d\cdot ind_ax\equiv ind_a1\pmod {\phi(m)}\equiv0$
Using Linear congruence theorem, it has exactly $(d,\phi(m))$ solutions as $(d,\phi(m))$ divides $0$