Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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.

Thanks in advance.

share|improve this question
1  
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

2 Answers 2

up vote 14 down vote accepted

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$.

share|improve this answer
    
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}]$$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.