# If $\{a_1,\dots,a_{\phi(n)}\}$ is a reduced residue system, what is $a_1\cdots a_{\phi(n)}$ congruent to?

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.

-
The half-power is misleading if you did the problems up to this point and figured that half-powers were a result of computations like $x=m/x$ so $x^2=m$. –  peoplepower Dec 28 '12 at 9:57

## 1 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$.

-
Thanks fretty. ${}$ –  Noomi Holloway Dec 28 '12 at 10:09