Number theory and algebra · existing Mathlib theorem
Chinese Remainder Theorem
When two moduli are coprime, one residue modulo their product carries exactly the same information as one ordered pair of component residues, and the correspondence respects both addition and multiplication.
Accepted Atlas resultNot recorded for the preferred artifact
These states distinguish upstream identity, local reproduction, review, and Atlas acceptance. This page is part of the public, read-only Mathlib landmark collection.
Formal orientation
Statement map
This deterministic map orients the reader from the mathematical summary to the pinned declaration and exact checked form. The HTML statement below is authoritative.
The theorem at a glance
Chinese Remainder Theorem — exact two-modulus ring form
A source-bound editorial overview of the exact Mathlib formulation. The image is explanatory; the statement map, formal type, and pinned source remain authoritative.
Chinese Remainder Theorem — exact two-modulus ring form
The two-modulus ZMod correspondence is bijective and preserves addition and multiplication. Generated explanation only; the exact HTML statement and pinned source are authoritative.Detailed visual description
The retained poster presents coprimality, the three rings, the forward and reverse reading, ring-operation preservation, and the exact two-modulus boundary of ZMod.chineseRemainder.
Coprimality makes one residue modulo m*n equivalent to one ordered pair modulo m and n. Generated explanation only; the exact HTML statement and pinned source are authoritative.Detailed visual description
The construction reduces a product residue to both component moduli, reconstructs it from the pair, and preserves the two ring operations.
Complementary intuition
A mathematical landmark
The Chinese Remainder Theorem turns a modular problem into independent coprime components. It is foundational in number theory, algebra, algorithms, and cryptography.
The low-text schematic gives the theorem a visual identity; it does not replace the source-bound poster or exact statement.
Authoritative formal type
Exact Mathlib statement
def ZMod.chineseRemainder {m n : ℕ} (h : m.Coprime n) : ZMod (m * n) ≃+* ZMod m × ZMod n
Selected evidence declaration text
def ZMod.chineseRemainder {m n : ℕ} (h : m.Coprime n) : ZMod (m * n) ≃+* ZMod m × ZMod n
Proof architecture
From one product residue to an ordered residue pair
4 curated stages
Mathlib constructs a ring equivalence between ZMod (m * n) and ZMod m × ZMod n for coprime natural moduli. The source builds the forward reduction map and a case-split inverse, proves both inverse laws, and packages the correspondence with its additive and multiplicative structure.
These source-anchored stages explain the retained Mathlib proof route. They are generated explanations, not proof evidence or an extracted Lean proof-term dependency graph.
Reduction sends one product residue to its ordered pair of component residues.
to_fun : ZMod (m * n) → ZMod m × ZMod n
The forward map to_fun is ZMod.castHom into the product ring. Coprimality identifies the least common multiple with the product, so one residue modulo m*n determines both component residues while preserving addition and multiplication.
02
Construct the inverse in both product cases
Construct the inverse in both product cases
Loading full-resolution image…
The inverse reconstructs a product residue, with the zero-product edge cases kept separate from the nonzero CRT branch.Open original image in a new tab ↗
The inverse reconstructs a product residue, with the zero-product edge cases kept separate from the nonzero CRT branch.
inv_fun : ZMod m × ZMod n → ZMod (m * n)
The inverse map branches on m*n=0. Coprimality reduces that edge case to a trivial factor, while the nonzero branch applies Nat.chineseRemainder to the canonical values of the two component residues.
03
Prove the two maps are inverse
Prove the two maps are inverse
Loading full-resolution image…
Simultaneous congruences recover the original residue, and finite cardinality closes the reverse identity.Open original image in a new tab ↗
Simultaneous congruences recover the original residue, and finite cardinality closes the reverse identity.
Nat.modEq_and_modEq_iff_modEq_mul turns agreement modulo both coprime factors into agreement modulo their product, proving the left inverse. rightInverse_of_card_le then uses the matching finite cardinalities to obtain the right inverse.
04
Assemble the ring equivalence
Assemble the ring equivalence
Loading full-resolution image…
The reversible correspondence preserves addition and multiplication, completing the two-modulus ring equivalence.Open original image in a new tab ↗
The reversible correspondence preserves addition and multiplication, completing the two-modulus ring equivalence.
ZMod (m * n) ≃+* ZMod m × ZMod n
The final structure packages to_fun, inv_fun, map_add, map_mul, and the two inverse laws. The endpoint is exactly a ring equivalence between the product modulus and the ordered pair of component moduli.
Claim boundary
No new theorem is claimed
This target indexes Mathlib's ring equivalence between integers modulo mn and pairs modulo m and n when m and n are coprime. It is the two-modulus ZMod form, not a finite-family formulation, an integer representative algorithm, or a new proof.
The selected declaration covers exactly two coprime natural moduli.
It states a ZMod ring equivalence, not an exposed integer-representative algorithm.
ProofAtlas is indexing an existing Mathlib construction, not claiming a new theorem or proof.
