# Why does the product of all the elements in $\mathbb{Z} _{m}^{*}$ equal to $\pm {1} \mod{m}$?

I am asked to prove that the product of all the elements in $\mathbb{Z}_{m}^{*}$ for $m>2$ equals to $\pm {1} \mod{m}$. So far I tried the following direction. I defined: $$S_{1} = \{x \in Z^*_{m} : x^2\equiv 1\mod{m}\}$$ and $$S_{2} = \{x \in Z^*_{m} : x^2\not \equiv 1\mod{m}\}$$ If $P_{i}$ is the product of all the elements in $S_{i}$ for $i=1,2$, I proved that it holds $$P = P_1\cdot P_2$$ I already proved that $P_2=1 \mod m$. I need to prove $P_{1}= \pm 1 \mod{m}$. I already know that $P_{1}^2 = 1\mod{m}$ but unfortunately this doesn't imply the required. Can I get a hint on how to prove that $P_{1}= \pm 1 \mod{m}$? Thank you

• A good start. One way of dealing with $S_1$ is to first consider the case when $m$ is a prime power (when that prime is equal to two there is an extra obstacle). Then apply the Chinese Remainder theorem to deduce $P_1$ modulo all the prime powers that appear in the factorization of $m$. Possibly there is an easier way forward. I had to wake up very early this morning, so I'm not firing on all cylinders at the moment. Apr 13 '18 at 20:10
• Call $x,y \in S_1$ equivalent if $x = y$ or $x = -y$. Partition $S_1$ into equivalence classes and look at each separately first. Apr 13 '18 at 20:12
• @DanielFischer This is brilliant. If $x \in S_{1}$ then $m-x \in S_{1}$ and $x\cdot (p-x) \equiv -1 \mod{m}$. Thank you. Apr 13 '18 at 20:21
• @JyrkiLahtonen Thank you too Apr 13 '18 at 20:21
• @Ben See this answer for more on the method hinted by Daniel. Nov 23 '20 at 13:16

On $S_1$, introduce the equivalence relation
$$x \sim y \iff (x = y \lor x = -y)\,.$$
Then every equivalence class contains exactly two elements of $\mathbb{Z}_m^{\ast}$ (if $m > 2$ is even, then $m/2$ is not coprime to $m$, so we have $x \neq -x$ for all $x \in \mathbb{Z}_m^{\ast}$), and
$$x\cdot (m-x) = mx - x^2 \equiv -x^2 \equiv -1 \pmod{m}\,.$$
$$P_1 \equiv (-1)^{(\operatorname{card} S_1)/2} \pmod{m}\,.$$