Show that $x^2 \equiv 1 \pmod{n}$ can have arbitrarily many solutions? 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!
 A: 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$.
