## You are here

Homeconverse of Wilson's theorem

## Primary tabs

# 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 $\displaystyle\frac{n}{2}$, and $\displaystyle\frac{n}{2}<(n-1)$ 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 2\mod n$ is satisfied. For all larger composite $n$, the congruence $(n-1)!\equiv 0\mod n$ 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\neq 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

## Mathematics Subject Classification

11-00*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections