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: Proof about relatively prime integers.

  1. Apr 20, 2014 #1
    1. The problem statement, all variables and given/known data
    Prove that if you have n+1 integers less than or equal to 2n then at least 2 are relatively prime.
    3. The attempt at a solution
    the book say integers but im pretty sure this will only work in the natural numbers.
    there are n even numbers between 0 and 2n okay and none of those are relatively prime but when we pick another number it will be odd and next to and even number. We know that consecutive integers are relatively prime because if they shared common factors it should divide their difference but the difference is (n+1)-n=1. so 1 is their only common factor. and picking n even integers is the most you pick that share common factors because multiples of 2 occur more frequently than any other multiple of a prime, because 2 is the smallest prime.
    Im just wondering how would i connect this to Ramsey theory.
  2. jcsd
  3. Apr 20, 2014 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You could shorten the proof a bit, just saying "there must be two that are consecutive". If you wanted to spell out the proof of that you could do it using the pigeon hole principle, which is at the root of Ramsey theory.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted