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.

  • 8
    That's easier in contraposed form: If $n$ is prime then $n$ does _not_ divide $(n-1)!$.2011-09-24
  • 0
    You might want to restrict $n$ to be at least $2$. The case $n=1$ provides a trivial and uninteresting counterexample.2011-09-24
  • 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
    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?2011-09-24
  • 0
    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)?2011-09-24
  • 0
    That n has two factors other than one and itself? Therefore it is not prime?2011-09-24
  • 0
    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)$?2011-09-24
  • 0
    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.2011-09-24
  • 0
    Can a positive integer ever divide a smaller positive integer?2011-09-25
  • 0
    I understand that for the first term (n-1). But looking at the (n-2)...(2)(1) term, doesn't that have the possibility to become an integer that is greater than n and therefore can be divisible?2011-09-25
  • 0
    Repeat the argument with $a = (n-2)$ and $b = (n-3) \cdots (2)(1)$. Continue repeating the argument until you reach something ridiculous, like $n \mid 1$.2011-09-25
  • 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.