1

Take $n + 1$ numbers out of $1, 2, ..., 2n$. Show that there will be two numbers $x, y$ so that $gcd(x, y) = 1$.

What I've got is:

Let $d=gcd(a,b)$; by definition there are integers $a′$ and $b′$ such that $a=a′d$ and $b=b′d$, so $a′dx+b′dy=d$. Dividing through by $d$, then a$′x+b′y=1$.

Let $e=gcd(x,y)$. As before, there are integers $x′$ and $y′$ such that $x=ex′$ and $y=ey′$. Substituting these into the previous equation, we get $a′ex′+′ey′=1$, or $e(a′x′+b′y′)=1$. Since $a′x′+b′y′$ is an integer, this implies that $e=1$ or $e=−1$: these are the only divisors of $1$. But $e$ is a greatest common divisor and hence by definition positive, so $e=1$.

Would this proof be correct?

user3434743
  • 393

2 Answers2

1

The OP proof does not use $n+1$ or $2n$, and therefore cannot be correct. Note that the statement is false if you replace $n+1$ by $n$; take $\{2,4,6,\ldots, 2n\}$.

The standard proof of this result uses the pigeonhole principle. Choose $n$ pigeonholes carefully, so that two numbers from the same set will have gcd=1.

vadim123
  • 82,796
1

Divide the numbers into subsets $\{1, 2\}, \{3, 4\}, \ldots, \{2n-1, 2n\}$. If you select $n+1$ numbers out of the integers from $1$ to $2n$, then by the pigeonhole principle, then amongst them there must be two from the same subset. Since those two integers are consecutive, they must have GCD equal to $1$, and are therefore the numbers desired.

Brian Tung
  • 34,160