Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passaudited 2026-07-31
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 n0,,nr1n_0,\ldots,n_{r-1} be a finite pairwise-coprime list of positive integers and let N:=i<rniN:=\prod_{i<r}n_i. The map

Φ:Z/Ni<rZ/ni,[x]N([x]ni)i<r,\Phi:\mathbb Z/N\longrightarrow\prod_{i<r}\mathbb Z/n_i,\qquad[x]_N\longmapsto([x]_{n_i})_{i<r},

is a bijection. It preserves addition, multiplication, [0][0], and [1][1] componentwise. For the empty list, N=1N=1 and both sides have one element.

Facts & Assumptions

Given: A natural rr, a finite pairwise-coprime list of positive integers n0,,nr1n_0,\ldots,n_{r-1}, and N:=i<rniN:=\prod_{i<r}n_i.

[L1]

Every initial product Pk:=i<kniP_k:=\prod_{i<k}n_i is coprime to nkn_k, 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).

[L2]

For coprime positive m,nm,n, each pair of residue classes modulo m,nm,n determines exactly one class modulo mnmn (For coprime positive m,nm,n, every pair of residue classes modulo mm and nn has a unique simultaneous class modulo mnmn).

[L5]

A map is bijective exactly when it is both injective and surjective (Injection, surjection, bijection).

[L6]

Induction proves a statement at every natural number from its base case and successor implication (The principle of mathematical induction).

[F1]

The quotient Z/c\mathbb Z/c is the set of congruence classes modulo cc (The congruence class [a]n[a]_n and the quotient set Z/n\mathbb{Z}/n).

Proof

technique · induction
1.1

For r=0r=0, N=P0=1N=P_0=1. The quotient Z/1\mathbb Z/1 has one class because congruence modulo 11 is universal, and the empty Cartesian product has its single empty tuple; hence Φ\Phi is a bijection and all componentwise preservation assertions are vacuous.

baseL3L4F1
1.2

Assume the simultaneous-residue assertion for the first kk moduli. Given classes modulo the first k+1k+1 moduli, the induction hypothesis supplies a unique class [y]Pk[y]_{P_k} having the first kk residues. Since gcd(Pk,nk)=1\gcd(P_k,n_k)=1 by [L1], [L2] supplies a unique class [x]Pknk=[x]Pk+1[x]_{P_kn_k}=[x]_{P_{k+1}} reducing to [y]Pk[y]_{P_k} and to the prescribed class modulo nkn_k. It therefore has all prescribed residues.

ihL1L2L3
1.3

If xy(modN)x\equiv y\pmod N, every nin_i divides NN and hence divides xyx-y, so Φ\Phi is well defined. For representatives x,yx,y, its iith coordinate sends [x+y]N[x+y]_N to [x+y]ni=[x]ni+[y]ni[x+y]_{n_i}=[x]_{n_i}+[y]_{n_i} and sends [xy]N[xy]_N to [xy]ni=[x]ni[y]ni[xy]_{n_i}=[x]_{n_i}[y]_{n_i}; it similarly sends [0]N,[1]N[0]_N,[1]_N to the componentwise identities.

L3L4
2.1

If two classes modulo Pk+1P_{k+1} have the same first k+1k+1 residues, their representatives have difference divisible by every nin_i for i<k+1i<k+1, hence by Pk+1P_{k+1} using [L1]; the two classes are equal. Thus the class constructed in step 1.2 is unique.

ihstep 1.2L1L4
3.1

Induction gives existence and uniqueness for every finite length rr. Therefore Φ\Phi is surjective and injective, hence bijective by [L5].

step 1.1step 1.2step 2.1L5L6
4.1

Steps 3.1 and 1.3 prove all assertions, including the empty-list boundary case from step 1.1.

step 1.1step 3.1step 1.3discharge-induction

Depends on

Used by

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