---

Claim. M. Szegedy, The solution of Graham's greatest common divisor problem, Combinatorica 6 (1986), no. 1, 67--71. The paper proves Graham's conjecture, the statement of Problem 402, for every sufficiently large set: there is an effectively computable $n_0$ such that for $n\ge n_0$ and any $n$ distinct positive integers $a_1,\ldots,a_n$,

$$\max_{i,j}\frac{a_i}{\gcd(a_i,a_j)}\ge n,$$

and equality holds only when the set is $\{k,2k,\ldots,nk\}$ or $\{k/1,k/2,\ldots,k/n\}$ for some $k$, the two extremal types of the conjecture. The statement is taken from the paper's abstract, which says the equality case is settled in these two cases, and from the transcription in the formal-conjectures statement file for the problem, which quotes the theorem from the paper with its two clauses. Since $a/\gcd(a,b)\ge|A|$ is the problem's inequality $\gcd(a,b)\le a/|A|$, this is the problem's claim for every finite set of at least $n_0$ elements. Balasubramanian and Soundararajan describe the method on p. 1 of their 1996 paper: Szegedy exhibits many $\alpha$ with $r_p(\alpha)\ge2$, where $r_p(\alpha)=\#\{d:\alpha d,(p-\alpha)d\in A\}$ for a prime $p$ near $2N$, and needs a short-interval prime estimate of the shape $\pi(x+x^{9/14})-\pi(x)\gg x^{9/14}/\log x$; by the nature of that tool the threshold is of the order $e^{10^6}$. The same introduction counts Szegedy's and Zaharescu's results as the conjecture "in its weaker form", while the abstract and the statement file give Szegedy's theorem with the equality case; the page records both readings. Zaharescu's independent proof is on its own page, and the full resolution on the page of Balasubramanian and Soundararajan.

Covers. The problem's inequality for every finite set $A$ with $|A|\ge N_0$, for some absolute $N_0$. Not covered: the sets of fewer than $N_0$ elements, where $N_0$ is of the order $e^{10^6}$.

Depends on. No page of this wiki.

Acceptance. Refereed: Combinatorica is a refereed journal, and the paper appeared in its volume 6 (1986). The site's commentary credits Szegedy and Zaharescu with the large-set case, including the equality case, while its PROVED label settles the problem through Balasubramanian and Soundararajan, so no reviewed evidence is listed here. The journal record dates the issue to March 1986, so the page is dated to its first day.