Solutions of the congruence $x^2 \equiv 1 \pmod{m}$

For $m>2$, if a primitive root modulo $m$ exists, prove that the only solutions of the congruence $x^2 \equiv 1 \pmod m$ are $x \equiv 1 \pmod m$ and $x \equiv -1 \pmod m$.

Thanks.

Here is an indirect solution - a solution that doesn't use any specific primitive root. I think a better solution exists, but I would still like to post it because it gives a different perspective.

The solutions $1$ and $m-1$ are obviously always solutions. So the difficulty is proving there aren't any more.

By the primitive root theorem, the possibilities for $m$ are $m=2$, $m=4$, $m=p^k$, or $m=2p^k$ where $p$ is an odd prime and $k\ge 1$.

For $m=2$ we actually have $1=m-1$, and there is a unique square root of $1$.

For $m=4$ you may check directly that the claim holds, just by calculating.

For $m=p^k$, we prove by induction on $k$. For $k=1$ there are no zero divisors, so $(x-1)(x+1)=0$ implies $x-1=0$ or $x+1=0$. For $k>1$, assuming there are exactly two solutions modulo $p^{k-1}$, we use Hensel's lemma to claim that these lift to exactly two solutions modulo $p^k$.

For $m=2p^k$ we use the Chinese remainder theorem to combine the two solutions modulo $p^k$ with the unique solution modulo $2$ to get two solutions modulo $m$.

Here is a direct solution involving a primitive root (see also my other answer for an "indirect" solution):

Let $r$ be a primitive root modulo $m$ and let $\{r^0, r^1, \ldots, r^s\}$ be the multiplicative group mod $m$.

Let $x$ satisfy $x^2 = 1$. Then $x$ must be a member of the multiplicative group, since it's invertible mod $m$ (it is its own inverse). So we can write $x = r^k$ for some integer $k$, and we know that $r^{2k} \equiv r^0 \pmod m$. This gives us $2k \equiv 0 \pmod {\phi(m)}$ where $\phi$ is Euler's totient function. This congruence has at most two solutions (this I leave as exercise), giving at most two solutions for $x$.

$x^2$$\equiv1 mod m means that m|(x^2-1).....what can you infer from this? • If m is not prime, not much. Mar 29 '13 at 14:24 • Yes, but if m has a primitive root, it is 2, 4, p^k or 2 p^k for an odd prime p. This severely cuts down the options here. Mar 29 '13 at 15:43 Suppose \,w\, is a primitive root modulo \,m\, , and \,x=w^k\, , then$$x^2=1\pmod m\iff w^{2k}=1\pmod m\iff (w^k-1)(w^k+1)=0\pmod m\iff (x-1)(x+1)=0\pmod m\ldots$$The fact that any unit$\,x\,$modulo$\,m\,$is a power of$\,w\,$follows from the fact of the latter being a primitive root modulo$\,m\,$...If$\,m\,$has no primitive roots then the claim isn't true. Warning: In the last step you still have to give a very little explanation... • What is$p$here? Mar 29 '13 at 14:24 • Typo, @YoniRozenshein. Thanks Mar 29 '13 at 14:44 hint: an equation of degree 2, also in modular arithmetic, has at most two solutions if a primitive root modulo$m$exists • This is not true because there could be$0$divisors. For instance$x^2 = 1 \pmod {15}$has solutions:$x=1$,$x=14$,$x=4$,$x=11$. Mar 29 '13 at 13:57 • No...$x^2 \equiv 1 \pmod{15}$has solutions$x \equiv 1, 4, 11, 14 \pmod{15}$. You need to use the fact that there is a primitive root$\pmod{n}\$. Mar 29 '13 at 13:58
• After the edit, the answer became a question slightly harder than the original question Apr 8 '13 at 8:22