I'm trying work on problem 11 of Chapter 3 in Ireland and Rosen's Number Theory.
Suppose $\{a_1,\dots,a_{\phi(n)}\}$ is a reduced residue system modulo $n$. Let $N$ be the number of solutions to $x^2\equiv 1\pmod{n}$, then $ a_1\cdots a_{\phi(n)}\equiv (-1)^{N/2}\pmod{n}. $
How can this be shown? I know that if $n=p_1^{\alpha_1}\cdots p_m^{\alpha_m}$, then $N=\prod N(p_i^{\alpha_i})$ where $N(p_i^{\alpha_i})$ denotes the number of solutions to $x^2\equiv 1\pmod{p_i^{\alpha_i}}$.
Also, if $x_0$ is a solution, then it is also a solution to $x^2\equiv 1\pmod{p_i}$ for any prime in the factorization of $n$. This implies that $x_0\equiv \pm 1\pmod{p_i}$, so that $x_0$ is coprime to all prime factors of $n$, and thus coprime to $n$.
But I'm not seeing a connection between the left and right hand side products of the congruence in question. Thanks.