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!

Homework Help: Common Divisor Question

  1. Aug 26, 2009 #1
    1. The problem statement, all variables and given/known data

    We select n + 1 different integers from the set {1,2,...,2n}. Prove that there will always be two among the selected integers whose largest common divisor is 1.

    2. Relevant equations

    None

    3. The attempt at a solution

    I was thinking that this problem has something to do with the pigeonhole principle, however I'm pretty stuck here and don't even know where to get started...
     
  2. jcsd
  3. Aug 26, 2009 #2
    You're correct that it uses the pigeonhole principle.

    What are the possible gcd's for an arbitrary pair of integers from the set {1,2,...,2n}?
     
  4. Aug 26, 2009 #3
    Figured it out... Thanks for the help...

    Essentially, gcd(k, k+1) is a good candidate! =)
     
  5. Aug 28, 2009 #4
    Exactly!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook




Loading...