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