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

Question

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.

Answer 1

Hint:

Consider a square-free integer: $\;N=p_1p_2\dotsm p_r$. By the Chinese Remainder theorem, solving the equation $x^2\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\,\vdots\\x \equiv \pm1\pmod{p_r} \end{cases}$$ so there are $2^r$ solutions.

Answer 2

Hint $ $ Let $\,f(x) = x^2-1\,$ below and exploit the highlighted $\rm\color{#c00}{multiplicativity}$ of number of roots.

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 \large 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_{\color{}{\large k}}\pmod{\! m},\phantom{I^{I^{I^I}}}\ \ \color{#c00}k\ \ \rm roots\\x\equiv s_1,\ldots,s_{\large\color{}{\ell}}\pmod n,\ \ \ \ \ \ \ \ \ \,\color{#c00}{\ell}\ \ \rm roots\end{array}\\[.3em] &\iff& \left\{ \begin{array}{}x\equiv r_{\large i}\pmod{\! m}\\x\equiv s_{\large j}\pmod n\end{array} \right\}\ \ \ \ {\rm for}\ \ \begin{array}{}1 \le i \le k\\ 1\le j\le\ell\end{array}\\ &\overset{\rm\large CRT\!}\iff& \left\{ x\equiv t_{\,\large i\, j}\!\!\!\!\pmod{\!mn} \right\}\,\ \ \underbrace{{\rm for}\ \ 1 \le i\le k,\,\ 1\le j\le\ell}_{\Large \color{#c00}{k\,\cdot\, \ell}\ \,\rm roots\ \ \ \ \ \ \ \ \ \ }\\ \end{eqnarray}\qquad\qquad$$