Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
Can the smallest modulus of a covering system be arbitrarily large? This problem has a negative answer: there is a universal bound on the least modulus of any distinct covering system.
Is there a covering system all of whose moduli are odd (and greater than 1)?
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…
Is there an integer \(m\) with \((m, 6) = 1\) such that none of \(2^k \cdot 3^\ell \cdot m + 1\) are prime, for any \(k, \ell \ge 0\)?
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…
Is there a covering system all of whose moduli are of the form \(p-1\) for some primes \(p \geq 5\)?
Herzog-Schönheim conjecture
If \(G\) is a group, can there exist an exact covering of \(G\) by more than one coset of different sizes? (i.e. each element is contained in exactly one of the cosets.) The conjectured answer is no: in every such exact covering, two of…
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. This is best possible as the system…
Is there an infinite Lucas sequence \(a_0, a_1, \ldots\) where \(a_{n+2} = a_{n+1} + a_n\) for \(n \ge 0\) such that all \(a_k\) are composite, and yet no integer has a common factor with every term of the sequence?
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 divide \(n\)? This was answered affirmatively by Haight [Ha79].
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\)?
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…
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…
Is there a covering system such that no two of the moduli divide each other? Asked by Schinzel, motivated by a question of Erdős and Selfridge (see [7](https://www.erdosproblems.com/7)). The answer is no, as proved by Balister, Bollobás,…
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. This is true, and was proved…
Sierpinski numbers
**Erdős Problem 1113.** Do there exist Sierpiński numbers that possess no finite covering set of primes? Erdős and Graham [ErGr80] conjectured that the answer is yes. A negative answer would imply that there are infinitely many Fermat…
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…
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…