# Homework Help: Proof about relatively prime integers.

1. Apr 20, 2014

### cragar

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. Apr 20, 2014

### haruspex

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.