1. Not finding help here? Sign up for a free 30min 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!

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




Similar Discussions: Common Divisor Question
  1. Greatest common divisor (Replies: 24)

Loading...