converse of Wilson’s theorem
Theorem. Given an integer , if then is prime.
To prove the converse of Wilson’s theorem it is enough to show that a composite number
can’t satisfy the congruence
. A number that does satisfy the congruence, then, would be not composite, and therefore prime.
Proof.
If is composite, then its greatest prime factor is at most , and as long as (and the smallest positive composite number is 4). Therefore, being the product of the numbers from 1 to includes among its divisors
the greatest prime factor of , and indeed all its proper divisors. In fact, for composite , it is the case that not only has all the same proper divisors of as a subset of its own proper divisors, but has them with greater multiplicity
than does. For the special case of , the congruence is satisfied. For all larger composite , the congruence is satisfied instead of the congruence stated in the theorem.∎
The special case of deserves further special attention, as it is an exception which proves the rule. With any other semiprime , with either or being a prime greater than 2, the product contains, in addition to and , both and (which are distinct numbers if ). So if and are distinct, then has both prime factors and with a multiplicity of at least 2, which is greater than the multiplicity of 1 in the semiprime . But with 4, the numbers and are both 2, and so 3! includes 2 as a factor with only a multiplicity of 1, which is less than that factor’s multiplicity in 4.
References
- 1 Thomas Kochy, ”Elementary Number Theory with Applications”, 2nd Edition. London: Elsevier (2007): 324 - 325