1
$\begingroup$

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.

  • 0
    Note that it is not true that any composite number $n$ divides $(n-1)!$ (consider $n = 4$).2011-09-24

2 Answers 2

2

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.

  • 0
    Alright, I think I get what you're pointing at. Thanks for all of your help.2011-09-25
0

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.