Exercise 1.3.27 ( $n \mid (n-1)!$ for all composite $n>4$)

Proof. Since $n$ is composite, $n>1$. Write

its decomposition in prime factors, where $a_i>0$.

• If $l>1$, then $n=\mathit{ab}$, where

  $$a=p_1^{a_1},b=p_2^{a_2}\cdots p_l^{a_l},$$

  so that $a\wedge b=1$.

  Since $a>1,b>1$, we have $1<a<n,1<b<n$, thus $a\mid (n-1)!$ and $b\mid (n-1)!$. There $a\wedge b=1$, therefore $n=\mathit{ab}\mid (n-1)!$.

  Note : In fact, it is sufficient that $a,b$ are two distinct positive integers less that $n$ to show that $\mathit{ab}\mid (n-1)!$.

• If $l=1$, then $n$ is a prime power, $n=p^{\alpha }$ $(p=p_1,\alpha =a_1>0)$. We want to show that $p^{\alpha }\mid (p^{\alpha }-1)!$. The multiples of $p$ less that $p^{\alpha }-1$ are

  $$p,2p,3p,\dots ,(p^{\alpha -1}-1)p.$$

  Therefore

  $$p^{p^{\alpha -1}-1}\mid (p^{\alpha }-1)!.$$

  It remains to show that $p^{\alpha -1}-1\ge \alpha$ if $p>2,\alpha >1$, or $p=2$ and $\alpha >2$.

  • If $p=2$, we show by induction for $\alpha \ge 3$ that $2^{\alpha -1}-1\ge \alpha$.

    First $2^{3-1}-1\ge 3$. Suppose that $2^{\alpha -1}-1\ge \alpha$ for some $\alpha \ge 3$. Then

    $$2^{\alpha }-1=2\cdot 2^{\alpha -1}-1\ge 2(\alpha +1)-1=2\alpha +1\ge \alpha +1.$$

    The induction is done, so $2^{\alpha -1}-1\ge \alpha$ for every $\alpha \ge 3$.

  • Suppose that $p>2$. We know that $2^a>a$ for every integer $a\ge 0$ (because $\mathrm{Card}(E)<\mathrm{Card}(𝒫(E))$, where $\mathrm{Card}(E)=a$). For $a=\alpha -1\ge 0$, we obtain

    $p^{\alpha -1}-1>2^{\alpha -1}-1$, thus $p^{\alpha -1}-1\ge 2^{\alpha -1}>\alpha -1$, therefore $p^{\alpha -1}-1\ge \alpha$.

  In both cases ( $p>2$ and $\alpha >1$, or $p=2$ and $\alpha >2$) , $p^{\alpha -1}-1\ge \alpha$. Therefore $p^{\alpha }\mid p^{\alpha -1}-1$, and $p^{\alpha -1}-1\mid (p^{\alpha }-1)!$, so

  $$p^{\alpha }\mid (p^{\alpha }-1)!.$$

This shows that $n\mid (n-1)!$ for all composite $n>4$.

(Alternatively, we can use the note of the first part, but it remains to show that $p^2\mid (p^2-1)!$.) □