# To prove there exist two relatively prime numbers in a finite set

Prove that in any set of $n+1$ positive numbers not exceeding $2n$ there must be two that are relatively prime.

-
This is an old problem. Without giving too much away, have you thought about how you could definitely tell that two numbers are coprime? And maybe the bounds you are given may suggest using the pigeonhole principle? I think this is one you should work at before asking it. – Mark Bennet Jul 2 '11 at 20:34

In some circles at least this is as famous as the question of what is the sum of the first $n$ positive integers. It is often called the Posa Problem, because it was the problem that Erdos asked of the (then) 12 year-old Lajos Posa upon first meeting him. According to Erdos, Posa solved it in about $30$ seconds, all the while eating a bowl of soup. An account of this story is here; there must be a more primary source somewhere.

P.S.: I have some colleagues who work in the branch of mathematics -- additive combinatorics -- for which this result is basically page 1. When I by chance mentioned this problem to one of them, she replied, "Yes, and there is also one integer which divides another." Try that one too!

-

Two numbers must be consecutive.

I read this years ago in a book about Erdos. Here's the page.

-
Your answer appeared as I was finishing mine up. Indeed, I have read the book you cite (as well as another, similar Erdos biography that came out around the same time). It's interesting to note that the story as it is told in Schechter's book is isomorphic but not identical to the story as it is told in the link in my answer. – Pete L. Clark Jul 2 '11 at 22:55

Throw out the 1, since if it is on your list, then $gcd(a,1)=1$, and you are done. If not, you will necessarily have to choose two numbers in the list that are one unit appart, by the pigeonhole principle. Now show that if you have two consecutive numbers a,a+1, with a>1, your numbers must be relatively prime. (Hint: your linear combination is all-ready for you.)

{2k-1,2k}

EDIT: It also follows that the sequence contains a pair $(a,b)$ such that $a|b$; we choose the terms to try to avoid a pair (a,b), by choosing $\{ n,n+2,n+4,...,2n-2\}$ as WOLG the even terms (i.e., we assume n is even), and $\{n+1,n+3,...,2n-1\}$ as the odd terms , so that the smallest multiple (i.e., by 2) of any of the chosen elements is strictly-larger than $2n$ (this shows that n+1 is the best-possible bound). But this only uses up n of the terms in the sequence. So we must choose some term 'b' strictly smaller than $n= \frac {2n}{2}$. But , since $b<n$, there must be a multiple 'c' of b in the set $\{n,n+1,....,2n-1\}$. Then b|c.

Trying to make the argument more precise: basically, given 2n, we argue that if n-k is the largest number in the collection $\{a_1,..,a_n\}$ of n+1 elements out of $\{1,2.,...,2n\}$, then we must remove some elements to avoid having a pair $(b,c)$ with $b|c$, but the crux is that we must remove "too many" elements to avoid having a pair $(b,c)$, after which we cannot have a total of $n-1$ elements in our sequence. Say, e.g., that $n-1$ is the smallest element of our set $\{a_1,..,a_{n+1}\}$. Then we have $(2n-(n-1)+1)=n+2$ numbers between $n-1$ and $2n$ to select our sequence of n+1 elements from. But if we select the number b=$n-1$ for our set, we cannot select its multiple c=$2(n-1)$. So we must throw out $2(n-1)$, and we are left with $n+1$. Then we must keep $n=(n-1)+1$ together with $\{n,n+1,...,2(n-1)-1,2(n-1)+1,2n\}$ , to have a total of $n+1$ terms in our sequence. But that means that $n$ and $2n$ will both be in the sequence, and $n|2n$. The argument generalized for $n-k$ being the largest element chosen in $\{a_1,..,a_n\}$

-
Yeah, it becomes pretty easy if excluding 1. – Robert Jul 2 '11 at 21:05

This follows from the pigeonhole principle. Consider the set of first $2n$ numbers. You can create $n$ subsets of co-primes as $\{2k-1,2k\}$ for $1\leq k \leq n$. It is easy to see that these will be coprime (their difference is 1, so their GCD is 1). Now you have $n$ pairs of coprimes, and amongst any $n+1$ numbers in this range, atleast two will be a coprime pair.

Note: I have followed the definition to allow $(1,2)$ to be a coprime pair.

-

The simplest prof I have ever found The Story of Louis Pósa (Thanks Pete L. Clark) which is: "I you have n+1 positive integer number less or equal than 2n, there must be two of them are consecutive, which means they are relative prime."

By the way, the reason of "there must be two of them are consecutive" is because of the Pigeonhole Principle

-