Theorem 9.1 — generalized Chinese remainder theorem
ProvedFernauIntersection.Bounded.theorem_9_1number-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexity
Let , let be positive integers (moduli) and integers (residues), and consider the system of congruences
Theorem 9.1 (Generalized Chinese Remainder Theorem).
- The system has an integral solution if and only if divides for all pairs .
- All integral solutions are congruent modulo .
- There is a natural number with for all if and only if for all .
Unlike the classical Chinese remainder theorem, the moduli need not be pairwise coprime. In the paper the theorem decides which pairs of vertices of different automata are joined by the edges of the Multicolored Clique instance built in the proof of Theorem 9.2.
Formalization Note. The moduli are natural numbers with , the residues integers, and the congruences are Mathlib's Int.ModEq. The lcm of the empty family () is .
Differences from the source:
- encoding: moduli m_i and residues r_i, indices 1..k → moduli m : Fin k → ℕ with m i > 0, residues r : Fin k → ℤ, 0-based indices; reason: the source's moduli are positive integers; no instance changes
Preamble
import Mathlib.Algebra.GCDMonoid.Finset import Mathlib.Algebra.GCDMonoid.Nat import Mathlib.Data.Int.GCD import Mathlib.Data.Int.ModEq import Mathlib.Data.Fintype.Fin
Formal statement
namespace FernauIntersection.Bounded
/-- Theorem 9.1 (Generalized Chinese Remainder Theorem, p. 23:18), for `k` congruences
`x ≡ rᵢ (mod mᵢ)` with positive moduli `mᵢ` and integer residues `rᵢ`: (1) an integral solution
exists iff `gcd(mᵢ, mⱼ) ∣ rᵢ - rⱼ` for all `i ≠ j`; (2) all integral solutions are congruent modulo
`lcm(m₁, …, m_k)`; (3) a natural-number solution exists iff `rᵢ ≡ rⱼ (mod gcd(mᵢ, mⱼ))` for all
`i, j`. -/
theorem theorem_9_1 (k : ℕ) (m : Fin k → ℕ) (hm : ∀ i, 0 < m i) (r : Fin k → ℤ) :
((∃ x : ℤ, ∀ i, x ≡ r i [ZMOD (m i : ℤ)]) ↔
∀ i j, i ≠ j → ((Nat.gcd (m i) (m j) : ℕ) : ℤ) ∣ r i - r j) ∧
(∀ x y : ℤ, (∀ i, x ≡ r i [ZMOD (m i : ℤ)]) → (∀ i, y ≡ r i [ZMOD (m i : ℤ)]) →
x ≡ y [ZMOD ((Finset.univ.lcm m : ℕ) : ℤ)]) ∧
((∃ x : ℕ, ∀ i, (x : ℤ) ≡ r i [ZMOD (m i : ℤ)]) ↔
∀ i j, r i ≡ r j [ZMOD ((Nat.gcd (m i) (m j) : ℕ) : ℤ)]) := by sorry
end FernauIntersection.Bounded
Source
Fernau, Hoffmann, Wehar (2021), arXiv:2108.05244v1, Theorem 9.1, p. 23:18 (PDF p. 18)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.