Exercise 3.10

Proof.

Suppose that $n>1$ is not a prime. Then $n=\mathit{uv}$, where $2\le u\le v\le n-1$.

$\text{∙}$ If $u\ne v$, then $n=\mathit{uv}\mid (n-1)!=1\times 2\times \cdots \times u\times \cdots \times v\times \cdots \times (n-1)$ (even if $u\wedge v\ne 1$ !).

$\text{∙}$ If $u=v$, then $n=u^2$ is a square.

If $u$ is not prime, $u=\mathit{st},2\le s\le t\le u-1\le n-1$, and $n=u^{\prime }{v}^{\prime }$, where $u^{\prime }=s,v^{\prime }=s{t}^2$ verify $2\le u^{\prime }<v^{\prime }\le n-1$. As in the first case, $n=u^{\prime }{v}^{\prime }\mid (n-1)!$.

If $u=p$ is a prime, then $n=p^2$.

In the case $p=2$, $n=4$ and $n=4\nmid (n-1)!=6$. In the other case, $p>2$, and $(n-1)!=(p^2-1)!$ contains the factors $p,2p$, where $1<p<2p<p^2$, so $p^2\mid (p^2-1)!$, that is $n\mid (n-1)!$.

Conclusion : if $n$ is not a prime, $(n-1)!\equiv 0(\mathit{mod}n)$, except when $n=4$. □