(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) TODO