Show that $x^2 \equiv 1 \pmod{n}$ can have arbitrarily many solutions?

Question

Equivalently, show that for every $m$, there exists some $n$ such that $x^2 \equiv 1 \pmod{n}$ has at least $m$ solutions.

Would appreciate any help or hints. I have a feeling this may be a pretty simple proof, but right now I am stuck. Thanks!

Answer 1

Expanding on my comment:

Let $k$ be some positive integer such that $2^k \geq m$. Let $p_1, p_2, p_3, \cdots, p_k$ be $k$ distinct odd primes. (It's possible to choose $k$ distinct odd primes since there are infinitely many primes.)

Consider $n = p_1 p_2 p_3 \cdots p_k$, and look at the system of congruences $$\begin{align*} x \equiv \pm 1 & \pmod{p_1} \\ x \equiv \pm 1 & \pmod{p_2} \\ x \equiv \pm 1 & \pmod{p_3} \\ & \vdots \\ x \equiv \pm 1 & \pmod{p_k} \end{align*}$$ where we choose either $+1$ or $-1$ for each prime. There are two choices for each prime, and so there are $2^k \geq m$ possible systems that can arise in this way.

by the Chinese Remainder Theorem, each one of these $2^k$ systems has some solution $x$ modulo $p_1 p_2 p_3 \cdots p_k = n$. No two systems give us the same value for $x$ modulo $n$, since if $x_1$ and $x_2$ arise from two different systems of congruences then there is some prime $p_i$ such that $$ \begin{align*} x_1 & \equiv \pm 1 \pmod {p_i} && \text{ but } & x_2 & \equiv \mp 1 \pmod {p_i} \end{align*} $$

(i.e. $x_1$ and $x_2$ have different remainders modulo some prime factor of $n$)

This shows that $x_1$ and $x_2$ are not congruent modulo $n$, and so we in fact get $2^k$ distinct values of $x$ by looking at systems of congruences of the form given above.

Now for any such solution $x$, we have that $$\begin{align*} x^2 \equiv (\pm 1)^2 & \equiv 1 \pmod{p_1} \\ x^2 \equiv (\pm 1)^2 & \equiv 1 \pmod{p_2} \\ x^2 \equiv (\pm 1)^2 & \equiv 1 \pmod{p_3} \\ & \vdots \\ x^2 \equiv (\pm 1)^2 & \equiv 1 \pmod{p_k} \end{align*}$$

and so we see (since the $p_i$ are pairwise relatively prime) that $x^2 \equiv 1 \pmod n$.

Thus each of the $2^k \geq m$ possible values for $x$ are a solution to $x^2 \equiv 1 \pmod n$.