How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced — the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted — a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated — a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
Chinese remainder theorem for a finite pairwise-coprime list: simultaneous residues determine one class modulo the product, and the resulting bijection preserves addition and multiplication
Statement
Let be a finite pairwise-coprime list of positive integers and let . The map
is a bijection. It preserves addition, multiplication, , and componentwise. For the empty list, and both sides have one element.
Facts & Assumptions
Given: A natural , a finite pairwise-coprime list of positive integers , and .
Every initial product is coprime to , and the full product divides every common multiple of all list entries (For a finite pairwise-coprime list of positive integers, the product divides every common multiple, and each initial product is coprime to every remaining modulus).
For coprime positive , each pair of residue classes modulo determines exactly one class modulo (For coprime positive , every pair of residue classes modulo and has a unique simultaneous class modulo ).
Finite products have empty value and satisfy (The product of a finite list in a monoid, by recursion, with the empty product () equal to the identity, Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either).
Congruence modulo a divisor follows from congruence modulo the dividend, and modular addition and multiplication are computed on representatives (Congruence modulo an integer: when , including the moduli and , Addition and multiplication on by and ).
A map is bijective exactly when it is both injective and surjective (Injection, surjection, bijection).
Induction proves a statement at every natural number from its base case and successor implication (The principle of mathematical induction).
The quotient is the set of congruence classes modulo (The congruence class and the quotient set ).
Proof
For , . The quotient has one class because congruence modulo is universal, and the empty Cartesian product has its single empty tuple; hence is a bijection and all componentwise preservation assertions are vacuous.
Assume the simultaneous-residue assertion for the first moduli. Given classes modulo the first moduli, the induction hypothesis supplies a unique class having the first residues. Since by [L1], [L2] supplies a unique class reducing to and to the prescribed class modulo . It therefore has all prescribed residues.
If , every divides and hence divides , so is well defined. For representatives , its th coordinate sends to and sends to ; it similarly sends to the componentwise identities.
If two classes modulo have the same first residues, their representatives have difference divisible by every for , hence by using [L1]; the two classes are equal. Thus the class constructed in step 1.2 is unique.
Induction gives existence and uniqueness for every finite length . Therefore is surjective and injective, hence bijective by [L5].
Steps 3.1 and 1.3 prove all assertions, including the empty-list boundary case from step 1.1.
Depends on
- For coprime positive $m,n$, every pair of residue classes modulo $m$ and $n$ has a unique simultaneous class modulo $mn$
- For a finite pairwise-coprime list of positive integers, the product divides every common multiple, and each initial product is coprime to every remaining modulus
- The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ($n = 0$) equal to the identity
- Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either
- The principle of mathematical induction
- Addition and multiplication on $\mathbb{Z}/n$ by $[a]_n+[b]_n=[a+b]_n$ and $[a]_n[b]_n=[ab]_n$
- Injection, surjection, bijection
- Congruence modulo an integer: $a\equiv b\pmod n$ when $n\mid(a-b)$, including the moduli $0$ and $1$
- The congruence class $[a]_n$ and the quotient set $\mathbb{Z}/n$
Used by
- Euler's totient is multiplicative: gcd(m,n)=1 implies φ(mn)=φ(m)φ(n) for positive m,n Corollary
- Every abelian group of order n is cyclic if and only if n is squarefree Corollary
- The system x≡1pmod2, x≡2pmod4 has no solution, so coprimality in the Chinese remainder theorem cannot be dropped Counterexample
- The Chinese remainder bijection ℤ/12→ℤ/3×ℤ/4 computed on all standard representatives Example
- The cyclic group of order six in elementary-divisor and invariant-factor forms Example
- The system x≡2pmod3, x≡3pmod5, x≡2pmod7 has the unique solution x≡23pmod105 Example
- Elementary divisors regroup uniquely into invariant factors Lemma
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 88 results over 29 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- K. Conrad, The Chinese Remainder Theorem (standard reference, not scraped)