Does n Divide (n-1)! for Composite and Prime Numbers?

[margot]

can u help me with this question

If n ≥ 6 is a composite integer, then n |(n − 1)! If n is a prime number, then n does not divide (n−1)!

 

[VeeEight]

Try working mod n. Also, see http://en.wikipedia.org/wiki/Wilson's_theorem

 

[mathman]

Two cases:

1. n not a square, then n=km, where k different from m, k<n, and m<n. Then both are separate factors of (n-1)! so that n divides (n-1)!

2. n a square of a prime p (if n is a square of non-prime case 1 could be used), then let k=p and m=2p, both < n, since p > 2. Then we have 2n divides (n-1)! so that n divides (n-1)!
This also illiustrates why 4 has to be excluded.

 

[Bingk]

For your second part, if n is prime, then n cannot divide any number less than itself. In other words, it is not in the prime factorization of those numbers. So a product of those numbers will still not contain that prime number, and thus n will never divide (n-1)!

For your first part, again, look at the prime factorization. n is composite, so it's prime factors will be less than n. What happens when you do the product (n-1)!?
Let's investigate why n ≥ 6 and composite ..
The first composite number is 4, this is 2^2 (prime factorization). (4-1)! = 3*2 ... clearly 2^2 can't divide 3*2, because there's not enough powers of 2.
The next composite number is 6 = 2*3. (6-1)! = 5*4*3*2 ... can you see that 6|5!? (The 3*2 parts cancel and you're left with 5*4=20).

Let's do another example ... say n = 216 = 2^3*3^3. (216-1)! = 215*214*213*...*27*...*8*...*4*3*2. You will notice that 27=3^3 and 8=2^3 ... so for that last bit we have 215! = 215*...*3^3*...*2^3*...*4*3*2. So 216|215!

Do you see what's going on?

 

[margot]

thanks so much ... now i get it :)

 

[ramsey2879]

For your second part, if n is prime, then n cannot divide any number less than itself. In other words, it is not in the prime factorization of those numbers. So a product of those numbers will still not contain that prime number, and thus n will never divide (n-1)!

For your first part, again, look at the prime factorization. n is composite, so it's prime factors will be less than n. What happens when you do the product (n-1)!?
Let's investigate why n ≥ 6 and composite ..
The first composite number is 4, this is 2^2 (prime factorization). (4-1)! = 3*2 ... clearly 2^2 can't divide 3*2, because there's not enough powers of 2.
The next composite number is 6 = 2*3. (6-1)! = 5*4*3*2 ... can you see that 6|5!? (The 3*2 parts cancel and you're left with 5*4=20).

Let's do another example ... say n = 216 = 2^3*3^3. (216-1)! = 215*214*213*...*27*...*8*...*4*3*2. You will notice that 27=3^3 and 8=2^3 ... so for that last bit we have 215! = 215*...*3^3*...*2^3*...*4*3*2. So 216|215!

Do you see what's going on?

That will work when the composite number is a*b where a<b but doesn't address the second case where a = b as covered by mathman.

 

[Bingk]

Yeah, I admit that I oversimplified my example, just to help see what's going on ...

For the case when n=p^2, this is what happens, 1<p<p^2 and 1<qp<p^2, where q is prime and q<p. so p and qp are still factors in (n-1)! so if we regroup it, (n-1)! = (n-1)*(n-2)*...*qp^2*...4*3*2 and we can see that p^2 is a factor in (n-1)!, so n|(n-1)!. It's just a matter of looking at the prime factorization of (n-1)! and comparing it to the prime factorization of n.

We can also generalize, for n=p^a, a>2, we have that p^(a-1) and p is a factor in (n-1)! so we p^(a-1)*p = p^a is a factor in (n-1)! so n|(n-1)!