1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Show N has Prime Numbers

  1. Jan 8, 2013 #1
    (For the following problem I don't just want a flat out answer, but steps and Ideas on how to solve it. The problem was given by my Universities newspaper and for solving it you get free Loot and stuff) ​

    The Problem:
    Show that every set of n+1 positive integers, chosen from a set of 2n consecutive integers, contains at least one pair of relatively prime numbers.

    relatively prime means: "Two integers are relatively prime if they share no common positive factors (divisors) except 1"

    Example: 8 and 15 are relatively prime.

    8 = 2 * 2 * 2 15 = 3 * 5

    Example: 9 and 12 are NOT relatively prime

    9 = 3 * 3 12 = 2 * 2 * 3
    My thinking thus far:
    None really I've just started
    Last edited by a moderator: Jan 8, 2013
  2. jcsd
  3. Jan 8, 2013 #2
    Hint: If m is a positive integer, then m and m+1 are relatively prime.
  4. Jan 8, 2013 #3
    very true, but I think the problem is more difficult than this.

    "Show that every set of n+1 positive integers, chosen from a set of 2n consecutive integers"

    wouldn't this mean the set would be...
    n= 0 1 2 3 4

    then you would do the n+1 one on that set?
    Or something to that extent?
  5. Jan 8, 2013 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Petek's hint is right. If you wanted to choose a subset without picking any pair that's relatively prime, what does that tell you about the option of picking consecutive numbers from the set?
  6. Jan 8, 2013 #5


    User Avatar
    Science Advisor

    The statement means: I give you a set S = {a, a+1, a+2, ..., a+2n-1} and you pick a subset with n+1 elements.

    The point of the problem is that no matter what you do, your subset always contains a pair which are relatively prime.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook