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.

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.

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

2 Answers 2

up vote 2 down vote accepted

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.

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

share|improve this answer

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.