28. The Theorems of Fermat and Wilson.—Let
where , be a complete set of residues prime to the modulus . Then if is any number prime to , the residues also form a complete set prime to (§ 27). Consequently , and dividing by , which is prime to the modulus, we infer that
which is the general statement of Fermat's theorem. If is a prime , it becomes
.
For a prime modulus there will be among the set
just one and no more that is congruent to : let this be . If
, we must have , and hence : consequently the residues can be arranged in pairs such that . Multiplying them all together, we conclude that and hence, since , . which is Wilson's theorem. It may be generalized, like that of Fermat, but the result is not very interesting. If is composite cannot be a multiple of : because will have a prime factor which is less than , so that . Hence Wilson’s theorem is invertible: but it does not supply any practical test to decide whether a given number is prime.