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

Homework Help: Counting and Pigeonhole, Incl- Excl

  1. Mar 22, 2010 #1
    1. The problem statement, all variables and given/known data
    Prove that, in any set of n + 1 positive integers (n ≥ 1) chosen from the set {1, 2, . . . 2n}, it must be that two of them are relatively prime (i.e. have no common divisor except 1). ( Hint: two consecutive integers are relatively prime. Make boxes labelled by pairs of consecutive integers. ).

    2. Relevant equations

    3. The attempt at a solution
    In boxes does it mean to write:


    and i dont understand how two consecutive integers are relatively prime.
  2. jcsd
  3. Mar 22, 2010 #2


    Staff: Mentor

    When you post a question and no one responds, you can "bump" the post and provide additional information, but don't start another thread about the same problem.

    I believe the hint means to label the boxes so they are distinct, like so...

    For any two consecutive integers, one must be even and the other odd, so they can't be divisible by 2. If one is divisible by 3, the other one can't be, because they're only 1 apart. Similarly, both can't be divisible by 5, 7, 11, 13, and so on. We don't need to check 4, 6, 8, and so on, or any other multiple of 2, since one of the numbers isn't even. We also don't need to check multiples of 3, or 4, or 5, or ...
  4. Mar 28, 2010 #3
    Suppose d divides n and n+1.
    Then d must divide (n+1) - n = 1.
    So d must be plus or minus 1.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook