Show N has Prime Numbers

  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. Hint: If m is a positive integer, then m and m+1 are relatively prime.
     
  4. 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
    Set=0,2,6,8

    then you would do the n+1 one on that set?
    Or something to that extent?
     
  5. haruspex

    haruspex 13,597
    Science Advisor
    Homework Helper
    Gold Member
    2014 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. pwsnafu

    pwsnafu 913
    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 a link to this question via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Show N has Prime Numbers
Loading...