# 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.

###### Proof.

If $n$ is composite, then its greatest prime factor is at most $\frac{n}{2}$, and $$ as long as $n>2$ (and the smallest positive composite number is 4). Therefore, $(n-1)!$ being the product^{} of the numbers from 1 to $n-1$ includes among its divisors^{} 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 multiplicity^{} than $n$ does. For the special case of $n=4$, the congruence $(n-1)!\equiv 2modn$ is satisfied. For all larger composite $n$, the congruence $(n-1)!\equiv 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 $p\ne q$). So if $p$ and $q$ are distinct, then $(n-1)!$ has both prime factors^{} $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

- 1 Thomas Kochy, ”Elementary Number Theory with Applications”, 2nd Edition. London: Elsevier (2007): 324 - 325

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 |