Problem

Source: China TSTST 3 Day 2 Problem 2

Tags: greatest common divisor, number theory



Show that there exists a positive real $C$ such that for any naturals $H,N$ satisfying $H \geq 3, N \geq e^{CH}$, for any subset of $\{1,2,\ldots,N\}$ with size $\lceil \frac{CHN}{\ln N} \rceil$, one can find $H$ naturals in it such that the greatest common divisor of any two elements is the greatest common divisor of all $H$ elements.