# Solutions of $x^2 \equiv 1 \pmod N$

by Phi_24   Last Updated June 19, 2019 15:20 PM

I am stuck with this exercise:

Show that $$\forall s >0 \quad \exists N >0$$ such that $$x^2 \equiv 1\pmod N$$ has more than $$s$$ solutions.

I think I cannot use the theory if quadratic residues, because the modulus is not prime, so maybe I must prove it with square roots or roots of unity, but I don't know how to approach it at all.

Thanks for any help.

Tags :

Hint:

Consider a square-free integer: $$\;N=p_1p_2\dotsm p_r$$. By the Chinese Remainder theorem, solving the equation $$x2\equiv 1\pmod N$$ is equivalent to solving the set of congruences $$\begin{cases} x^2\equiv 1\pmod{p_1} \\ \quad\enspace\vdots\\x^2\equiv 1\pmod{p_r} \end{cases}\iff \begin{cases} x\equiv\pm 1\pmod{p_1} \\ \quad\enspace\vdots\\x \equiv \pm1\pmod{p_r} \end{cases}$$ so there are $$2^r$$ solutions.

Bernard
June 19, 2019 14:48 PM

HInt $$\$$ Use the multiplicativity of the number of roots of $$\,f(x) = x^2-1\,$$ as in the Remark below.

Remark $$\$$ If $$\,m,n\,$$ are coprime then, by CRT, solving a polynomial $$\,f(x)\equiv 0\pmod{\!mn}\,$$ is equivalent to solving $$\,f(x)\equiv 0\,$$ mod $$\,m\,$$ & mod $$\,n.\,$$ By CRT, each combination of a root $$\,r_i\,$$ mod $$\,m\,$$ and a root $$\,s_j\,$$ mod $$\,n\,$$ corresponds to a unique root $$\,t_{ij}\,$$ mod $$\,mn,\,$$ i.e.

$$\begin{eqnarray} f(x)\equiv 0\!\!\!\pmod{mn}&\overset{\rm CRT}\iff& \begin{array}{}f(x)\equiv 0\pmod{\! m}\\f(x)\equiv 0\pmod{\! n}\end{array} \\ &\iff& \begin{array}{}x\equiv r_1,\ldots,r_k\pmod{\! m}\phantom{I^{I^{I^I}}}\\x\equiv s_1,\ldots,s_\ell\pmod n\end{array}\\ &\iff& \left\{ \begin{array}{}x\equiv r_i\pmod{\! m}\\x\equiv s_j\pmod n\end{array} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}^{\phantom{I^{I^{I^I}}}}\\ &\overset{\rm CRT}\iff& \left\{ x\equiv t_{i j}\!\!\!\pmod{\!mn} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}\\ \end{eqnarray}\qquad\qquad$$

Bill Dubuque
June 19, 2019 15:08 PM

## Related Questions

Updated December 12, 2018 05:20 AM

Updated December 12, 2017 12:20 PM

Updated July 09, 2017 20:20 PM

Updated February 28, 2018 19:20 PM