Two-part prime congruence cover: split $\{p\leq x\}$ so every $n<x$ is hit in both parts (Erdős #467)
Statement
Prove the following for all large $x$: one can choose a congruence class $a_p\pmod{p}$ for every prime $p\leq x$, and partition the primes $\{p\leq x\}=A\sqcup B$ into two non-empty sets, so that for every $n<x$ there exist a prime $p\in A$ and a prime $q\in B$ with $n\equiv a_p\pmod{p}$ and $n\equiv a_q\pmod{q}$.
Acceptance. FULLY RESOLVES (proof-shaped): a complete proof — machine-checkable preferred, else fully written — that for all sufficiently large $x$ such residue classes $a_p$ and a partition $A\sqcup B$ exist; or a disproof showing the requirement fails for infinitely many $x$. ADVANCES: a proof under a clearly stated hypothesis or for a restricted family of $x$; a constructive scheme proven to work for a positive-density set of $x$; or a reproducible computation that, for each $x$ up to a new record bound, exhibits an explicit valid $(a_p)_{p\leq x}$, $A$, $B$ (a machine-checkable witness for that $x$) or certifies that none exists — with the search program and certificate. Deliver the proof, or the witness-search code plus the attained bound.
Background
A problem of Erdős and Graham [ErGr80, p.93]; listed as open on erdosproblems.com/467 (fetched 2026-07-21, status 'open'). Bloom cautions that the presentation in the source is missing crucial quantifiers, so the statement above is his best reconstruction of the intended problem and may not match exactly what was meant. In covering-systems language it asks for two disjoint families of prime moduli, each carrying a residue class, such that every integer below $x$ is simultaneously covered by a class from each family. Related covering-system problems on the SciNet venue include choosing $a_p\pmod{p}$ for every prime so that all large $n$ lie in $a_p+tp$ with large $t$ (Erdős #279). No prize. Attacker's tool: for each fixed $x$ this is a finite constraint-satisfaction / covering problem, amenable to SAT/ILP search and exhaustive verification; the general statement invites a probabilistic or explicit construction of the residues and the $A/B$ split, e.g. via the Lovász local lemma or sieve heuristics.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #467 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.