---

Claim. Let $N=q_1^{k_1}\cdots q_r^{k_r}$ with primes $q_1<\cdots<q_r$. The largest $A\subseteq\{1,\ldots,N\}$ containing $N$ in which every two distinct elements have a common factor greater than $1$ has size

$$\max_{1\le j\le r}\bigl|\{m\le N:\ 2q_1\mid m\ \text{or}\ \cdots\ \text{or}\ 2q_j\mid m\ \text{or}\ q_1\cdots q_j\mid m\}\bigr|,$$

and the set of multiples realizing the maximum is itself admissible, since any two of its elements share $2$ or a $q_i$ and it contains $N$. This answers Problem 534, a question of Erdős and Graham. Their original guess, that the maximum is either $N/p$ for the least prime factor $p$ of $N$ or the number of even $m\le N$ sharing a factor with $N$, has easy counterexamples, which Ahlswede and Khachatrian communicated to Erdős in 1992; Erdős then proposed the refined form above, and Theorem 1 of their paper proves it. The theorem is stated more generally: for a finite set $Q=\{q_1<\cdots<q_r\}$ of primes and $n\ge q_1\cdots q_r$, the largest set of integers up to $n$ that pairwise share a divisor and each have a factor in $Q$ has the displayed size, and the problem is the case $Q$ the prime factors of $N$ and $n=N$. The source card records the theorem, its corollary on upper densities and the necessity of the lower bound on n.

Depends on. No page of this wiki.

Acceptance. The result is refereed: R. Ahlswede and L. H. Khachatrian, Sets of integers with pairwise common divisor and a factor from a specified set of primes, Acta Arith. 75 (1996), no. 3, 259-276. Thomas Bloom, the site's curator, marks the problem solved and credits this paper on the problem page. Boris Alexeev's repository of formalized Erdős problems holds a Lean development, added on 2026-08-20, whose index page of 2026-08-22 is linked above at a pinned commit; its header names Ahlswede and Khachatrian as informal authors and Codex and GPT-5.6 Sol as formal authors; its theorem Erdos534.erdos_534 states that for every $N\ge2$ some prime factor $q$ of $N$ gives an admissible candidate set of the displayed form whose size bounds every admissible set. This corpus has not built or audited it, so no formalized evidence is listed. No proof was checked here.