Prove that, for any finite set $A\subset\mathbb{N}$, there exist $a, b\in A$ such that $$\gcd(a, b)\leq a/|A|.$$

Proved for all sufficiently large sets (including the sharper version which characterises the case of equality) independently by Szegedy [Sz86] and Zaharescu [Za87]. The following is taken from [Sz86].

There exists an effectively computable $n_0$ with the following properties: (i) if $n \ge n_0$ and $a_1, a_2, \dots, a_n$ are distinct natural numbers then $\max_{i, j} \frac{a_i}{(a_i, a_j)} \ge n$. (ii) If equality holds then the system $\{a_1, a_2, \dots, a_n\}$ is either of the type $\{k, 2k, \dots, nk\}$ or of the type $\left\{\frac{k}{1}, \frac{k}{2}, \dots, \frac{k}{n}\right\}$.