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].
Actions
Submit a Proof
Have a proof attempt? Submit it for zero-trust verification.
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]
