Wilson's theorem gives that $(p-1)! \equiv -1 \mod p$ when p is a prime number, while for a composite number n, either $(n-1)! \equiv 0 \mod n$ or $(n-1)! \equiv 2 \mod n$ if $n=4$. The problem being that for the composite number n, (n-1)! contains factors which are not relatively prime to n. This raises the question of what happens if we modify the product (n-1)! to include only those numbers which are relatively prime to n. In other words, the product

(1)where $\gcd (i_j,n) =1$ and $1 \leq i_j \leq n$ for all $i_j$ on the list, and $\varphi(n)$ is the number of such integers. In other words $\varphi$ is the Euler Phi function.

The first thing to notice is that if n is prime, then $i_1 \times i_2 \times \dots \times i_{\varphi(n)} = (n-1)!$ and Wilson's theorem applies. But if n=8, then $i_1 \times i_2 \times \dots \times i_{\varphi(n)} = 1 \times 3 \times 5 \times 7 \equiv 1 \mod 8$, so we do get something different than we had before.

As in the proof of Wilson's theorem, the product $i_1 \times i_2 \times \dots \times i_{\varphi(n)} \mod n$ simplifies down to the solutions of $x^2 \equiv 1 \mod n$. All other integers will be canceled by their inverses. Of course $x^2 \equiv 1 \mod n$ has either one solution or an even number of solutions (if k is a solution then so is -k), so as in the last problem of homework 3 you get that

(2)with the sign on the right hand side determined by the exact number of solutions to $x^2 \equiv 1 \mod n$. You can also show that the sign is negative only when $n=p^r$ or $n=2p^r$ where p is a prime and r is a non-negative integer.