# $n|(n-1)!$ for all composite numbers $n>4,n\in \mathbb{N}$

$n|(n-1)!$ for all composite numbers $n>4,n\in \mathbb{N}$!

Can anyone provide an elementary general or even combinatorial proof of this.

-
Have you heard of Wilson's theorem? –  draks ... Feb 9 '13 at 19:38
Changed to more informative and less subjective title. –  Pedro Tamaroff Feb 9 '13 at 19:41

Write $n=ab$ with $a,b<n$. If $a\ne b$, then the factors $a$ and $b$ occur in $(n-1)!=1\cdot 2\cdot \ldots \cdot (n-1)$. If on the other hand $a=b$ (i.e. $n$ is a perfect square), then $b\ge 3$ because $n>4$, hence the distinct factors $a$ and $2a<n$ occur in $(n-1)!=1\cdot 2\cdot \ldots \cdot (n-1)$.

Remark: Note that we can improve this to $n|(n-3)!$ for composite $n>4$: If $a< b$, then $b\le \frac n2\le n-3$. And if $a=b\ge 3$, then $2a\le 3a-3\le n-3$.

-
Your last bound is sharp, as $9|6!$ but does not divide $5!$. –  Ross Millikan Feb 9 '13 at 19:37
@RossMillikan Of course, otherwise I would have sharpened it. ;) For bigger $n$ we can go down to $\lfloor\frac n2\rfloor!$ (worst case is if $n$ is twice a prime) –  Hagen von Eitzen Feb 9 '13 at 22:09

Hint $\rm\,\ n\, =\, \color{#C00}a\:\!\color{#0A0}b\:|\:1\!\cdot\! 2\cdots\color{#C00} a\:\color{#0A0}{(a\!+\!1)\, (a\!+\!2) \cdots (a\!+\!b)}\cdots (ab\!-\!1)\,\$ when $\rm\,\ a\!+\!b \le ab\!-\!1$

Note $\$ That $\rm\:\color{#0A0}b\:$ divides the above $\rm\color{#0A0}{green}$ term needn't deduced from the fact that it is divisible by $\rm\,b!\,$ by integrality of the binomial coefficient $\rm\:(a\!+\!b:a),\:$ as is often done. Rather, it follows from the much simpler fact that any sequence of $\rm\,b\,$ consecutive integers contains a multiple of $\rm\,b,\,$ which is an immediate consequence of (Euclidean) division. For completeness. here is a proof: $$\rm\ mod\ b\!:\ a\!+\!b\equiv k\in [\color{#C00}0,\color{#0A0}{b\!-\!1}]\ \Rightarrow\ b\:|\:a\!+\!b\!-\!k\in [\color{#0A0}{a\!+\!1},\color{#C00}{a\!+\!b}]$$

-
Of course $a+b\le ab-1$ is equivalent to $2\le ab-a-b+1=(a-1)(b-1)$ and hence to $n=ab$ being a nontrivial factorization ($a\ne 1\ne b$) and not $a=b=2$ (i.e. doesn't work for $n=4$). –  Hagen von Eitzen Feb 23 '13 at 20:56