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)$
'math > number theory' 카테고리의 다른 글
| The product of all primitive roots modulo m is either 1 or -1. (0) | 2025.11.22 |
|---|---|
| If m>2, ϕ(m) is even. (0) | 2025.11.22 |
| Let m > 2 be an integer with a primitive root r. Then, r^(ϕ(m)/2) ≡ −1 (mod m) (0) | 2025.11.22 |
| 디오판토스 방정식의 해 구하기 (1) | 2025.09.24 |
| 상수항을 통해 n차방정식의 정수근 찾기 (0) | 2025.09.24 |