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
    2016 Award

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

Similar Discussions: Show N has Prime Numbers
  1. Prime Number (Replies: 15)

  2. Prime numbers (Replies: 12)

  3. Prime numbers (Replies: 8)