Erdős Problem 275

Theorem 275 · Erdős

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 $2^{i-1}\pmod{2^i}$ shows. This was proved independently by Selfridge and Crittenden and Vanden Eynden [CrVE70].

This was formalized in Lean by Alexeev using Aristotle.

Formal statement · Lean 4.lean

theorem erdos_275 (r : ℕ) (a : Fin r → ℤ) (n : Fin r → ℕ)
    (H : ∃ k : ℤ, ∀ x ∈ Ico k (k + 2 ^ r), ∃ i, x ≡ a i [ZMOD n i]) (x : ℤ) :
    ∃ i, x ≡ a i [ZMOD n i] := by
  sorry

Proof. sorry

Nobody has tried yet.

Reference ↗ · Lean source ↗