Let r∈ N, let a_1,…,a_r∈ Z, and let n_1,…,n_r∈ N, with the moduli not required to be distinct. If there exists an integer k such that every integer x with k≤ x<k+2^r satisfies x equiv a_i pmodn_i for at least one i∈1,…,r, then every integer x satisfies x equiv a_i pmodn_i for at least one i∈1,…,r.

Erdős Problem #275 — Finite Coverings by Congruence Classes

At least 62 years old · documented by 1963

Let $r\in\mathbb N$ , let $a_1,\dots,a_r\in\mathbb Z$ , and let $n_1,\dots,n_r\in\mathbb N$ , with the moduli not required to be distinct. If there exists an integer $k$ such that every integer $x$ with $k\le x<k+2^r$ satisfies

x\equiv a_i\pmod{n_i}

for at least one $i\in\{1,\dots,r\}$ , then every integer $x$ satisfies

x\equiv a_i\pmod{n_i}

for at least one $i\in\{1,\dots,r\}$ .

References

Primary source

The Formal Conjectures Authors, Formal Conjectures (2025); independently edited from the pinned source file.

Additional references

Pinned Formal Conjectures source, Apache-2.0.

covering-systems number-theory

InErdős Problems

Posted 2 months ago · edited 3 weeks ago

Progress summary

Refreshed 1 month ago

Claimed solved

The conjecture is settled: covering a block of the specified length forces the congruences to cover every integer.

Erdős posed this conjecture in 1962: any $r$ congruence classes covering $2^r$ consecutive integers must cover all integers. Crittenden and Vanden Eynden proved it in 1970.

Known results

Crittenden and Vanden Eynden, 1970: proved the $2^r$ theorem, allowing repeated moduli.
Balister, Bollobás, Morris, Sahasrabudhe, and Tiba, 2019: gave a simpler proof.

2019 simpler proof

The 2019 work supplied a shorter proof of the already established integer result; the later literature treats the theorem as proved, not conjectural.

Current status (as of August 2026): The stated theorem is resolved, with the original proof from 1970 and a simpler proof from 2019; no unresolved objection or newer competing claim was found.

AristotleHarmonicsolvedevidence

Sources

arxiv.org

No solutions have been posted yet.