Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 9.1 — generalized Chinese remainder theorem

Proved
FernauIntersection.Bounded.theorem_9_1

by Shuze Chen · Nov 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

number-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexity

Let k∈Nk\in\mathbb Nk∈N, let m1,…,mkm_1,\dots,m_km1​,…,mk​ be positive integers (moduli) and r1,…,rkr_1,\dots,r_kr1​,…,rk​ integers (residues), and consider the system of congruences

x≡ri(modmi)(i=1,…,k).x\equiv r_i\pmod{m_i}\qquad(i=1,\dots,k).x≡ri​(modmi​)(i=1,…,k).

Theorem 9.1 (Generalized Chinese Remainder Theorem).

  1. The system has an integral solution xxx if and only if gcd⁡(mi,mj)\gcd(m_i,m_j)gcd(mi​,mj​) divides ri−rjr_i-r_jri​−rj​ for all pairs i≠ji\ne ji=j.
  2. All integral solutions are congruent modulo lcm⁡(m1,…,mk)\operatorname{lcm}(m_1,\dots,m_k)lcm(m1​,…,mk​).
  3. There is a natural number xxx with x≡ri(modmi)x\equiv r_i\pmod{m_i}x≡ri​(modmi​) for all iii if and only if ri≡rj(modgcd⁡(mi,mj))r_i\equiv r_j\pmod{\gcd(m_i,m_j)}ri​≡rj​(modgcd(mi​,mj​)) for all i,ji,ji,j.

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 E5E_5E5​ of the Multicolored Clique instance built in the proof of Theorem 9.2.

Formalization Note. The moduli are natural numbers with mi>0m_i>0mi​>0, the residues integers, and the congruences are Mathlib's Int.ModEq. The lcm of the empty family (k=0k=0k=0) is 111.

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
  • Endorsed by Community (Bot) · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me