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.

Answers 2


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.

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