Exercise 2.1.34 (Converse of Wilson's theorem.)

Proof. The Wilson’s theorem (Theorem 2.11) shows that if $m$ is prime, then $m$ divides $(m-1)!+1$. To prove the converse, we show that if $m>1$ is not prime (i.e $m$ is composite), then $m$ doesn’t divide $(m-1)!+1$.

Let $m>1$ a composite number. Then $m=\mathit{ab}$, where $1<a<m,1<b<m$.

Suppose first that $a\ne b$. Since $a\le m-1,b\le m-1$, then $a$, $b$ are distinct elements of the set $\{2,\dots ,m-1\}$, therefore $m=\mathit{ab}$ divides $(m-1)!$ (even if $a$, $b$ are not relatively prime). Hence $m\nmid (m-1)!+1$ (otherwise $m\mid 1=((m-1)!+1)-(m-1)!$).

The only case where the composite $m$ is not a product $m=\mathit{ab}$ where $1<a<b<m$ is the case where $m=p^2$ is the square of a prime number $p$. Indeed, write $m=p_1^{a_1}\cdots p_k^{a_k}(p_1<\cdots <p_k)$ the decomposition of $m$ in prime factors.

• If $k\ge 2$, we can take $a=p_1^{a_1},b=p_2^{a_2}\cdots p_k^{a_k}$ are distinct non trivial divisors of $m$.
• If $k=1$, $m=p^k$ for $p=p_1$. If $k>2$, then $a=p,b=p^{k-1}$ are distinct non trivial divisors of $m$.

It remains to prove $p^2\nmid (p^2-1)!+1$, if $p$ is some prime number.

Assume for contradiction that $p^2\mid (p^2-1)!+1$. A fortiori $p\mid (p^2-1)!+1$. But $p\le p^2-1$ ( because $p(p-1)\ge 1$), therefore $p\mid (p^2-1)!$, thus $p\mid 1$, and this is impossible since $p$ is prime.

We have proved that if $m$ is composite, then $m\nmid (m-1)!+1$.

To conclude, $m>1$ is prime if and only if $m$ divides $(m-1)!+1$ □