# Prove that if $p_1,\dots,p_k$ are distinct odd primes then 1 has $2^k$ square roots $\mod m$ where $m$ is the product of the primes.

I think I am most of the way through this proof but I am stuck. Here was my approach: I looked at the square roots of $1$ mod $105$, and noticed that each one corresponded to one less than an integer multiple of a subset of the prime factors of $105$, i.e. we have for instance $71=24\cdot3-1$ or $29=2\cdot(3\cdot 5)-1$ and so on. I conjectured that given a subset of the prime factors of $m$, I could construct a unique square root of $1$ mod $m$, which would show that there are (at least) $2^k$ of them.

So I did that and I think that it worked. Pick some set of the prime factors of $m$, say $p_{a_1},\dots,p_{a_j}$. Claim: we can find a corresponding $n$ such that $n\prod_{i=1}^jp_{a_i}-1$ is a square root of $1$ mod $m$.

Proof: We are looking for a solution to

$$\left(n\prod_{i=1}^jp_{a_i}-1\right)^2\equiv 1 \pmod m$$ which may be rewritten as

$$\left(\prod_{i=1}^jp_{a_i}\right)^2n^2 - 2\prod_{i=1}^jp_{a_i}n\equiv 0 \pmod m$$

Now since $\prod_{i=1}^jp_{a_i}|m$ we may write this as $$\prod_{i=1}^jp_{a_i}n^2-2n \equiv 0\mod \frac{m}{\prod_{i=1}^jp_{a_i}}$$

or

$$n\left(\prod_{i=1}^jp_{a_i}n-2\right) \equiv 0 \mod {\frac{m}{\prod_{i=1}^jp_{a_i}}}$$

This has solutions when $n\equiv0\mod \frac{m}{\prod_{i=1}^jp_{a_i}}$ or when $\prod_{i=1}^jp_{a_i}n-2\equiv 0 \mod \frac{m}{\prod_{i=1}^jp_{a_i}}$. In the first case we end up with the same root for any choice of $p_{a_i}$'s so that's sort of a degenerate one. But in the second case we have $\prod_{i=1}^jp_{a_i}n\equiv 2 \mod \frac{m}{\prod_{i=1}^jp_{a_i}}$, which has a unique and nonzero solution for $n$. Plugging that $n$ back into $n\prod_{i=1}^jp_{a_i}-1$ thus gives a square root of $1$ mod $m$ which corresponds uniquely to your choice of prime factors, thus showing that there are (at least) $2^k-1$ square roots of 1. Then we add 1 in which corresponds to the empty set of prime factors and we get the full $2^k$.

My problem is ruling out the possibility of more square roots of 1, i.e. if $x^2\equiv1\mod m$ I need to show that it corresponds uniquely to something of the form $n\prod_{i=1}^jp_{a_i}-1$. This is proving to be difficult if not impossible.

I put a lot of work into going the one way and I really don't want it all to be for nothing. Can anyone see a way to go the other direction?

-

Since $x^2=1 \mod (p)$ has $2$ solutions, applying then the Chinese remainder theorem.

-

Note $\ p_1\!\cdots p_k\mid x^2\!-1 = (x\!-\!1)(x\!+\!1) \!\iff\! p_i \mid x\!-\!1\,\ {\rm or}\,\ p\mid x\!+\!1\!\iff\! x\equiv \pm1 \pmod{ p_i}$

Therefore there are precisely $\,2^k\,$ solutions $\ x\equiv\, (\pm1,\ldots,\pm1)\ \pmod{p_1,\ldots,p_k}$

Your method amounts to bijecting each solution with the subset of primes where $\,x\equiv -1,\,$ or, equivalently, the product of primes from that subset. So the solutions are in $1$-$1$ correspondence with all subsets of $\,\{p_1,\ldots,p_k\}\,$ or, equivalently, all factors of $\,p_1\!\cdots p_k.$

-

To elaborate on Ma Ming's answer, note that every cyclic group $C$ of even order $2b$ has a unique element of order $2$, namely the $b$-th power of a generator, which defines an order-$2$ subgroup in $C$. Your question concerns the group $\mathbb{Z}_m^*$ which is the product of the groups $\mathbb{Z}_{p_i}^*$, each of even order. The subgroup of $\mathbb{Z}_m^*$ given by the product of the order-$2$ subgroups as above is precisely the collection of the "square roots" you are interested in. Since there are $k$ of these order-$2$ subgroups, the order of the product is $2^k$.

-