# Prove $n$ is composite when it divides $(n-1)!$

I am having trouble solving this. Any tips of how to get this proof started would be greatly appreciated.

Let $n$ be a number in $\mathbb{N}$. Prove that if $n$ divides $(n-1)!$ then n is composite.

-
That's easier in contraposed form: If $n$ is prime then $n$ does not divide $(n-1)!$. –  Henning Makholm Sep 24 '11 at 15:24
You might want to restrict $n$ to be at least $2$. The case $n=1$ provides a trivial and uninteresting counterexample. –  Srivatsan Sep 24 '11 at 15:28
Note that it is not true that any composite number $n$ divides $(n-1)!$ (consider $n = 4$). –  TMM Sep 24 '11 at 15:29

I suggest using Euclid's Lemma, which states "If $p$ is prime and $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$." Suppose you knew $n$ divides $(n-1)!$ but $n$ were prime. Can you reach a contradiction using Euclid's Lemma?

I'll leave the rest to you (since this looks like homework), but please do ask for further clarification if you need it.

-
I think so, still not entirely sure. My reasoning is to essentially set (n-1)! to a number ab. By showing that neither a or b is divisible by n, n must be a composite number? –  user16626 Sep 24 '11 at 19:01
Well, you can certainly write $(n-1)! = (n-1)(n-2) \cdots (2)(1)$. Setting $a = (n-1)$ and $b = (n-2) \cdots (2)(1)$, what can you conclude (assuming $n$ is prime)? –  Hans Parshall Sep 24 '11 at 19:22
That n has two factors other than one and itself? Therefore it is not prime? –  user16626 Sep 24 '11 at 22:02
No. I was hinting more toward our prime $n$ must divide either $(n-1)$ or $(n-2) \cdots (2)(1)$. Why can't it divide $(n-1)$? –  Hans Parshall Sep 24 '11 at 22:33
You will get (1-1/n) in the one term and (1-2/n) in the other? Sorry I'm still getting the hang of these things. –  user16626 Sep 24 '11 at 23:21

If you agree to use Wilson's theorem, the problem is a one-liner. Because, if p is a prime, then p divides (p-1)!+1 : that's what the theorem says.Its proof essentially uses the concept of residues and can be found in any standard text on Number Theory. Now your problem is trivial, since the assumption that n is a prime leads to the dual result: n|(n-1)! and n|(n-1)!+1 => n|1=>n=1, a contradiction, since 1 is not a prime. However, the proof Hans Parshall gives using Euclid's lemma is still the most basic and better.

-