# Showing that a greatest common divisor must be 1 or 2 using pigeonhole principle

I need to prove that for any $$S \subset \{1,2,...,2018\}$$ with $$|S|=673$$, it follows that $$\exists\,a,b \in S$$ such that $$gcd(a,b)<3$$.

I can see the obvious application of pigeonhole principle here, since $$673 \times 3=2019$$ and just from the wording of the problem, but unfortunately it's late and I'm having trouble constructing the proof. Any tips?

• Hint: $\gcd(n,n+1)=1$ and $\gcd(n,n+2) \in \{1,2\}$ for all $n$. Nov 16, 2018 at 11:42
• This turned out to be more helpful, thanks! There are only 672 elements whose difference is greater than or equal to three in the set, which means that by the pigeonhole principle, in any set of cardinality 673 there must be two elements with a difference less than or equal to two. Apply your fact and the problem is solved. Dec 8, 2018 at 3:05

Any choice of $$k+1$$ elements from $$kd$$ consecutive positive integers where $$d\ge2$$ contains, by the pigeonhole principle, a pair of elements $$b where $$a-b\le d-1$$. This pair will have $$\gcd(a,b)=\gcd(a-b,b)\le d-1$$.
The OP's question is essentially the case when $$d=3$$ and $$k=672$$; $$1$$ and $$2$$ cannot be chosen since $$\gcd(1,n)$$ and $$\gcd(2,n)$$ are less than $$3$$, but then $$673$$ elements cannot be chosen from $$3,\dots,2018$$ that are all at least $$3$$ apart.