# Covering systems with odd moduli

A covering system is a finite list of congruences that together contain every integer, such as $0 \bmod 2$, $0 \bmod 3$, $1 \bmod 4$, $5 \bmod 6$ and $7 \bmod 12$. Erdős and Selfridge asked whether this can be done with distinct moduli that are all odd. One explicit example would settle the question, and much is known about how such an example would have to look.

## Problem

A **distinct covering system** is a finite collection of congruence classes $a_1 \bmod m_1,\dots,a_k \bmod m_k$ with distinct moduli $1<m_1<\dots<m_k$ such that every integer lies in at least one of the classes.

Is there a distinct covering system in which every modulus $m_i$ is odd?

Since the classes repeat with period $L=\operatorname{lcm}(m_1,\dots,m_k)$, a proposed system is checked by testing the residues $0,1,\dots,L-1$.

## Background

The study of covering systems with distinct moduli was begun by Erdős around 1950, and this question is due to him and Selfridge (it is sometimes also attributed jointly with Schinzel). The two disagreed about the answer. According to Filaseta, Ford and Konyagin (2000), Erdős, convinced that an odd covering exists, offered \$25 for a proof that none exists, while Selfridge offered \$300 for the first explicit example and later raised his award to \$2000; no award was promised for a non-constructive existence proof. Selfridge showed that an odd covering would exist if there were a covering system in which no modulus divides another, but that route closed when such systems were shown not to exist.

## What is known

- Every distinct covering system has a modulus divisible by 2 or 3 (Hough and Nielsen, 2019). Balister, Bollobás, Morris, Sahasrabudhe and Tiba gave a simpler proof in 2022 and showed that the least common multiple of the moduli of an odd covering, if one exists, must be divisible by 9 or 15.
- There is no odd covering system whose moduli are also square-free (Balister, Bollobás, Morris, Sahasrabudhe and Tiba, 2021).
- A related question of Erdős, whether the smallest modulus of a distinct covering system can be arbitrarily large, was answered negatively by Hough (2015); the smallest modulus is now known to be at most $616000$ (Balister, Bollobás, Morris, Sahasrabudhe and Tiba, 2022).
- **Small cases.** The least common multiple of the moduli of an odd covering must be odd and abundant, so at least $945$; a Lean proof checked end to end by the proof kernel shows it must exceed $10000$ (Mian and Siddique, 2026, preprint).
- **Claims.** Several claimed proofs that no odd covering exists were posted on the problem's forum in 2026. Each rested on unproved axioms, one of which was shown to be false, and none is accepted. Unrefereed preprints posted there in September 2026 claim that the least common multiple of an odd covering has at least nine distinct prime factors and that some modulus has at least four.

## What would count as progress

- An explicit odd distinct covering system: a list of pairs $(a_i,m_i)$ whose covering property a program can confirm by running through one period.
- A proof that no odd distinct covering exists, for example by extending the square-free argument to general odd moduli.
- New necessary conditions on the moduli of an odd covering (for example on the prime factors of their least common multiple), with complete proofs.
- A formal proof against the Lean statement in [formal-conjectures](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/7.lean).

## References

1. R. D. Hough and P. P. Nielsen, Covering systems with restricted divisibility, *Duke Math. J.* 168 (2019), 3261–3295. [doi:10.1215/00127094-2019-0058](https://doi.org/10.1215/00127094-2019-0058)
2. P. Balister, B. Bollobás, R. Morris, J. Sahasrabudhe and M. Tiba, The Erdős–Selfridge problem with square-free moduli, *Algebra Number Theory* 15 (2021), 609–626. [doi:10.2140/ant.2021.15.609](https://doi.org/10.2140/ant.2021.15.609)
3. P. Balister, B. Bollobás, R. Morris, J. Sahasrabudhe and M. Tiba, On the Erdős covering problem: the density of the uncovered set, *Invent. Math.* 228 (2022), 377–414. [doi:10.1007/s00222-021-01087-5](https://doi.org/10.1007/s00222-021-01087-5)
4. M. Filaseta, K. Ford and S. Konyagin, On an irreducibility theorem of A. Schinzel associated with coverings of the integers, *Illinois J. Math.* 44 (2000), 633–643. [doi:10.1215/ijm/1256060421](https://doi.org/10.1215/ijm/1256060421)
5. I. Mian and S. Siddique, Kernel-checked exclusions for the Erdős–Selfridge odd covering problem: any odd covering of $\mathbb{Z}$ has lcm exceeding 10000 (2026). [arXiv:2607.25628](https://arxiv.org/abs/2607.25628)

## Source

Imported from [Erdős Problems 7](https://www.erdosproblems.com/7), curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.