Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can u help me with this questionIf n ≥ 6 is a composite

  1. Oct 28, 2009 #1
    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)!
     
  2. jcsd
  3. Oct 28, 2009 #2
  4. Oct 28, 2009 #3

    mathman

    User Avatar
    Science Advisor
    Gold Member

    Re: factorials

    Two cases:

    1. n not a square, then n=km, where k different from m, k<n, and m<n. Then both are seperate 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.
     
  5. Oct 28, 2009 #4
    Re: factorials

    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?
     
  6. Oct 28, 2009 #5
    Re: factorials

    thanks so much ... now i get it :)
     
  7. Oct 28, 2009 #6
    Re: factorials

    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.
     
  8. Oct 29, 2009 #7
    Re: factorials

    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)!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Can u help me with this questionIf n ≥ 6 is a composite
  1. Divisibility of n by 6 (Replies: 10)

Loading...