math/number theory

If x^2 ≡ 1 (mod m), then either x ≡ 1 (mod m) or x ≡ −1 (mod m).

finding wangdo 2025. 11. 22. 19:32

If integer $m>2$ has a primitive root and $x^2\equiv1\ (\text{mod} \ m)$, then either $x\equiv1\ (\text{mod} \ m)$ or $x\equiv-1\ (\text{mod} \ m)$.

Proof.

Solve the congruence $x^2\equiv1\ (\text{mod} \ m)$. 
It is equivalent to solving the congruence $2y\equiv\text{ind}_r(1)\equiv0\ (\text{mod} \ \phi(m))$
Since $\text{gcd}(2,\phi(m))=2$ (because $\phi(m)$ is even), this congruence has 2 solutions (that are not congruent with each other).

Therefore, the original congruence also has two solutions (that are not congruent with each other).
We can easily find that $1, -1$ are the two solutions not congruent with each other.
We can conclude either $x\equiv1\ (\text{mod} \ m)$ or $x\equiv-1\ (\text{mod} \ m)$.
End of proof.

 

Note: this is not necessarily true for $m$ with no primitive roots. 8 doesn't have a primitive root. See that $3^2\equiv1\ (\text{mod} \ 8)$ but $3\not\equiv1\ (\text{mod} \ 8)$ and $3\not\equiv-1\ (\text{mod} \ 8)$