solution set for congruence $x^2 \equiv 1 \mod m$

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.

Solution 1:

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

Solution 2:

Hint $\ $ If $\rm\:g\:$ generates a cyclic group of order $\rm\:2n,\:$ and $\rm\:x = g^k,\:$ then

$$\rm 1 = x^2\! = g^{2k}\!\!\iff 2n\mid 2k\iff n\mid k\iff x\! = g^n\, \ or\, \ x = g^0\! = 1$$