Erdős Problems

Browse all problems

↑ ↓ to move↵ to openesc to close

Loading problem…

Status

On this page

Status

Topics

Terms Privacy info@plasma.ai

Problem 275 — Erdős Problems

Problem 275

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.

Source: erdosproblems.com/275

Number theory
Covering systems

Wiki page

Status

Solved·, Proved

An accepted solution exists. The statement is true.

PROVED (LEAN). The proof of Crittenden and Vanden Eynden and the short proof of Balister, Bollobás, Morris, Sahasrabudhe and Tiba, which the Lean proof follows, are recorded on the first and the second claim page (Balister, Bollobás, Morris, Sahasrabudhe and Tiba, 2019).

BBMST20b: Balister, P. and Bollobás, B. and Morris, R. and Sahasrabudhe, J. and Tiba, M., Covering intervals with arithmetic progressions. Acta Math. Hungar. (2020), 197-200.
CrVE70: Crittenden, R. B. and Vanden Eynden, C. L., Any $n$ arithmetic progressions covering the first $2^n$ integers cover all integers. Proc. Amer. Math. Soc. (1970), 475-481.

Proof claims

Loading proof claims…

Discussion

Loading discussion…

PreviousProblem 274 NextProblem 276

On this page

Statement
Status
References
Proof claims
Discussion

Status: Solved, Proved
Topics: Number theory
Covering systems
In the wiki: Wiki page