VOOZH about

URL: https://www.erdosproblems.com/tags/covering systems

⇱ Erdős Problems


👁 Logo
Forum Inbox Favourites Tags
More
Forum
Dual View Random Solved Random Open
10 solved out of 22 shown (show only or or or )
DISPROVED This has been solved in the negative. - $1000
Can the smallest modulus of a covering system be arbitrarily large?
#2: [Er55c][Er57][Er61][Er65][Er65b][Er73][Er77c][Er80,p.95][ErGr80,p.24][Er82e][Er85c][Er90][Er95,p.166][Er96b][Er97][Er97c][Er97e][Va99,1.31]
number theory | covering systems
Described by Erdős as 'perhaps my favourite problem'. Hough [Ho15], building on work of Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], has shown (contrary to Erdős' expectations) that the answer is no: the smallest modulus must be at most $10^{16}$.

An alternative, simpler, proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who improved the upper bound on the smallest modulus to $616000$.

The best known lower bound is a covering system whose minimum modulus is $42$, due to Owens [Ow14].

View the LaTeX source

This page was last edited 05 April 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
Related OEIS sequences: A160559
3 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Alfaiz and Desmond Weisenberg

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 #2, https://www.erdosproblems.com/2, accessed 2026-04-10
VERIFIABLE Open, but could be proved with a finite example. - $25
Is there a distinct covering system all of whose moduli are odd?
#7: [Er57][Er61][Er65][Er65b][Er73][ErGr80][Er82e][Er90][Er95,p.166][Er96b][Er97][Er97c][Er97e]
number theory | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Asked by Erdős and Selfridge (sometimes also with Schinzel). They also asked whether there can be a covering system such that all the moduli are odd and squarefree. The answer to this stronger question is no, proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

Hough and Nielsen [HoNi19] proved that at least one modulus must be divisible by either $2$ or $3$. A simpler proof of this fact was provided by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22], who also prove that if an odd covering system exists then the least common multiple of its moduli must be divisible by $9$ or $15$.

Selfridge has shown (as reported in [Sc67]) that such a covering system exists if a covering system exists with moduli $n_1,\ldots,n_k$ such that no $n_i$ divides any other $n_j$ (but the latter has been shown not to exist, see [586]).

Filaseta, Ford, and Konyagin [FFK00] report that Erdős, 'convinced that an odd covering does exist, offered \$25 for a proof that no odd covering exists; Selfridge, convinced (at that point) that no odd covering exists, offered \$300 for the first explicit example...no award was promised to someone who gave a non-constructive proof that an odd covering of the integers exists...Selfridge (private communication) has informed us that he is now increasing his award to \$2000.'

View the LaTeX source

This page was last edited 22 January 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
12 comments on this problem
Likes this problem MvanOorschot
Interested in collaborating None
Currently working on this problem None
This problem looks difficult Dogmachine
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Sarosh Adenwalla, Alfaiz, and Antonio Girao

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 #7, https://www.erdosproblems.com/7, accessed 2026-04-10
DISPROVED This has been solved in the negative.
For any finite colouring of the integers is there a covering system all of whose moduli are monochromatic?
#8: [Er80,p.95][ErGr80,p.25][Er96b][Er97][Er97e]
number theory | covering systems
Conjectured by Erdős and Graham, who also ask about a density-type version: for example, is\[\sum_{\substack{a\in A\\ a>N}}\frac{1}{a}\gg \log N\]a sufficient condition for $A$ to contain the moduli of a covering system?

The answer (to both colouring and density versions) is no, due to the result of Hough [Ho15] on the minimum size of a modulus in a covering system - in particular one could colour all integers $<10^{18}$ different colours and all other integers a new colour.

View the LaTeX source

This page was last edited 05 April 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
2 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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 #8, https://www.erdosproblems.com/8, accessed 2026-04-10
DISPROVED This has been solved in the negative. - $100
An $\epsilon$-almost covering system is a set of congruences $a_i\pmod{n_i}$ for distinct moduli $n_1<\ldots<n_k$ such that the density of those integers which satisfy none of them is $\leq \epsilon$.

Is there a constant $C>1$ such that for every $\epsilon>0$ and $N\geq 1$ there is an $\epsilon$-almost covering system with $N\leq n_1<\cdots <n_k\leq CN$?
#27: [Er95,p.4]
number theory | covering systems
By a simple averaging argument the set of moduli $[m_1,m_2]\cap \mathbb{N}$ has a choice of residue classes which form an $\epsilon(m_1,m_2)$-almost covering system with\[\epsilon(m_1,m_2)=\prod_{m_1\leq m\leq m_2}(1-1/m).\]A $0$-covering system is just a covering system, and so by Hough [Ho15] these only exist for $n_1<10^{18}$ (now $<616000$ thanks to [BBMST22]).

The answer is no, as proved by Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07], who (among other results) prove that if\[1< C \leq N^{\frac{\log\log\log N}{4\log\log N}}\]then, for any $N\leq n_1<\cdots< n_k\leq CN$, the density of integers not covered for any fixed choice of residue classes is at least\[(1-o(1))\prod_{i}(1-1/n_i)\](and this density is achieved for some choice of residue classes as above).

View the LaTeX source

This page was last edited 06 December 2025. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
0 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Mehtaab Sawhney and Wouter van Doorn

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 #27, https://www.erdosproblems.com/27, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
Let $n_1<\cdots < n_r\leq N$ with associated $a_i\pmod{n_i}$ such that the congruence classes are disjoint (that is, every integer is $\equiv a_i\pmod{n_i}$ for at most one $1\leq i\leq r$). How large can $r$ be in terms of $N$?
#202: [Er61][Er65][Er65b][Er73][Er77c][Er80,p.96][ErGr80][Va99,1.29]
covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Let $f(N)$ be the maximum possible $r$. Erdős and Stein conjectured that $f(N)=o(N)$, which was proved by Erdős and Szemerédi [ErSz68], who showed that, for every $\epsilon>0$,\[\frac{N}{\exp((\log N)^{1/2+\epsilon})} \ll_\epsilon f(N) < \frac{N}{(\log N)^c}\]for some $c>0$. Erdős believed the lower bound is closer to the truth.

These bounds were improved by Croot [Cr03b] who proved\[\frac{N}{L(N)^{\sqrt{2}+o(1)}}< f(N)<\frac{N}{L(N)^{1/6-o(1)}},\]where $L(N)=\exp(\sqrt{\log N\log\log N})$. These bounds were further improved by Chen [Ch05] and then by de la Bretéche, Ford, and Vandehey [BFV13] to\[\frac{N}{L(N)^{1+o(1)}}<f(N) < \frac{N}{L(N)^{\sqrt{3}/2+o(1)}}.\]The latter authors conjecture that the lower bound here is the truth.

See also [1190].

View the LaTeX source

This page was last edited 06 April 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
Related OEIS sequences: A389975
0 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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 #202, https://www.erdosproblems.com/202, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
Is there an integer $m\geq 1$ with $(m,6)=1$ such that none of $2^k3^\ell m+1$ are prime, for any $k,\ell\geq 0$?
#203: [ErGr80,p.27]
primes | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Positive odd integers $m$ such that none of $2^km+1$ are prime are called Sierpinski numbers - see [1113] for more details.

Erdős and Graham also ask more generally about $p_1^{k_1}\cdots p_r^{k_r}m+1$ for distinct primes $p_i$, or $q_1\cdots q_rm+1$ where the $q_i$ are primes congruent to $1\pmod{4}$. (Dogmachine has noted in the comments this latter question has the trivial answer $m=1$ - perhaps some condition such as $m$ even is meant.)

View the LaTeX source

This page was last edited 20 January 2026. View history

External data from the database - you can help update this
Formalised statement? Yes
13 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem uona
This problem looks difficult Dogmachine
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Dogmachine and Wouter van Doorn

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 #203, https://www.erdosproblems.com/203, accessed 2026-04-10
DISPROVED (LEAN) This has been solved in the negative and the proof verified in Lean.
Are there $n$ such that there is a covering system with moduli the divisors of $n$ which is 'as disjoint as possible'?

That is, for all $d\mid n$ with $d>1$ there is an associated $a_d$ such that every integer is congruent to some $a_d\pmod{d}$, and if there is some integer $x$ with\[x\equiv a_d\pmod{d}\textrm{ and }x\equiv a_{d'}\pmod{d'}\]then $(d,d')=1$.
#204: [ErGr80,p.27]
covering systems | divisors
The density of such $n$ is zero. Erdős and Graham believed that no such $n$ exist.

Adenwalla [Ad25] has proved there are no such $n$.

In general, for any $n$ one can try to choose such $a_d$ to maximise the density of integers so covered, and ask what this density is. This was also investigated by Adenwalla [Ad25].

View the LaTeX source

This page was last edited 28 December 2025. View history

External data from the database - you can help update this
Formalised statement? Yes
1 comment on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Sarosh Adenwalla

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 #204, https://www.erdosproblems.com/204, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
Is there a covering system all of whose moduli are of the form $p-1$ for some primes $p\geq 5$?
#273: [ErGr80,p.24]
number theory | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Selfridge has found an example using divisors of $360$ if $p=3$ is allowed.

View the LaTeX source

This page was last edited 01 October 2025. View history

External data from the database - you can help update this
Formalised statement? Yes
0 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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 #273, https://www.erdosproblems.com/273, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
If $G$ is a group then can there exist an exact covering of $G$ by more than one cosets of different sizes? (i.e. each element is contained in exactly one of the cosets)
#274: [Er77c,p.49][ErGr80,p.26][Er97c,p.53]
group theory | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
A question of Herzog and Schönheim, who conjectured more generally that if $G$ is any (not necessarily finite) group and $a_1G_1,\ldots,a_kG_k$ are finitely many cosets of subgroups of $G$ with distinct indices $[G:G_i]$ then the $a_iG_i$ cannot form a partition of $G$.

This conjecture was proved in the case when all the $G_i$ are subnormal in $G$ by Sun [Su04]. In particular if $G$ is abelian (which was the special case asked about in [Er77c] and [ErGr80]) the answer to the original question is no.

Margolis and Schnabel [MaSc19] proved this conjecture for all groups $G$ of size $<1440$.

View the LaTeX source

This page was last edited 31 October 2025. View history

External data from the database - you can help update this
Formalised statement? Yes
3 comments on this problem
Likes this problem Fedir
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Boris Alexeev, Alfaiz, Sean Eberhard, and Dustin Mixon

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 #274, https://www.erdosproblems.com/274, accessed 2026-04-10
PROVED (LEAN) This has been solved in the affirmative and the proof verified in Lean.
If a finite system of $r$ congruences $\{ a_i\pmod{n_i} : 1\leq i\leq r\}$ (the $n_i$ are not necessarily distinct) covers $2^r$ consecutive integers then it covers all integers.
#275: [Er65][Er65b][ErGr80]
number theory | covering systems
This is best possible as the system $2^{i-1}\pmod{2^i}$ shows. This was proved indepedently by Selfridge and Crittenden and Vanden Eynden [CrVE70]. A simpler proof was given by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST20b].

View the LaTeX source

This page was last edited 23 January 2026. View history

External data from the database - you can help update this
Formalised statement? Yes
2 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Alfaiz

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 #275, https://www.erdosproblems.com/275, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
Is there an infinite Lucas sequence $a_0,a_1,\ldots$ where $a_{n+2}=a_{n+1}+a_n$ for $n\geq 0$ such that all $a_k$ are composite, and yet no integer has a common factor with every term of the sequence?
#276: [ErGr80,p.27]
number theory | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Whether such a composite Lucas sequence even exists was open for a while, but using covering systems Graham [Gr64] showed that\[a_0 = 1786772701928802632268715130455793\]and\[a_1 = 1059683225053915111058165141686995\]generate such a sequence. This problem asks whether one can have a composite Lucas sequence without 'an underlying system of covering congruences responsible'.

This problem has been 'conjecturally solved' by Ismailescu and Son [IsSo14], in that they provide an explicit infinite Lucas sequence in which all the terms are composite, and believe that no covering system is responsible for this. See the comment by van Doorn below for more details.

See also [1113] for another problem in which the question is whether covering systems are always responsible.

View the LaTeX source

This page was last edited 29 December 2025. View history

External data from the database - you can help update this
Formalised statement? Yes
3 comments on this problem
Likes this problem Woett
Interested in collaborating Woett
Currently working on this problem None
This problem looks difficult Dogmachine
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Dogmachine and Wouter van Doorn

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 #276, https://www.erdosproblems.com/276, accessed 2026-04-10
PROVED This has been solved in the affirmative.
Is it true that, for every $c$, there exists an $n$ such that $\sigma(n)>cn$ but there is no covering system whose moduli all distinct divisors of $n$ (which are $>1$)?
#277: [Er77c,p.47][Er80,p.95][ErGr80,p.27][Er82e,p.67]
number theory | covering systems
This was answered affirmatively by Haight [Ha79].

In [Er80] Erdős goes on to ask about\[f(x)=\max_{m<x} \frac{\sigma(m)}{m},\]where the maximum is taken over all $m$ for which the divisors of $m$ do not form a covering system, so that Haight proved $f(x)\to \infty$ as $x\to \infty$. Is it true that $f(x)=o(\log\log x)$?

Filaseta, Ford, Konyagin, Pomerance, and Yu [FFKPY07] have proved that\[f(x)\geq (1+o(1))\sqrt{\log\log x}.\]van Doorn notes in the comments that the result of Hough [Ho15] that the smallest modulus is bounded by an absolute constant $C>0$ (see [2]) implies that one can let $n$ be least common multiple of all integers $\leq x$ which have all prime divisors $>C$, which shows that\[f(x)= (1+o(1))\log\log x.\]

View the LaTeX source

This page was last edited 10 April 2026. View history

External data from the database - you can help update this
Formalised statement? Yes
1 comment on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Wouter van Doorn

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 #277, https://www.erdosproblems.com/277, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
Let $A=\{n_1<\cdots<n_r\}$ be a finite set of positive integers. What is the maximum density of integers covered by a suitable choice of congruences $a_i\pmod{n_i}$?

Is the minimum density achieved when all the $a_i$ are equal?
#278: [ErGr80,p.28]
number theory | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Simpson [Si86] has observed that the density of integers covered is at least\[\sum_i \frac{1}{n_i}-\sum_{i<j}\frac{1}{[n_i,n_j]}+\sum_{i<j<k}\frac{1}{[n_i,n_j,n_k]}-\cdot\](where $[\cdots]$ denotes the least common multiple) which is achieved when all $a_i$ are equal, settling the second question.

View the LaTeX source

This page was last edited 20 January 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
4 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Sarosh Adenwalla

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 #278, https://www.erdosproblems.com/278, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
Let $k\geq 3$. Is there a choice of congruence classes $a_p\pmod{p}$ for every prime $p$ such that all sufficiently large integers can be written as $a_p+tp$ for some prime $p$ and integer $t\geq k$?
#279: [ErGr80,p.29]
number theory | covering systems | primes
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Even the case $k=3$ seems difficult. This may be true with the primes replaced by any set $A\subseteq \mathbb{N}$ such that\[\lvert A\cap [1,N]\rvert \gg N/\log N\]and\[\sum_{\substack{n\in A\\ n\leq N}}\frac{1}{n} -\log\log N\to \infty\]as $N\to \infty$.

For $k=1$ or $k=2$ any set $A$ such that $\sum_{n\in A}\frac{1}{n}=\infty$ has this property.

View the LaTeX source

This page was last edited 20 January 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
0 comments on this problem
Likes this problem Dogmachine
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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 #279, https://www.erdosproblems.com/279, accessed 2026-04-10
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).\]
#280: [ErGr80,p.29]
number theory | covering systems
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. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
4 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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-04-10
PROVED (LEAN) This has been solved in the affirmative and the proof verified in Lean.
Let $n_1<n_2<\cdots$ be an infinite sequence such that, for any choice of congruence classes $a_i\pmod{n_i}$, the set of integers not satisfying any of the congruences $a_i\pmod{n_i}$ has density $0$.

Is it true that for every $\epsilon>0$ there exists some $k$ such that, for every choice of congruence classes $a_i$, the density of integers not satisfying any of the congruences $a_i\pmod{n_i}$ for $1\leq i\leq k$ is less than $\epsilon$?
#281: [ErGr80,p.29]
number theory | covering systems
The latter condition is clearly sufficient, the problem is if it's also necessary. The assumption implies $\sum \frac{1}{n_i}=\infty$. If the $n_i$ are pairwise relatively prime then it is sufficient that $\sum \frac{1}{n_i}=\infty$.

This is true - a proof is given in the comments by Somani (using ChatGPT).

An alternative elementary proof was noted by KoishiChan in the comments: let $\delta$ be the lower density of the set of integers divisible by some $n\in A$, and $\delta_k$ be the density of the set of integers divisible by at least one of $n_1,\ldots,n_k$. A theorem of Davenport and Erdős [DaEr36] states that\[\delta = \lim_{k\to \infty}\delta_k.\]In the present case $\delta=1$ and hence for every $\epsilon>0$ there exists $k$ such that $\delta_k>1-\epsilon$. In other words, the density of those integers not satisfying $a_i\equiv 0\pmod{n_i}$ for $1\leq i\leq k$ is $<\epsilon$. By a theorem of Rogers (which first appeared in print in Chapter V.3 of the book of Halberstam and Roth [HaRo66]) the density of those integers not satisfying any of the congruences $a_i\pmod{n_i}$ for $1\leq i\leq k$ is maximised when $a_i\equiv 0$, which concludes the proof.

Given that both Rogers' result and the Davenport-Erdős theorem mentioned above must have been very familiar to Erdős in 1980, it is strange that this natural argument was overlooked.

View the LaTeX source

This page was last edited 18 January 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
28 comments on this problem
Likes this problem Dogmachine
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Sarosh Adenwalla, KoishiChan, Neel Somani, and Terence Tao

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 #281, https://www.erdosproblems.com/281, accessed 2026-04-10
DISPROVED This has been solved in the negative.
Is there a covering system such that no two of the moduli divide each other?
#586: [ErGr80][Er96b][Er97][Er97c][Er97e]
number theory | covering systems
Asked by Schinzel, motivated by a question of Erdős and Selfridge (see [7]). The answer is no, as proved by Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST22].

View the LaTeX source

View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
0 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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 #586, https://www.erdosproblems.com/586, accessed 2026-04-10
PROVED (LEAN) This has been solved in the affirmative and the proof verified in Lean.
There is no exact covering system - that is, a finite collection of congruence classes $a_i\pmod{n_i}$ with distinct $n_i$ such that every integer satisfies exactly one of these congruence classes.
#947: [Er77c]
number theory | covering systems
This is true, and was proved independently by Mirsky and Newman and Davenport and Rado.

View the LaTeX source

View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
1 comment on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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 #947, https://www.erdosproblems.com/947, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
A positive odd integer $m$ such that none of $2^km+1$ are prime for $k\geq 0$ is called a Sierpinski number. We say that a set of primes $P$ is a covering set for $m$ if every $2^km+1$ is divisible by some $p\in P$.

Are there Sierpinski numbers with no finite covering set of primes?
#1113: [ErGr80,p.27]
number theory | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Sierpinski [Si60] proved that there are infinitely many Sierpinski numbers, using covering systems to construct suitable covering sets for any $m$ satisfying a certain congruence. This establishes that there is a positive density set of such $m$.

The smallest Sierpinski number is believed to be $78557$, which was found by Selfridge.

Erdős and Graham [ErGr80] asked whether there are Sierpinski numbers for which a covering system is not 'responsible', for which the best interpretation seems to be the above question. This is formulated precisely in problem F13 of Guy's collection [Gu04]. Erdős and Graham thought the answer is yes (in that there are such Sierpinski numbers), since otherwise this would imply there are infinitely many Fermat primes.

There is now further evidence with a concrete example: an argument of Izotov [Iz95], given in more detail by Filaseta, Finch, and Kozek [FFK08], suggests that $m=734110615000775^4$ is a Sierpinski number without a covering set. (Izotov proved that this $m$ is indeed a Sierpinski number.)

Filaseta, Finch, and Kozek [FFK08] give a revised conjecture, suggesting that every Sierpinski number is either a perfect power or else has a finite covering set of primes. They also prove that for every $l\geq 1$ there is an $m$ such that $2^km^i+1$ is composite for all $1\leq i\leq l$ and $k\geq 0$.

See also [203], and [276] for another problem in which the question is whether covering systems are always responsible.

View the LaTeX source

This page was last edited 29 December 2025. View history

External data from the database - you can help update this
Formalised statement? Yes
Related OEIS sequences: A076336
1 comment on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult Dogmachine
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

Additional thanks to: Dogmachine and Wouter van Doorn

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 #1113, https://www.erdosproblems.com/1113, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
Call a set of distinct integers $1<n_1<\cdots<n_k$ with associated congruence classes $a_i\pmod{n_i}$ a distinct covering system if every integer satisfies at least one of these congruences. A minimal distinct covering system is one such that no proper subset forms a covering system.

Let $F(x)$ count the number of minimal distinct covering systems with all moduli in $[1,x]$. Estimate $F(x)$.
#1188: [Er80,p.95]
number theory | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Erdős [Er80] asked this without the minimal assumption, but otherwise this is trivial (since e.g. any system containing some fixed covering system would work, resulting in $\gg 2^x$ many such systems). He expected $F(x)\to \infty$ as $x\to \infty$ 'very slowly'.

In [Er80] Erdős also asked to estimate the number of irreducible covering sets in $[1,x]$ (that is, those sets of moduli which contain no proper sets of moduli which form a covering system, perhaps with a different choice of congruence class). If this count is $G(x)$ then trivially $G(x)\leq F(x)$. See [1189] for more on irreducible covering sets.

It follows from the solution of Hough [Ho15] to [3] that $F(x)\to \infty$ as $x\to \infty$. The lower bound construction of Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST24] implies that there are at least $\exp(k^{3+o(1)})$ many minimal distinct covering systems, all of whose moduli are at most $\prod_{p<k}p=e^{(1+o(1))k}$, which implies\[F(x)\geq \exp((\log x)^{3-o(1)})\](in particular $F(x)$ grows faster than any polynomial, perhaps contradicting Erdős' guess that it should grow 'very slowly', although it is possible he was thinking of the number of different moduli possible). The trivial upper bound is\[F(x) \leq \exp(O(x\log x)).\]

View the LaTeX source

This page was last edited 08 April 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
Related OEIS sequences: Possible
0 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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 #1188, https://www.erdosproblems.com/1188, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
Call a set of distinct integers $1<n_1<\cdots<n_k$ a covering set if there is a choice of $a_i\pmod{n_i}$ for $1\leq i\leq k$ such that every integer satisfies at least one of these congruences. A set is an irreducible covering set if no proper subset is a covering set.

How many irreducible covering sets of size $k$ are there?

What is the minimum and maximum that $n_k$ can be?

Determine or estimate $\max \sum\frac{1}{n_i}$, where the maximum ranges over all irreducible covering sets of size $k$.

Are there infinitely many $n$ such that the divisors of $n$ (which are $>1$) form an irreducible covering set?
#1189: [Er80,p.95]
number theory | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
This is subtly different from the (more usually studied) notion of minimal covering system: an irreducible covering set corresponds to the set of moduli of a minimal covering system, but not necessarily vice versa.

The divisors of $12$ (which are $>1$) are an example of an irreducible covering set. Sun [Su07] proved more generally that, for any odd prime $p$, the divisors (which are $>1$) of $2^{p-1}p$ form an irreducible covering set, settling the final question.

Simpson [Si85] proved $n_k\leq 2^{k-1}$.

Let $I(k)$ count the number of irreducible covering sets of size $k$. Balister, Bollobás, Morris, Sahasrabudhe, and Tiba [BBMST24] proved that\[I(k) \leq \exp\left((c+o(1))\frac{k^{3/2}}{(\log k)^{1/2}}\right)\]by proving that the right-hand side is an asymptotic for the number of minimal covering systems on $k$ moduli.

It is trivial that $\sum\frac{1}{n_i}>1$ for any irreducible covering set.

See also [1188].

View the LaTeX source

This page was last edited 08 April 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
Related OEIS sequences: Possible
0 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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 #1189, https://www.erdosproblems.com/1189, accessed 2026-04-10
OPEN This is open, and cannot be resolved with a finite computation.
Let\[\epsilon_m=\max \sum \frac{1}{n_i}\]where the maximum is taken over all finite sequences $m<n_1<\cdots<n_k$ for which there exist congruences $a_i\pmod{n_i}$ such that no integer satisfies two such congruences.

Estimate $\epsilon_m$.
#1190: [Er80,p.96]
number theory | covering systems
Disclaimer: The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Erdős [Er80] seems to credit Mirsky and Newman with the result that $\epsilon_m<1$, but gives no reference. He could not even decide whether $\epsilon_m\to 0$ as $m\to \infty$.

The number of $n_1<\cdots<n_k<x$ with disjoint congruences is the subject of [202]. The work of de la Bretéche, Ford, and Vandehey [BFV13] implies\[L(m)^{-1+o(1)}< \epsilon_m < L(m)^{-\sqrt{3}/2+o(1)},\]where $L(m)=\exp(\sqrt{\log m\log\log m})$. (The upper bound follows immediately from their upper bound as reported in [202] and partial summation; the lower bound is implicit in their construction.)

View the LaTeX source

This page was last edited 06 April 2026. View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
Related OEIS sequences: Possible
0 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

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 #1190, https://www.erdosproblems.com/1190, accessed 2026-04-10