Wilson's Theorem states that an integer $n$ is prime if and only if $(n - 1)! \equiv -1\ (mod\ n)$, or we can also say:
$(n - 1)! = an - 1$ for some integer $a$ if and only if $n$ is prime.
Since the theorem states $if\ and\ only\ if$ it means if one is true then the other condition is also true. Thus, this proof can be broken down into two parts:
$A)$ For any positive integer $n \gt 1$, if $(n-1)! \equiv -1\ (mod\ n)$ then $n$ is prime.
$B)$ If any integer $p$ is prime, then $(p-1)! \equiv -1\ (mod\ p)$.
$\underline{Proof\ (Part\ A)}:$
Let us assume the contradiction of this to be true, that is,
$(m-1)! \equiv -1\ (mod\ m)$ where $m$ is a composite integer.
We know that $m$ and $m-1$ are coprime for any $m \gt 1$, therefore $m-1$, $m$ do not share a common factor.
Since $m$ is composite, it has a factor $q$, and $q$ does not divide $m-1$, therefore $1 \lt q \lt m-1$.
Let $m = qr$, where $q,\ r$ are positive integers greater than $1$.
$(m-1)! \equiv -1\ (mod\ m)$ we can write $(m-1)! = am - 1$ for some integer $a$.
$\Rightarrow$ $(m-1)! = aqr - 1$
Let us take a look at the $L.H.S$ of the above equation.
Since $(m - 1)!$ is a product of all integers from $1$ to $(m-1)$, it includes $q$ as a factor as well, and hence is divisible by $q$.
Therefore, $(m-1)! \equiv 0\ (mod\ q)$
-----------book page break-----------
Now let us take a look at the $R.H.S.$ of the same equation.
Taking modulo $q$ of right hand side of the equation $aqr - 1$, we get:
Since the left hand side gives $0$ and the right hand side gives $-1$ modulo $q$, this relationship is not possible. Therefore, $m$ cannot be composite.
$\underline{Proof\ (Part\ B)}:$
Let $p$ be a prime. Since $p$ is a prime, it is coprime to every positive integer less than $p$, which means
$1,\ 2,\ ...,\ (p-1)$ are coprimes to $p$.
We learnt the following aspects of inverses from ,
- every number that is coprime to $p$ has an inverse modulo $p$
- inverse of $1$ is $1$ and inverse of $p-1$ is $p-1$
- every number less than $p$ maps to a unique inverse
Since $p$ is odd, $p - 2$ is odd and $1$ to $p-2$ is an odd count of integers.
Therefore $2$ to $p - 2$ is an even count of integers.
We can divide this numbers into two groups, where each number in the first group has its inverse modulo $p$ in the second group.
Now when we multiply these numbers from the two groups together modulo $p$, each number from the first group will multiply with the corresponding inverse from the second group leaving $1$.