11-00-ConverseOfWilsonsTheorem.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{ConverseOfWilsonsTheorem}
\pmcreated{2013-03-22 17:58:55}
\pmmodified{2013-03-22 17:58:55}
\pmowner{PrimeFan}{13766}
\pmmodifier{PrimeFan}{13766}
\pmtitle{converse of Wilson's theorem}
\pmrecord{7}{40491}
\pmprivacy{1}
\pmauthor{PrimeFan}{13766}
\pmtype{Theorem}
\pmcomment{trigger rebuild}
\pmclassification{msc}{11-00}

\endmetadata

% 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
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
%%%\usepackage{xypic}

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

% define commands here

\begin{document}
{\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.

\begin{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.
\end{proof}

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.

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