converse of Wilson’s theorem


Theorem. Given an integer n>1, if (n-1)!-1modn then n is prime.

To prove the converseMathworldPlanetmath of Wilson’s theorem it is enough to show that a composite numberMathworldPlanetmath can’t satisfy the congruenceMathworldPlanetmathPlanetmathPlanetmath. A number that does satisfy the congruence, then, would be not composite, and therefore prime.

Proof.

If n is composite, then its greatest prime factor is at most n2, and n2<(n-1) as long as n>2 (and the smallest positive composite number is 4). Therefore, (n-1)! being the productPlanetmathPlanetmath of the numbers from 1 to n-1 includes among its divisorsMathworldPlanetmathPlanetmath the greatest prime factor of n, and indeed all its proper divisors. In fact, for composite n>4, it is the case that (n-1)! not only has all the same proper divisors of n as a subset of its own proper divisors, but has them with greater multiplicityMathworldPlanetmath than n does. For the special case of n=4, the congruence (n-1)!2modn is satisfied. For all larger composite n, the congruence (n-1)!0modn is satisfied instead of the congruence stated in the theorem. ∎

The special case of n=4 deserves further special attention, as it is an exception which proves the rule. With any other semiprime n=pq, with either p or q being a prime greater than 2, the product (n-1)! contains, in addition to p and q, both (p-1)q and p(q-1) (which are distinct numbers if pq). So if p and q are distinct, then (n-1)! has both prime factorsMathworldPlanetmath p and q with a multiplicity of at least 2, which is greater than the multiplicity of 1 in the semiprime pq. But with 4, the numbers (p-1)q and p(q-1) 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

Title converse of Wilson’s theorem
Canonical name ConverseOfWilsonsTheorem
Date of creation 2013-03-22 17:58:55
Last modified on 2013-03-22 17:58:55
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 7
Author PrimeFan (13766)
Entry type Theorem
Classification msc 11-00