Fork me on GitHub
Math for the people, by the people.

User login

converse of Wilson's theorem

% this is the default PlanetMath preamble.  as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these

% used for TeXing text within eps files
% need this for including graphics (\includegraphics)
% for neatly defining theorems and propositions
% making logically defined graphics

% there are many more packages, add them here as you need them

% define commands here

{\bf Theorem}. Given an integer $n > 1$, if $(n - 1)! \equiv -1 \mod n$ then $n$ 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.

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.

\bibitem{tk} Thomas Kochy, ''Elementary Number Theory with Applications'', 2nd Edition. London: Elsevier (2007): 324 - 325