DISPROVED
This has been solved in the negative.
Let $n_1<n_2<\cdots $ be an infinite sequence of integers with associated $a_k\pmod{n_k}$, such that for some $\epsilon>0$ we have $n_k>(1+\epsilon)k\log k$ for all $k$. Then\[\#\{ m<n_k : m\not\equiv a_i\pmod{n_i} \textrm{ for }1\leq i\leq k\}\neq o(k).\]
Erdős and Graham
[ErGr80] suggest this 'may have to await improvements in current sieve methods' (of which there have been several since 1980).
Note that since the $k$th prime is $\sim k\log k$ the lower bound $n_k>(1+\epsilon)k\log k$ is best possible here.
Cambie has observed that this question has a trivial negative answer, since taking $n_k=2^k$ and $a_k=2^{k-1}+1$ for $k\geq 1$ implies the only $m$ not in any congruence class is $1$, so the count is actually $1$!
For further discussion on counterexamples, and what a non-trivial variant of this problem might be, see the comments.
View the LaTeX source
This page was last edited 18 November 2025.
Additional thanks to: Stijn Cambie
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #280, https://www.erdosproblems.com/280, accessed 2026-02-13
