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

Product of r consecutive numbers divisible by r!

  1. Jul 11, 2007 #1
    1*2*3...r is congruent to 0modr!

    2*3*4...(r+1) is congruent to 0modr!

    3*4*5...(r+1)(r+2) is congruent to 0modr! because the last 2 factors must contain 2.

    So if I carry on in this fashion is this sufficient to prove that the product of r consecutive numbers is divisible by r!?

    It seems like circular argument to me and so I'm not sure if it's justified.
  2. jcsd
  3. Jul 12, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    There's a slick combinatorial proof. How many subsets of size r does a set with r+k elements have?
  4. Jul 12, 2007 #3
    Ummm... Why must the last 2 factors contain 2? If you mean the last two factors are divisible by 2, you do realize that not both of r+1, and r+2 can be divisible by 2 right?

    What exactly is this fashion? What happens when your set of r consecutive integers no longer contains r?
  5. Jul 12, 2007 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    When you've finished verifying all of the infinitely many cases you will have proved the result. It could be a while before we hear from you again, though.
  6. Jul 12, 2007 #5
    could someone clarify what's wrong with it?
  7. Jul 12, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    1. You should have said 'one of the last two factors r+1 and r+2 is divisible by 2'

    2. It is not clear that your idea actually works for 4*5*....*r+3, or any other example - you will need to make more of an argument when you start wishing to distribute lots of prime factors, and explain why there are enough powers of 2, say, later on.

    3. Even if it did, you are attempting to check infinitely many things in turn. That is not a proof - you will never be able to verify all of the cases by hand as you assert you wish to.
  8. Jul 12, 2007 #7
    Personally, I would start off in a slightly different direction: Let's say you have your set of r consecutive numbers, [itex]a_1[/itex] to [itex]a_r[/itex]. Have a look at the first one, [itex]a_1[/itex].
    1st case: Let's say [itex]a_1[/itex] is divisible by r. Then you're done.
    2nd case: Let's say [itex]a_1[/itex] is not divisible by r. Then integer division will leave you with a rest between 1 and r-1, true? Now, what implication does this have?
  9. Jul 23, 2011 #8
    If the first of the r numbers is n, and n[itex]\equiv[/itex]m(mod(x)) where 0[itex]\leq[/itex]x[itex]\leq[/itex]r, then n+(x-m) is a multiple of x. Because x-m[itex]\leq[/itex]r at least one of the r numbers will be a multiple of x. r! is the product of all such x.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook