converse of Wilson’s theorem
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.
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.
- 1 Thomas Kochy, ”Elementary Number Theory with Applications”, 2nd Edition. London: Elsevier (2007): 324 - 325
|Title||converse of Wilson’s theorem|
|Date of creation||2013-03-22 17:58:55|
|Last modified on||2013-03-22 17:58:55|
|Last modified by||PrimeFan (13766)|