Existing in Mathlib · Number theory and algebra

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.

Chinese remainder theorem
coprime moduli
residue rings
ring equivalence

Exact definition

Exact Mathlib definition

def ZMod.chineseRemainder {m n : ℕ} (h : m.Coprime n) : ZMod (m * n) ≃+* ZMod m × ZMod n

The theorem at a glance

Chinese Remainder Theorem — exact two-modulus ring form

A visual guide to the theorem's hypotheses, structure, and conclusion; the exact statement gives the formal detail.

Editorial theorem poster connects a gold product-modulus wheel to emerald and cobalt component wheels, states the ring equivalence in words, and gives a four-step reading guide. — The two-modulus ZMod correspondence is bijective and preserves addition and multiplication.

Statement structure

Statement and scope

Read the exact Mathlib declaration

This map summarizes the statement's structure; the exact Mathlib declaration remains authoritative.

Scientific figure illustrating: Coprimality makes one residue modulo m*n equivalent to one ordered pair modulo m and n. — Coprimality makes one residue modulo m*n equivalent to one ordered pair modulo m and n.

Why it matters

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.

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.

Reduce one product residue to a pair
Reduce one product residue to a pair
Reduction sends one product residue to its ordered pair of component residues.
Open original image in a new tab
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.
Construct the inverse in both product cases
Construct the inverse in both product cases
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.
Prove the two maps are inverse
Prove the two maps are inverse
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.
LeftInverse inv_fun to_fun ∧ RightInverse inv_fun to_fun
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.
Assemble the ring equivalence
Assemble the ring equivalence
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.

ProofAtlas record

What has been checked

Upstream indexedPinned source bytes verified locally

Locally reproducedExact upstream declaration replayed

Reviewed pageCurrent public presentation reviewed

Accepted Atlas resultNot recorded for the preferred artifact

Mathlib is the source of the theorem; the local Lean replay and page review are separate.

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.

Source and local evidence

Where the theorem comes from

Existing declaration: ZMod.chineseRemainder in mathlib
Relationship: The checked artifact is the upstream declaration itself
Local Lean evidence: artifact.library.mathlib.chinese-remainder-theorem.v001
Source: Open the pinned upstream reference