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.
Best Answer
Think about how you prove Wilson's theorem.
$(p-1)!$ can really be viewed a product over all elements of the group $(\mathbb{Z}/p\mathbb{Z})^{\times}$. Now each element in this product has an inverse mod $p$ and so when actually calculating this product mod $p$ all terms will cancel...except those that are self inverse.
What are the self inverse elements? Well those are the ones such that $x^2 \equiv 1 \bmod p$, (i.e. $1,p-1$). Thus $(p-1)! \equiv (1)(p-1) \equiv -1 \bmod p$.
The exact same proof will work for this more general theorem except the group is now $(\mathbb{Z}/n\mathbb{Z})^{\times}$ and you have more self inverse elements (denoted $b_1, b_2, ..., b_{N}$ where $N$ is the number of solutions to $x^2 \equiv 1 \bmod n$).
Thus as earlier: $a_1 a_2...a_{\phi(n)} \equiv b_1b_2 ... b_{N} \bmod n$.
Now it is not difficult to see that $N$ must be even. Also if $c$ is self inverse then $n-c$ is too (compare this with the mod $p$ case). Then the product $c(n-c) \equiv -c^2 \equiv -1 \bmod n$.
So pairing the $b$'s in this way we see that:
$b_1 b_2... b_N \equiv (-1)^{\frac{N}{2}} \bmod n$.