OP-00942 Open

Covering every integer up to N ten times by one residue class per prime

Erdős remarked that he did not know the answer to the question below even with $10$ replaced by $2$.

Problem. Can one assign to each prime $p \le N$ a residue class $a_p \bmod p$ so that each integer $n \le N$ belongs to at least $10$ of these classes?

Source: P. Erdős, A survey of problems in combinatorial number theory, Ann. Discrete Math. 6 (1980), Section 6, Problem 6. Listed as Problem 45 in B. Green, 100 open problems (version of January 2026).

Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.

Classification

Primary: NT — Number Theory
Secondary: CO
Keywords: covering systems, Erdős problems, residue classes, sieve theory
Literature checked: Oct. 26, 2026 by clemens-admin

References

@article{erdos1979unconventional,
  author = {Erd{\H o}s, P.},
  title = {Some unconventional problems in number theory},
  journal = {Acta Mathematica Academiae Scientiarum Hungaricae},
  volume = {33},
  number = {1-2},
  pages = {71--80},
  year = {1979},
  doi = {10.1007/BF01903382}
}

@incollection{erdos1980survey,
  author = {Erd{\H o}s, Paul},
  title = {A survey of problems in combinatorial number theory},
  booktitle = {Combinatorial Mathematics, Optimal Designs and Their Applications},
  series = {Annals of Discrete Mathematics},
  volume = {6},
  pages = {89--115},
  publisher = {North-Holland},
  year = {1980},
  doi = {10.1016/S0167-5060(08)70697-6}
}

@misc{erdosproblems689,
  author = {Bloom, Thomas F.},
  title = {Erd{\H o}s Problem \#689},
  howpublished = {\url{https://www.erdosproblems.com/689}},
  note = {Accessed 2026-10-26; the case of two classes, with unrefereed proof claims}
}

@misc{green100open,
  author = {Green, Ben},
  title = {100 open problems},
  howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
  note = {Problem 45; version of January 2026, most recent update December 2025},
  year = {2026}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00942, "Covering every integer up to N ten times by one residue class per prime", clopen.solutions.