(i) Let $\{r_1, r_2, r_3, \ldots , r_{\phi(n)}\}$ be a set of reduced residue system modulo $n$.
Prove that
$$ r_1 × r_2 × r_3 × ⋯ × r_{\phi(n)} \equiv \pm 1 \pmod n $$
(ii) Prove Wilson’s Theorem.
(i) We showed in the previous exercise that every element of a reduced residue system has an inverse, and that inverse is in the same reduced residue system.
Let $r_k$ be the inverse of $r_j$. That is
$$ r_j \times r_k \equiv 1 \pmod n $$
where $1 \le j,k \le \phi(n)$.
The inverse is unique, which we show as follows. If $r_a$ and $r_b$ are the inverse of $r_j$ then
$$ r_j \times r_a \equiv 1 \equiv r_j \times r_b \pmod n $$
Since $\gcd(n,r_k)=1$ we can cancel $r_j$ to give $ r_a \equiv r_b \pmod n $. So the inverse of $r_j$ is unique.
There are two cases for $r_j$:
- $r_j$ is not its own inverse, that is $r_j \ne r_k$
- $r_j$ is its own inverse, that is $r_j = r_k$
In the first case, $r_j \ne r_k$, we can pair $r_j$ with its unique inverse $r_k$. The product of both is 1 modulo $n$.
$$ r_j \times r_k \equiv 1 \pmod n $$
In the second case, $r_j$ is its own inverse. This means the element congruent to $-r_j$ is also its own inverse, because
$$-r_j \times -r_j \equiv r_j \times r_j \equiv 1 \pmod n$$
That element is $(n-r_j)$ in the reduced residue system set. Pairing $r_j$ and $(n-r_j)$, we have
$$ r_j \times (n - r_j) \equiv (n \times r_j) - (r_j \times r_j) \equiv -1 \pmod n \pmod n $$
If there are an odd number of such pairs, then the product is -1, otherwise the product is +1.
We have shown the product of the residues in the reduced residue system is the product of several factors 1 and -1, giving an overall product of $\pm1$. That is,
$$ r_1 × r_2 × r_3 × ⋯ × r_{\phi(n)} \equiv \pm 1 \pmod n $$
(ii) We remind ourselves of Wilson's Theorem (4.4), which states that if $p$ is prime then $(p-1)! \equiv -1 \pmod p$.
We use the result above, with $n$ set to be prime $p$, which means the reduced residue system is $\{1, 2, \ldots, p-1\}$,
$$ 1 \times 2 \times 3 \times \ldots \times p-1 \equiv \pm 1 \pmod n $$
There is one pair of self-inverse residues, 1 and (p-1), which means their product is -1. The remaining residues are not self-inverses, by exercise (3.3).16, and their product is 1. And so the product of all the residues is 1, giving us the desired result.
$$ (p-1)! \equiv -1 \pmod p $$
Note: Other texts give Wilson's Theorem as bidirectional, that $p$ is prime if and only if $(p-1)! \equiv -1 \pmod p$.