If and only if is a prime, then is a multiple of . In other words .
Wilson's theorem is easily verifiable for 2 and 3, so let's consider . If is composite, then its positive factors are among
Hence, , so .
However if is prime, then each of the above integers are relatively prime to . So for each of these integers a there is another such that . It is important to note that this is unique modulo , and that since is prime, if and only if is or . Now if we omit 1 and , then the others can be grouped into pairs whose product is congruent to one,
Finally, multiply this equality by to complete the proof.
Let be a prime number such that dividing by 4 leaves the remainder 1. Show that there is an integer such that is divisible by .