21.01.03 · number-theory / elementary

Congruences, the Chinese remainder theorem, and the ring structure of ℤ/nℤ

shipped3 tiersLean: none

Anchor (Master): Sun Zi c. 4th-5th c. CE *Sunzi Suanjing* (originator example); Qin Jiushao 1247 *Mathematical Treatise in Nine Sections* (Da Yan procedure); Gauss 1801 *Disquisitiones Arithmeticae* arts. 1-37, 49-89 (canonical modern formulation); Hardy-Wright 2008 *An Introduction to the Theory of Numbers* 6e §§V-VI; Lang 2002 *Algebra* (Springer GTM 211, 3e) Ch. II §2; Niven-Zuckerman-Montgomery 1991 *An Introduction to the Theory of Numbers* 5e §2; Shamir 1979 *CACM* 22 (secret sharing); Schönhage-Strassen 1971 *Computing* 7 (CRT-based fast integer multiplication)

Intuition Beginner

A congruence is an equation that ignores multiples of a fixed number. Two whole numbers $a$ and $b$ are congruent modulo $n$ when they leave the same remainder upon division by $n$ . The notation, due to Gauss in 1801, is $a \equiv b (mod n)$ . Examples: $13 \equiv 1 (mod 12)$ , because $13$ and $1$ both leave remainder $1$ when divided by $12$ ; $26 \equiv 12 \equiv 0 (mod 2)$ , because both are even.

Clock arithmetic is the everyday picture. A $12$ -hour clock identifies $13$ with $1$ , $14$ with $2$ , and so on. Adding $5$ hours to $10$ o'clock gives $3$ o'clock, because $10 + 5 = 15 \equiv 3 (mod 12)$ . The seven-day week is the same idea modulo $7$ : a hundred days from Wednesday is Friday, because $100 \equiv 2 (mod 7)$ and Wednesday plus two is Friday. Every cyclic phenomenon — clocks, calendars, musical octaves, the angles in a circle — is congruence in disguise.

The set of residue classes modulo $n$ is written $Z / n Z$ and consists of $n$ elements: $[0], [1], [2], \dots, [n - 1]$ . The bracket means "the class of all whole numbers that leave this remainder". The class $[1]$ modulo $12$ collects $\dots, - 23, - 11, 1, 13, 25, 37, \dots$ — every number that lands on the $1$ position when you walk around a $12$ -hour clock. Addition and multiplication of these classes are defined by picking any representatives, doing the operation, and reducing modulo $n$ . The result does not depend on which representatives you chose.

The Chinese remainder theorem is the surprise of the subject. Suppose you want a number $x$ that leaves remainder $2$ when divided by $3$ and remainder $3$ when divided by $5$ . The answer is $x = 8$ , and every other answer differs from $8$ by a multiple of $15 = 3 \times 5$ . The theorem says that whenever two moduli have no common factor, simultaneous congruences with those moduli always have a unique solution modulo their product. This generalises to any number of pairwise-coprime moduli.

Modular arithmetic is the workhorse behind familiar systems. ISBN-10 book numbers use a checksum modulo $11$ to detect typos: the ten digits $d_{1}, d_{2}, \dots, d_{10}$ satisfy $d_{1} + 2 d_{2} + 3 d_{3} + \dots + 10 d_{10} \equiv 0 (mod 11)$ , and a single-digit error or any swap of two adjacent digits breaks the congruence. Credit card numbers use the Luhn algorithm modulo $10$ . RSA encryption computes powers modulo a large product of two primes — every secure web connection you make routes through the arithmetic of $Z / n Z$ for $n$ with hundreds of digits.

Visual Beginner

A picture of two circular clocks side by side. The left clock has $12$ positions and shows arrows labelling $13 \to 1$ , $14 \to 2$ , $25 \to 1$ , illustrating the wrap-around when you walk past $12$ .

The right clock has $15$ positions, with one arrow at position $8$ . Below it, two smaller clocks of size $3$ and $5$ both point to the same image of $8$ : the size- $3$ clock has $8$ at position $2$ (since $8 = 2 \times 3 + 2$ ), and the size- $5$ clock has $8$ at position $3$ (since $8 = 1 \times 5 + 3$ ). An arrow connects the pair of small clocks to the big size- $15$ clock, illustrating the Chinese remainder correspondence: a position on the $15$ -clock is a position on the $3$ -clock paired with a position on the $5$ -clock.

The picture captures the central fact of the subject. A clock of size $n$ is a circular world in which numbers wrap around. When $n = mk$ with $m$ and $k$ coprime, the clock of size $n$ splits into a pair: a clock of size $m$ and a clock of size $k$ . Specifying a position on the big clock is the same as specifying a pair of positions on the two smaller clocks. The Chinese remainder theorem is the rigorous statement of this splitting.

Worked example Beginner

Find a whole number $x$ such that $x \equiv 2 (mod 3)$ and $x \equiv 3 (mod 5)$ . State the answer as a single residue modulo $15$ .

Step 1. List the numbers satisfying $x \equiv 2 (mod 3)$ between $0$ and $14$ : these are $2, 5, 8, 11, 14$ .

Step 2. List the numbers satisfying $x \equiv 3 (mod 5)$ between $0$ and $14$ : these are $3, 8, 13$ .

Step 3. The intersection is ${8}$ . So $x = 8$ is one solution, and every solution differs from $8$ by a multiple of $15$ . The full solution set is $x \equiv 8 (mod 15)$ .

Step 4. Check: $8 = 2 \times 3 + 2$ , so $8 \equiv 2 (mod 3)$ . And $8 = 1 \times 5 + 3$ , so $8 \equiv 3 (mod 5)$ . Both conditions are satisfied.

What this tells us: when the two moduli $3$ and $5$ have no common factor, the pair of congruences pins down a unique residue modulo the product $3 \times 5 = 15$ . The same construction extends to any number of pairwise-coprime moduli — five conditions modulo $2, 3, 5, 7, 11$ specify a unique residue modulo $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310$ .

Check your understanding Beginner

Formal definition Intermediate+

The notion of congruence, the ring $Z / n Z$ , its group of units, and the Chinese remainder theorem admit clean definitions on the foundation laid by 21.01.01 (Bézout, gcd) and 21.01.02 (primes, the fundamental theorem).

Definition (congruence). For integers $a, b \in Z$ and a positive integer $n$ , we say $a$ is congruent to $b$ modulo $n$ , written $a \equiv b (mod n)$ , if $n ∣ (a - b)$ . Equivalently, $a$ and $b$ have the same remainder upon division by $n$ .

The relation $\equiv (mod n)$ is an equivalence relation: reflexive ( $n ∣ 0$ ), symmetric ( $n ∣ (a - b)$ iff $n ∣ (b - a)$ ), transitive ( $n ∣ (a - b)$ and $n ∣ (b - c)$ imply $n ∣ (a - c)$ since $(a - c) = (a - b) + (b - c)$ ). It is compatible with $+$ and $\times$ : if $a \equiv a^{'} (mod n)$ and $b \equiv b^{'} (mod n)$ , then $a + b \equiv a^{'} + b^{'} (mod n)$ and $ab \equiv a^{'} b^{'} (mod n)$ .

Definition (residue classes; the ring $Z / n Z$ ). The residue class of $a$ modulo $n$ is $[a]_{n} = {b \in Z : a \equiv b (mod n)} = a + n Z$ . The set of residue classes is $$ \mathbb{Z}/n\mathbb{Z} ;=; { [0]_n, [1]_n, \ldots, [n-1]_n }, $$ a set of cardinality $n$ . Addition and multiplication on residue classes are defined by $[a]_{n} + [b]_{n} = [a + b]_{n}$ and $[a]_{n} \cdot [b]_{n} = [ab]_{n}$ ; the compatibility of congruence with $+$ and $\times$ shows these definitions are independent of choice of representative. The resulting structure $(Z / n Z, +, \cdot)$ is a commutative ring with identity, the ring of integers modulo $n$ .

Definition (group of units $(Z / n Z)^{\times}$ ). The group of units of $Z / n Z$ is $$ (\mathbb{Z}/n\mathbb{Z})^\times ;=; { [a]_n : \exists , [b]_n \text{ with } [a]_n \cdot [b]_n = [1]_n }. $$ By Bézout (proved in 21.01.01), $[a]_{n}$ has a multiplicative inverse modulo $n$ if and only if $g cd (a, n) = 1$ . The order of the group of units is the Euler totient $φ (n) = # {1 \leq a \leq n : g cd (a, n) = 1}$ . The first values are $φ (1) = 1$ , $φ (2) = 1$ , $φ (3) = 2$ , $φ (4) = 2$ , $φ (5) = 4$ , $φ (6) = 2$ , $φ (p) = p - 1$ for $p$ prime, and $φ (p^{k}) = p^{k} - p^{k - 1}$ for $p$ a prime power.

Definition (field; $Z / n Z$ as a field iff $n$ is prime). $Z / n Z$ is a field if and only if $n$ is prime. The forward direction: if $n = ab$ with $1 < a, b < n$ , then $[a]_{n} \cdot [b]_{n} = [n]_{n} = [0]_{n}$ , so $Z / n Z$ has zero-divisors and is not an integral domain. The reverse: if $n = p$ is prime, then $g cd (a, p) = 1$ for every $1 \leq a < p$ , so every nonzero element is a unit, and $Z / p Z$ is a field. We write $F_{p}$ for this field.

Counterexamples to common slips

" $[a]_{n} = [b]_{n}$ is the same as $a = b$ ." The class $[a]_{n}$ is an infinite set, namely $a + n Z$ . The classes $[1]_{12}$ and $[13]_{12}$ are equal because they have the same set of representatives, even though $1 \neq = 13$ as integers. Pedagogically, write $[a]_{n}$ when emphasising the class and $a$ when emphasising the representative.
"You can always cancel: $a x \equiv a y (mod n)$ implies $x \equiv y (mod n)$ ." False unless $g cd (a, n) = 1$ . Example: $2 \times 3 \equiv 2 \times 8 (mod 10)$ (both sides $\equiv 6$ ), but $3 \neq \equiv 8 (mod 10)$ . The correct cancellation rule: $a x \equiv a y (mod n)$ implies $x \equiv y (mod n / g cd (a, n))$ .
"Fermat's little theorem $a^{p - 1} \equiv 1 (mod p)$ holds for every $a$ ." It holds for every $a$ coprime to $p$ , equivalently for every nonzero residue class. The case $a \equiv 0 (mod p)$ gives $0^{p - 1} = 0 \neq \equiv 1 (mod p)$ . The unrestricted version is Fermat's little theorem in the form $a^{p} \equiv a (mod p)$ , which covers $a \equiv 0$ .

Key theorem with proof Intermediate+

The signature theorem of this unit is the Chinese remainder theorem in its modern form: a ring isomorphism $Z / (n_{1} n_{2}) Z ≅ Z / n_{1} Z \times Z / n_{2} Z$ when $g cd (n_{1}, n_{2}) = 1$ . We prove the two-modulus case in full; the multi-modulus generalisation follows by induction.

Theorem (Chinese remainder theorem, two-modulus form). Let $n_{1}, n_{2}$ be positive integers with $g cd (n_{1}, n_{2}) = 1$ , and set $n = n_{1} n_{2}$ . The map $$ \Phi : \mathbb{Z}/n\mathbb{Z} ;\longrightarrow; \mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z}, \qquad [x]n \longmapsto ([x]{n_1}, [x]_{n_2}), $$ is a ring isomorphism. In particular, for any pair $(a_{1}, a_{2}) \in Z / n_{1} Z \times Z / n_{2} Z$ , the simultaneous congruence system $$ x \equiv a_1 \pmod{n_1}, \qquad x \equiv a_2 \pmod{n_2} $$ admits a unique solution $[x]_{n}$ modulo $n$ .

Proof. $Φ$ is well-defined. If $[x]_{n} = [y]_{n}$ , then $n ∣ (x - y)$ , hence $n_{1} ∣ (x - y)$ and $n_{2} ∣ (x - y)$ ; so $[x]_{n_{1}} = [y]_{n_{1}}$ and $[x]_{n_{2}} = [y]_{n_{2}}$ .

$Φ$ is a ring homomorphism. Both addition and multiplication of residue classes are defined pointwise on representatives, and reduction modulo $n_{i}$ is itself a ring homomorphism $Z \to Z / n_{i} Z$ . The map $Φ$ is the product of the two reductions composed with the canonical surjection $Z \to Z / n Z$ , hence a ring homomorphism.

$Φ$ is injective. Suppose $Φ ([x]_{n}) = ([0]_{n_{1}}, [0]_{n_{2}})$ . Then $n_{1} ∣ x$ and $n_{2} ∣ x$ . Since $g cd (n_{1}, n_{2}) = 1$ , we have $n_{1} n_{2} ∣ x$ (a consequence of unique factorisation from 21.01.02, or directly from Bézout: choose $u, v$ with $u n_{1} + v n_{2} = 1$ , multiply $x = x \cdot 1 = xu n_{1} + xv n_{2}$ , and use $n_{2} ∣ xu n_{1}$ and $n_{1} ∣ xv n_{2}$ ). Hence $[x]_{n} = [0]_{n}$ , so the kernel is the identity element.

$Φ$ is surjective. Given $(a_{1}, a_{2})$ , we explicitly construct an integer $x$ with $Φ ([x]_{n}) = (a_{1}, a_{2})$ . By Bézout, since $g cd (n_{1}, n_{2}) = 1$ , there exist integers $u, v$ with $$ u n_2 + v n_1 = 1. $$ Set $e_{1} = u n_{2}$ and $e_{2} = v n_{1}$ . Then $e_{1} \equiv 1 (mod n_{1})$ , $e_{1} \equiv 0 (mod n_{2})$ , $e_{2} \equiv 0 (mod n_{1})$ , $e_{2} \equiv 1 (mod n_{2})$ . (The pair $(e_{1}, e_{2})$ is the CRT idempotent decomposition of $1$ .) The integer $$ x = a_1 e_1 + a_2 e_2 = a_1 u n_2 + a_2 v n_1 $$ satisfies $x \equiv a_{1} \cdot 1 + a_{2} \cdot 0 = a_{1} (mod n_{1})$ and $x \equiv a_{1} \cdot 0 + a_{2} \cdot 1 = a_{2} (mod n_{2})$ . Hence $Φ ([x]_{n}) = (a_{1}, a_{2})$ .

Since $Φ$ is an injective ring homomorphism between two finite sets of the same cardinality $n = n_{1} n_{2}$ , it is also surjective and hence bijective. $□$

Bridge. The CRT builds toward 01.02.06 commutative rings and ideals, where the proof above reappears as "if $I_{1} + I_{2} = R$ , then $R / (I_{1} \cap I_{2}) ≅ R / I_{1} \times R / I_{2}$ ". The central insight is exactly that coprimality of moduli is the operational content of $I_{1} + I_{2} = R$ — the ideal-theoretic encoding of "the moduli share no common factor". This is the bridge from elementary modular arithmetic to the ring-theoretic decomposition principles of 01.02.07 (Noether's first isomorphism theorem applied to the diagonal map). The pattern generalises to localisation (an isomorphism $R / m_{1} \dots m_{k} ≅ \prod R_{m_{i}} / m_{i} R_{m_{i}}$ for finite collections of maximal ideals), identifies the idempotent decomposition $1 = e_{1} + e_{2}$ with the structure of a product ring, and appears again in 01.02.18 pending the construction of $F_{q}$ as $F_{p} [x] / (f (x))$ for $f$ irreducible. Putting these together, the CRT is the proto-localisation theorem: it splits the global ring $Z / n Z$ into independent factors at each prime power dividing $n$ .

Exercises Intermediate+

Exercise 3 (medium, numeric).

Solve the five-modulus CRT system $x \equiv 1 (mod 2)$ , $x \equiv 2 (mod 3)$ , $x \equiv 3 (mod 5)$ , $x \equiv 4 (mod 7)$ , $x \equiv 5 (mod 11)$ . Enter $x$ in the range $0 \leq x < 2310$ .

Hint

Use the explicit construction in the proof: for each $i$ , compute $N_{i} = N / n_{i}$ where $N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310$ ; find $u_{i}$ with $N_{i} u_{i} \equiv 1 (mod n_{i})$ ; set $x = \sum_{i} a_{i} N_{i} u_{i} mod N$ .

Answer

$1523$ . Set $N = 2310$ . Compute $N_{i}$ and $u_{i}$ :

$N_{1} = 1155$ ; $1155 \equiv 1 (mod 2)$ , so $u_{1} = 1$ .
$N_{2} = 770$ ; $770 = 256 \times 3 + 2$ , so $770 \equiv 2 (mod 3)$ ; $u_{2} = 2$ (since $2 \times 2 = 4 \equiv 1$ ).
$N_{3} = 462$ ; $462 = 92 \times 5 + 2$ , so $462 \equiv 2 (mod 5)$ ; $u_{3} = 3$ (since $2 \times 3 = 6 \equiv 1$ ).
$N_{4} = 330$ ; $330 = 47 \times 7 + 1$ , so $330 \equiv 1 (mod 7)$ ; $u_{4} = 1$ .
$N_{5} = 210$ ; $210 = 19 \times 11 + 1$ , so $210 \equiv 1 (mod 11)$ ; $u_{5} = 1$ .

The sum: $$ x = 1 \cdot 1155 \cdot 1 + 2 \cdot 770 \cdot 2 + 3 \cdot 462 \cdot 3 + 4 \cdot 330 \cdot 1 + 5 \cdot 210 \cdot 1 $$ $= 1155 + 3080 + 4158 + 1320 + 1050 = 10763$ . Reduce: $10763 = 4 \times 2310 + 1523$ , so $x \equiv 1523 (mod 2310)$ . Verify by hand: $1523/2 = 761.5$ (remainder $1$ ), $1523/3 = 507.67$ (remainder $2$ ), $1523 = 304 \times 5 + 3$ , $1523 = 217 \times 7 + 4$ , $1523 = 138 \times 11 + 5$ — all five congruences hold.

Exercise 4 (medium, symbolic).

Prove Fermat's little theorem: for $p$ prime and $a$ not divisible by $p$ , $a^{p - 1} \equiv 1 (mod p)$ .

Hint

Consider the multiplication-by- $a$ map on $(Z / p Z)^{\times}$ . It is a bijection because $a$ is a unit. Compare the product of all nonzero residues with the product of $a$ times all nonzero residues.

Answer

Since $g cd (a, p) = 1$ , the residue $[a]_{p}$ is a unit. Consider the map $μ_{a} : (Z / p Z)^{\times} \to (Z / p Z)^{\times}$ given by $[x]_{p} \mapsto [a x]_{p}$ . This map is a bijection: it has inverse $μ_{a^{- 1}}$ , where $a^{- 1}$ is the modular inverse of $a$ (which exists because $g cd (a, p) = 1$ and Bézout).

Hence the set ${[a]_{p}, [2 a]_{p}, \dots, [(p - 1) a]_{p}}$ is a permutation of ${[1]_{p}, [2]_{p}, \dots, [p - 1]_{p}}$ . Multiplying all elements: $$ \prod_{k=1}^{p-1} [ka]p ;=; \prod{k=1}^{p-1} [k]_p. $$ The left side equals $[a]_{p}^{p - 1} \cdot \prod_{k = 1}^{p - 1} [k]_{p}$ . Cancelling the common factor $\prod [k]_{p}$ (which is a unit since each $[k]_{p}$ is a unit and the units form a group), $[a]_{p}^{p - 1} = [1]_{p}$ , i.e., $a^{p - 1} \equiv 1 (mod p)$ .

Rubric: full credit for the orbit-counting / pigeon-hole argument and the cancellation step. The same argument generalises to Euler's theorem $a^{φ (n)} \equiv 1 (mod n)$ for $g cd (a, n) = 1$ , replacing $p - 1$ by $φ (n)$ and $(Z / p)^{\times}$ by $(Z / n)^{\times}$ .

Exercise 5 (medium, symbolic).

Prove that the Euler totient $φ$ is multiplicative: if $g cd (m, n) = 1$ , then $φ (mn) = φ (m) φ (n)$ .

Hint

Use the CRT ring isomorphism $Z / mn Z ≅ Z / m Z \times Z / n Z$ and count units on both sides.

Answer

Restrict the CRT isomorphism $Φ : Z / mn Z \to Z / m Z \times Z / n Z$ to groups of units. A ring isomorphism sends units to units bijectively, and the unit group of a product ring is the product of unit groups (an element $(x, y)$ has an inverse iff both $x$ and $y$ have inverses). Hence $$ (\mathbb{Z}/mn\mathbb{Z})^\times ;\cong; (\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times. $$ Counting cardinalities, $φ (mn) = φ (m) φ (n)$ .

Combining this with the prime-power formula $φ (p^{k}) = p^{k} - p^{k - 1} = p^{k - 1} (p - 1)$ gives the closed form $$ \varphi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right). $$

Rubric: full credit for the CRT-based bijection argument. The closed-form derivation is a useful follow-up but optional for full credit on the multiplicativity statement.

Exercise 6 (medium, symbolic).

Prove Wilson's theorem: for $p$ prime, $(p - 1)! \equiv - 1 (mod p)$ .

Hint

In the product $\prod_{k = 1}^{p - 1} k$ modulo $p$ , pair each $k$ with its inverse $k^{- 1}$ . The pairs cancel to give $1$ , except for self-inverse elements. Find which elements are self-inverse.

Answer

Work in $F_{p}^{\times} = (Z / p Z)^{\times}$ . An element $x$ is self-inverse when $x^{2} = 1$ , i.e., $x^{2} - 1 = (x - 1) (x + 1) = 0$ in $F_{p}$ . Because $F_{p}$ is a field (a consequence of $p$ prime), it is an integral domain, so $(x - 1) (x + 1) = 0$ implies $x = 1$ or $x = - 1$ . Hence the only self-inverse elements of $F_{p}^{\times}$ are $[1]_{p}$ and $[- 1]_{p}$ .

In the product $\prod_{k = 1}^{p - 1} [k]_{p}$ , every non-self-inverse element $[k]_{p}$ pairs with its inverse $[k^{- 1}]_{p}$ ( $\neq = [k]_{p}$ ), contributing $1$ to the product. The unpaired contributions are $[1]_{p}$ and $[- 1]_{p}$ , multiplying to $[- 1]_{p}$ . Hence $$ (p-1)! = \prod_{k=1}^{p-1} k ;\equiv; -1 \pmod p. $$

For $p = 7$ : $6! = 720 = 102 \times 7 + 6 \equiv 6 \equiv - 1 (mod 7)$ . For $p = 13$ : $12! = 479001600 = 36846277 \times 13 + (- 1)$ — direct computation confirms.

Rubric: full credit for the pairing argument identifying self-inverses via the factorisation $(x - 1) (x + 1) = 0$ and the field property. The converse of Wilson is also true: if $(n - 1)! \equiv - 1 (mod n)$ then $n$ is prime; this gives an inefficient but conceptually clean primality test.

Exercise 7 (hard, symbolic).

Prove the structure theorem for $(Z / n Z)^{\times}$ via CRT: if $n = p_{1}^{k_{1}} \dots p_{r}^{k_{r}}$ is the prime factorisation of $n$ , then $(Z / n Z)^{\times} ≅ \prod_{i = 1}^{r} (Z / p_{i}^{k_{i}} Z)^{\times}$ as groups.

Hint

Apply the multi-modulus CRT to the pairwise-coprime moduli $p_{1}^{k_{1}}, \dots, p_{r}^{k_{r}}$ (they are coprime because the $p_{i}$ are distinct primes). Then restrict the ring isomorphism to unit groups.

Answer

The moduli $p_{1}^{k_{1}}, \dots, p_{r}^{k_{r}}$ are pairwise coprime: $g cd (p_{i}^{k_{i}}, p_{j}^{k_{j}}) = 1$ for $i \neq = j$ , because $p_{i}$ and $p_{j}$ are distinct primes. The multi-modulus CRT — proved by induction on $r$ , applying the two-modulus form to the pair $(p_{1}^{k_{1}}, p_{2}^{k_{2}} \dots p_{r}^{k_{r}})$ at each step — gives the ring isomorphism $$ \Psi : \mathbb{Z}/n\mathbb{Z} ;\xrightarrow{\sim}; \prod_{i=1}^r \mathbb{Z}/p_i^{k_i}\mathbb{Z}. $$ A ring isomorphism restricts to a group isomorphism on unit groups: $Ψ$ sends a unit to a tuple of units, and an element of the product is a unit iff every component is a unit. Hence $$ (\mathbb{Z}/n\mathbb{Z})^\times ;\cong; \prod_{i=1}^r (\mathbb{Z}/p_i^{k_i}\mathbb{Z})^\times, $$ as required.

Combined with the prime-power structure (Master Theorem 4 below: $(Z / p^{k})^{\times}$ is cyclic for $p$ odd; for $p = 2$ and $k \geq 3$ it is $Z /2 \times Z / 2^{k - 2}$ ), this gives a complete description of $(Z / n)^{\times}$ as an abstract abelian group. The result is the dimension-1 case of the structure theorem for finitely generated modules over a PID applied to $Z$ .

Rubric: full credit for the CRT-based reduction and the unit-group restriction argument. Stating the prime-power structure as a known input is acceptable; deriving it is a separate Master-tier task.

Exercise 8 (hard, symbolic).

Prove that for $p$ an odd prime and $k \geq 1$ , the group $(Z / p^{k} Z)^{\times}$ is cyclic of order $p^{k - 1} (p - 1)$ .

Hint

Step 1: $(Z / p)^{\times}$ is cyclic (a finite subgroup of the multiplicative group of a field is cyclic). Step 2: lift a generator $g$ of $(Z / p)^{\times}$ to an element of $(Z / p^{k})^{\times}$ of order $p^{k - 1} (p - 1)$ , using $(1 + p)^{p^{k - 1}} \equiv 1 + p^{k} \cdot c (mod p^{k + 1})$ for some $c$ coprime to $p$ .

Answer

Step 1: $(Z / p)^{\times}$ is cyclic of order $p - 1$ . This is the standard fact that every finite subgroup of the multiplicative group of a field is cyclic. Proof sketch: if $d ∣ (p - 1)$ , the polynomial $x^{d} - 1$ has at most $d$ roots in $F_{p}$ (a field property). For each $d ∣ (p - 1)$ , let $ψ (d)$ be the number of elements of order exactly $d$ in $F_{p}^{\times}$ . Either $ψ (d) = 0$ or $ψ (d) = φ (d)$ , by orbit counting in a cyclic subgroup of order $d$ . Summing $\sum_{d ∣ (p - 1)} ψ (d) = p - 1 = \sum_{d ∣ (p - 1)} φ (d)$ (the second equality is the standard divisor sum), so $ψ (d) = φ (d) > 0$ for every $d$ , in particular for $d = p - 1$ . A generator exists.

Step 2: Lifting. Let $g$ generate $(Z / p)^{\times}$ . Choose a representative integer $g$ with $1 \leq g \leq p - 1$ . The order of $g$ in $(Z / p^{k})^{\times}$ is a multiple of its order modulo $p$ , namely a multiple of $p - 1$ , and divides the group order $p^{k - 1} (p - 1)$ .

To force the order to equal $p^{k - 1} (p - 1)$ , possibly replace $g$ by $g + p$ if needed. Compute $(1 + p)^{p^{k - 2}} (mod p^{k})$ : expanding the binomial, $$ (1 + p)^{p^{k-2}} = 1 + p^{k-2} \cdot p + \binom{p^{k-2}}{2} p^2 + \cdots $$ For $p$ odd, all terms beyond the linear are divisible by $p^{k}$ , so $(1 + p)^{p^{k - 2}} \equiv 1 + p^{k - 1} (mod p^{k})$ , which is $\neq \equiv 1$ . Hence $1 + p$ has order exactly $p^{k - 1}$ in the kernel of $(Z / p^{k})^{\times} \to (Z / p)^{\times}$ .

Now show that for some $g_{0} \in {g, g + p}$ , the element $g_{0}$ has order $p - 1$ in $(Z / p^{k})^{\times}$ : $g^{p - 1} \equiv 1 (mod p)$ so $g^{p - 1} = 1 + pt$ for some $t$ . If $p ∤ t$ , then $g$ has $p$ -adic order $p - 1$ to the leading. If $p ∣ t$ , replace by $g + p$ : $(g + p)^{p - 1} = g^{p - 1} + (p - 1) g^{p - 2} p + O (p^{2}) = 1 + pt + (p - 1) g^{p - 2} p + O (p^{2})$ , and the linear coefficient $t + (p - 1) g^{p - 2}$ is no longer divisible by $p$ (since $p ∤ g^{p - 2}$ ).

Hence the element $g_{0} \cdot (1 + p)$ has order $lcm (p - 1, p^{k - 1}) = p^{k - 1} (p - 1)$ , generating $(Z / p^{k})^{\times}$ .

Failure at $p = 2$ . For $p = 2$ and $k \geq 3$ , the analogous lift fails: $(1 + 2)^{2^{k - 2}} = 3^{2^{k - 2}} \neq \equiv 1 + 2^{k - 1} (mod 2^{k})$ in general, because the binomial $(2 p ^{k - 2}) p^{2} = 2^{k - 3} (2^{k - 2} - 1) \cdot 4$ is no longer divisible by $2^{k}$ . The result is that $(Z / 2^{k})^{\times} ≅ Z /2 \times Z / 2^{k - 2}$ for $k \geq 3$ , generated by $- 1$ and $5$ .

Rubric: full credit for the cyclic-from-field argument in Step 1 and the binomial-lift argument in Step 2. Acknowledging the $p = 2$ exception receives bonus credit.

Lean formalization Intermediate+

Mathlib provides essentially all the operational machinery used in this unit. The Lean module Codex.NumberTheory.Elementary.CongruencesCRT packages the unit's load-bearing identifications alongside the standard Mathlib API.

-- Operative imports: Mathlib.Data.ZMod.Basic, Mathlib.Data.ZMod.Quotient,
-- Mathlib.NumberTheory.Padics, Mathlib.Data.Nat.Totient,
-- Mathlib.RingTheory.Ideal.QuotientOperations, Mathlib.NumberTheory.ZMod.Basic

#check @ZMod                       -- ZMod : ℕ → Type, the ring ℤ/nℤ
#check @ZMod.chineseRemainder      -- (m n : ℕ) [Coprime m n] : ZMod (m * n) ≃+* ZMod m × ZMod n
#check @Nat.totient                 -- Nat.totient : ℕ → ℕ, the Euler totient
#check @Nat.totient_mul             -- ∀ {m n : ℕ}, m.Coprime n → (m * n).totient = m.totient * n.totient

#check @ZMod.unitsEquivCoprime
-- ZMod.unitsEquivCoprime : (ZMod n)ˣ ≃ {x : ZMod n // IsCoprime x n}

#check @Ideal.quotientInfRingEquivPiQuotient
-- The general commutative-ring CRT: pairwise coprime ideals I_i with intersection J satisfy
-- R/J ≃+* Π i, R/I_i

#check @ZMod.pow_card_sub_one_eq_one
-- Fermat's little theorem: (a : ZMod p)^(p - 1) = 1 when p is prime and a ≠ 0

The CRT isomorphism ZMod.chineseRemainder is the operational form of the Key Theorem above; its inductive multi-modulus generalisation is ZMod.chineseRemainderRing (or assembled by hand from the two-modulus form). Fermat's little theorem is ZMod.pow_card_sub_one_eq_one; Wilson's theorem is ZMod.wilsons_lemma; the totient multiplicativity is Nat.totient_mul. What Mathlib does not yet supply as a unified module — the prime-power structure of $(Z / p^{k})^{\times}$ , the Carmichael function with its prime-power formula, the CRT-based RSA decryption, and the Schönhage-Strassen NTT modular rings — is documented in the unit metadata Mathlib gap analysis.

Advanced results Master

Theorem 1 (general CRT for commutative rings; Lang 2002 Ch. II §2). Let $R$ be a commutative ring with identity and let $I_{1}, \dots, I_{k}$ be pairwise coprime ideals of $R$ — that is, $I_{i} + I_{j} = R$ for every $i \neq = j$ . Then the canonical map $$ R ;\longrightarrow; \prod_{i=1}^k R/I_i, \qquad r \mapsto (r + I_1, \ldots, r + I_k), $$ has kernel $I_{1} \cap \dots \cap I_{k} = I_{1} \cdot I_{2} \dots I_{k}$ , and induces a ring isomorphism $$ R \big/ (I_1 \cap \cdots \cap I_k) ;\xrightarrow{\sim}; \prod_{i=1}^k R/I_i. $$ ^{[Lang 2002]}. The integer case is the special case $R = Z$ , $I_{i} = (n_{i})$ with $g cd (n_{i}, n_{j}) = 1$ ; the intersection becomes the principal ideal $(n_{1} n_{2} \dots n_{k})$ by unique factorisation. The polynomial-ring case $R = k [x]$ , $I_{i} = (x - a_{i})$ with distinct $a_{i} \in k$ gives Lagrange interpolation: a polynomial of degree $< k$ is determined by its values at $k$ distinct points. The general statement clarifies that CRT is the categorical content of "coprime decomposition" in any commutative ring, not a phenomenon special to $Z$ .

Theorem 2 (Euler totient and the multiplicativity formula; Gauss 1801 art. 38). The Euler totient $φ : Z_{> 0} \to Z_{> 0}$ is multiplicative: $φ (mn) = φ (m) φ (n)$ for $g cd (m, n) = 1$ . The closed form is $φ (n) = n \prod_{p ∣ n} (1 - 1/ p)$ ^{[Gauss 1801]}. The multiplicativity is the unit-group statement of the CRT isomorphism $Z / mn ≅ Z / m \times Z / n$ . The closed form is the prime-power formula $φ (p^{k}) = p^{k} - p^{k - 1} = p^{k - 1} (p - 1)$ assembled via multiplicativity. Dirichlet 1849 gave the average value $\frac{1}{N} \sum_{n \leq N} φ (n) \sim \frac{3 N}{π ^{2}}$ , with the constant identified as $1/ ζ (2)$ — a first hint of the analytic-number-theoretic content of $φ$ . The Möbius-inversion identity $\sum_{d ∣ n} φ (d) = n$ is equivalent to the partition of $Z / n$ into orbits of cyclic subgroups, each of size $φ (d)$ for some $d ∣ n$ .

Theorem 3 (Fermat-Euler theorem; Fermat 1640, Euler 1736). For $g cd (a, n) = 1$ , $a^{φ (n)} \equiv 1 (mod n)$ . Specialised to $n = p$ prime: $a^{p - 1} \equiv 1 (mod p)$ (Fermat 1640, in correspondence with Frénicle de Bessy); equivalently $a^{p} \equiv a (mod p)$ for all $a$ ^{[Gauss 1801]}. The proof is Lagrange's theorem applied to the cyclic group $(Z / n)^{\times}$ : the order of any element divides the order $φ (n)$ . Fermat 1640 stated only the prime case; Euler 1736 generalised to arbitrary $n$ via the totient. The contrapositive (a composite-detector): if there exists $a$ coprime to $n$ with $a^{n - 1} \neq \equiv 1 (mod n)$ , then $n$ is composite — this is the Fermat primality test, with the Carmichael numbers ( $n$ composite but $a^{n - 1} \equiv 1 (mod n)$ for every $a$ coprime to $n$ ) the well-known false negatives.

Theorem 4 (structure of $(Z / n)^{\times}$ ; Gauss 1801 arts. 49-89). Let $n = 2^{e_{0}} p_{1}^{e_{1}} \dots p_{r}^{e_{r}}$ with $p_{i}$ distinct odd primes. Then $$ (\mathbb{Z}/n\mathbb{Z})^\times ;\cong; (\mathbb{Z}/2^{e_0})^\times \times \prod_{i=1}^r (\mathbb{Z}/p_i^{e_i})^\times, $$ where $(Z / p^{e})^{\times}$ is cyclic of order $p^{e - 1} (p - 1)$ for $p$ odd, $(Z /2)^{\times}$ is the identity group of order $1$ , $(Z /4)^{\times} ≅ Z /2$ , and $(Z / 2^{e})^{\times} ≅ Z /2 \times Z / 2^{e - 2}$ for $e \geq 3$ ^{[Gauss 1801]}. Gauss 1801 Disquisitiones Arithmeticae arts. 49-89 contains the complete structural development, including the existence of primitive roots modulo odd prime powers and the explicit lifting argument $(Z / p^{e})^{\times} = ⟨ g ⟩$ for a primitive root $g$ of $p$ chosen so $g^{p - 1} \neq \equiv 1 (mod p^{2})$ . The Carmichael function $λ (n)$ , the exponent of $(Z / n)^{\times}$ , equals $lcm {orders of the factors}$ ; thus $λ (n) ∣ φ (n)$ with equality iff $(Z / n)^{\times}$ is cyclic, namely when $n \in {1, 2, 4, p^{e}, 2 p^{e}}$ for $p$ an odd prime. Carmichael 1910 Bull. AMS 16 introduced $λ$ in the form usable for cryptographic key-strength estimates ^{[Carmichael 1910]}.

Theorem 5 (Quadratic reciprocity via the CRT decomposition; Gauss 1801 art. 130). For distinct odd primes $p, q$ , the Legendre symbols satisfy $$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}. $$ Gauss 1801 §IV gave eight different proofs over his career; the modern proofs (e.g., via Gauss sums, via the splitting of cyclotomic fields, via the Chebotarev density theorem) all rest on the CRT identification $(Z / pq)^{\times} ≅ (Z / p)^{\times} \times (Z / q)^{\times}$ and the quadratic-residue behaviour in each factor. Hilbert 1897 Bericht über die Theorie der algebraischen Zahlkörper lifted the reciprocity law into a statement about Hilbert symbols and quadratic forms; Artin 1927 Hamburg Abh. 5, 353 stated the general Artin reciprocity law, of which quadratic reciprocity is the $GL_{1}$ specialisation. Quadratic reciprocity is the foundation of the genus theory of quadratic forms and the prototype of class-field theory.

Theorem 6 (CRT-based RSA decryption; Rivest-Shamir-Adleman 1978 + standard speedup). For RSA decryption with modulus $N = pq$ , exponent $d$ , and ciphertext $C$ , the decryption $M = C^{d} mod N$ can be computed approximately 4 times faster by parallel computation modulo $p$ and modulo $q$ followed by CRT recombination. The algorithm: set $d_{p} = d mod (p - 1)$ and $d_{q} = d mod (q - 1)$ (per Fermat's little theorem); compute $M_{p} = C^{d_{p}} mod p$ and $M_{q} = C^{d_{q}} mod q$ in parallel; recombine $M$ via the CRT inverse for the pair $(p, q)$ : $M = M_{p} + p \cdot ((M_{q} - M_{p}) \cdot p^{- 1} mod q)$ , with $p^{- 1}$ the precomputed modular inverse modulo $q$ . Each of $C^{d_{p}} mod p$ and $C^{d_{q}} mod q$ involves operands half the bit-size of $C^{d} mod N$ , so the squaring cost drops by roughly $4 \times$ . PKCS#1 v2.2 (RFC 8017) specifies this CRT-form as the canonical RSA decryption routine; essentially every TLS handshake uses it.

Theorem 7 (Schönhage-Strassen integer multiplication via CRT-NTT; 1971 Computing 7). Two $n$ -bit integers can be multiplied in $O (n lo g n lo g lo g n)$ operations via the number-theoretic transform (NTT) over the ring $Z / (2^{2^{k}} + 1) Z$ with $k = ⌈ lo g_{2} n ⌉$ ^{[Schönhage-Strassen 1971]}. The algorithm: split each operand into chunks, view as polynomial; compute the product modulo $2^{2^{k}} + 1$ via an FFT in the cyclotomic ring $Z [ζ_{2^{k}}] / (ζ_{2^{k}}^{2^{k}} + 1) ≅ Z / (2^{2^{k}} + 1) Z$ ; recover the product via CRT in $Z / (2^{2^{k}} + 1) Z \times Z / 2^{2^{k + 1}} Z$ . The choice of Fermat-prime-like moduli makes the $2^{k}$ -th root of unity an integer power of $2$ , so multiplication by it is a bit-shift. Schönhage-Strassen held the asymptotic record until Furer 2007 (and the recent Harvey-van der Hoeven 2021 Annals of Mathematics 193 at $O (n lo g n)$ ); all are CRT-NTT-based.

Theorem 8 (Shamir-Asmuth-Bloom CRT secret sharing; Shamir 1979, Asmuth-Bloom 1983). A secret $S$ can be split into $n$ shares such that any $k$ shares reconstruct $S$ but any $k - 1$ shares reveal nothing. Shamir 1979 CACM 22 used polynomial interpolation over $F_{p}$ ; the dual CRT-based scheme of Asmuth-Bloom 1983 IEEE Trans. Inform. Theory IT-29 uses pairwise-coprime moduli ^{[Shamir 1979]}. The Asmuth-Bloom construction: choose pairwise-coprime $m_{1} < \dots < m_{n}$ with the product of the smallest $k$ exceeding the product of the largest $k - 1$ times $S$ ; the $i$ -th share is $S mod m_{i}$ ; reconstruction from any $k$ shares uses the multi-modulus CRT. Used in distributed-key generation, threshold cryptography, and the post-quantum protocols of NIST PQC. Both Shamir and CRT sharing are instances of a more general theme: error-correcting codes (Reed-Solomon, Reed-Muller) realised via polynomial CRT in $F_{q} [x]$ .

Synthesis. The Chinese remainder theorem is the foundational reason that the multiplicative structure of $Z$ factors cleanly across distinct primes, and this is exactly the bridge from elementary modular arithmetic to commutative algebra. The central insight is that coprimality of moduli is the operational content of "the corresponding ideals sum to the whole ring" — an ideal-theoretic statement that survives every generalisation from $Z$ to polynomial rings, to number rings, to local-global principles in arithmetic geometry. Putting these together with the Fermat-Euler theorem and the structure theorem for $(Z / n)^{\times}$ , every arithmetic question modulo $n$ decomposes into independent questions modulo each prime power dividing $n$ , computed locally and reassembled by CRT.

The pattern generalises in multiple directions. The localisation $Z_{(p)}$ at a prime $p$ and the $p$ -adic completion $Z_{p}$ are the limits of the CRT factor $Z / p^{k}$ as $k \to \infty$ , identifying the local-global principle of 21.05.01 $p$ -adic numbers with the analytic completion. The Artin map $Frob_{p}$ in class-field theory generalises Dirichlet's character-equidistribution from $(Z / q)^{\times}$ to general Galois groups, with the CRT decomposition becoming the splitting behaviour of $p$ in a number-field extension. The étale fundamental group of $Spec (Z)$ specialises CRT to the profinite completion $Z = \prod_{p} Z_{p}$ , a single object that encodes all arithmetic of $Z$ at once.

The applied consequences are equally pervasive. CRT-based RSA decryption is the canonical speedup in every TLS implementation. The Schönhage-Strassen NTT is the basis of modern arbitrary-precision arithmetic in GMP, Magma, and Mathematica. Reed-Solomon codes — polynomial CRT in $F_{q} [x]$ — protect every CD, DVD, QR code, deep-space transmission, and RAID-6 disk array. Shamir-Asmuth-Bloom secret sharing underpins distributed-key cryptosystems and post-quantum threshold protocols. The bridge is everywhere the same: a question over $Z / N$ decomposes into independent questions over $Z / p_{i}^{e_{i}}$ , computed locally and recombined via CRT — the operational content of "the local-global principle" in its most elementary form.

Full proof set Master

Proposition 1 (CRT for $k$ pairwise-coprime moduli, full statement and proof). Let $n_{1}, \dots, n_{k}$ be pairwise coprime positive integers, $N = n_{1} n_{2} \dots n_{k}$ . The map $$ \Psi : \mathbb{Z}/N\mathbb{Z} ;\longrightarrow; \prod_{i=1}^k \mathbb{Z}/n_i\mathbb{Z}, \qquad [x]N \mapsto ([x]{n_1}, \ldots, [x]_{n_k}), $$ is a ring isomorphism.

Proof. By induction on $k$ . The base case $k = 1$ is direct. For $k = 2$ , this is the Key Theorem. For the inductive step from $k - 1$ to $k$ , set $M = n_{1} n_{2} \dots n_{k - 1}$ . Since each $n_{i}$ is coprime to $n_{k}$ for $i < k$ , the product $M$ is coprime to $n_{k}$ (a Bézout consequence: write $1 = a_{i} n_{i} + b_{i} n_{k}$ for each $i$ , take the product over $i < k$ , expand). Apply the two-modulus CRT to $(M, n_{k})$ : $$ \mathbb{Z}/(M n_k)\mathbb{Z} ;\xrightarrow{\sim}; \mathbb{Z}/M\mathbb{Z} \times \mathbb{Z}/n_k\mathbb{Z}. $$ By the inductive hypothesis applied to $(n_{1}, \dots, n_{k - 1})$ : $$ \mathbb{Z}/M\mathbb{Z} ;\xrightarrow{\sim}; \prod_{i=1}^{k-1} \mathbb{Z}/n_i\mathbb{Z}. $$ Composing the two isomorphisms, $$ \mathbb{Z}/N\mathbb{Z} ;\xrightarrow{\sim}; \prod_{i=1}^k \mathbb{Z}/n_i\mathbb{Z}. \qquad \square $$

Proposition 2 (Explicit CRT solution formula). Given pairwise-coprime $n_{1}, \dots, n_{k}$ and target residues $a_{1}, \dots, a_{k}$ , the unique solution of the system $x \equiv a_{i} (mod n_{i})$ modulo $N = n_{1} \dots n_{k}$ is $$ x ;\equiv; \sum_{i=1}^k a_i N_i u_i \pmod N, \qquad N_i = N/n_i, \qquad u_i \equiv N_i^{-1} \pmod{n_i}. $$

Proof. Each $N_{i} = \prod_{j \neq = i} n_{j}$ is coprime to $n_{i}$ (a product of integers each coprime to $n_{i}$ ). Hence $N_{i}$ has a multiplicative inverse $u_{i}$ modulo $n_{i}$ , computable by extended Euclidean (from 21.01.01).

The product $N_{i} u_{i}$ satisfies $N_{i} u_{i} \equiv 1 (mod n_{i})$ and $N_{i} u_{i} \equiv 0 (mod n_{j})$ for $j \neq = i$ (because $n_{j} ∣ N_{i}$ ). Multiplying by $a_{i}$ and summing: $$ \sum_{i=1}^k a_i N_i u_i ;\equiv; \begin{cases} a_j \cdot 1 + \sum_{i \neq j} a_i \cdot 0 = a_j \pmod{n_j}, & \text{(focusing on the }j\text{-th component)} \end{cases} $$ for each $j$ . So the proposed $x$ satisfies all $k$ congruences. Uniqueness modulo $N$ follows from Proposition 1: the map $Ψ$ is injective, so two solutions agree modulo $N$ . $□$

Proposition 3 (Euler totient via CRT — full computation). For $n = p_{1}^{e_{1}} \dots p_{r}^{e_{r}}$ , $$ \varphi(n) ;=; \prod_{i=1}^r p_i^{e_i - 1}(p_i - 1) ;=; n \prod_{p \mid n}\left(1 - \frac{1}{p}\right). $$

Proof. By Proposition 1, $(Z / n)^{\times} ≅ \prod_{i} (Z / p_{i}^{e_{i}})^{\times}$ as groups. Taking cardinalities, $φ (n) = \prod_{i} φ (p_{i}^{e_{i}})$ .

It remains to compute $φ (p^{e})$ for a prime power. The residues modulo $p^{e}$ are $0, 1, 2, \dots, p^{e} - 1$ ; the non-units are exactly the multiples of $p$ , namely $0, p, 2 p, \dots, (p^{e - 1} - 1) p$ , totalling $p^{e - 1}$ elements. Hence $φ (p^{e}) = p^{e} - p^{e - 1} = p^{e - 1} (p - 1)$ .

Substituting: $$ \varphi(n) = \prod_{i} p_i^{e_i - 1}(p_i - 1) = \prod_i p_i^{e_i} \cdot \prod_i \frac{p_i - 1}{p_i} = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right). \qquad \square $$

Proposition 4 (Fermat-Euler theorem; structural proof). For $g cd (a, n) = 1$ , $a^{φ (n)} \equiv 1 (mod n)$ .

Proof. The residue $[a]_{n}$ lies in the group $(Z / n)^{\times}$ , which has order $φ (n)$ . By Lagrange's theorem (every element of a finite group satisfies $g^{∣ G ∣} = e$ ), $[a]_{n}^{φ (n)} = [1]_{n}$ . Translating: $a^{φ (n)} \equiv 1 (mod n)$ . $□$

The specialisation $n = p$ gives Fermat's little theorem $a^{p - 1} \equiv 1 (mod p)$ for $g cd (a, p) = 1$ . Multiplying both sides by $a$ extends to $a^{p} \equiv a (mod p)$ for every integer $a$ (the case $a \equiv 0 (mod p)$ is direct: both sides are $0$ ).

Connections Master

Divisibility, GCD, and Bézout 21.01.01. Just shipped. Bézout's identity is the load-bearing step in the CRT proof — both the constructive existence (the idempotent decomposition $1 = u n_{2} + v n_{1}$ ) and the uniqueness (the joint kernel $n_{1} ∣ x$ , $n_{2} ∣ x$ implies $n_{1} n_{2} ∣ x$ when $g cd (n_{1}, n_{2}) = 1$ ). The extended Euclidean algorithm of 21.01.01 supplies the modular inverse $u_{i} \equiv N_{i}^{- 1} (mod n_{i})$ needed for the explicit CRT formula of Proposition 2. Without 21.01.01 the present unit's central theorem has no operational construction.
Primes and the fundamental theorem of arithmetic 21.01.02. Just shipped. The fundamental theorem provides the prime-power factorisation $n = p_{1}^{e_{1}} \dots p_{r}^{e_{r}}$ that decomposes $(Z / n)^{\times}$ via CRT into the product of $(Z / p_{i}^{e_{i}})^{\times}$ (Theorem 4 above). Primality is also the dividing line for field structure: $Z / n Z$ is a field if and only if $n$ is prime. The Fermat-Euler theorem (Theorem 3) inherits Fermat's little theorem as the prime case. The chapter-level synthesis of elementary number theory rests on the interplay of 21.01.01 (additive structure), 21.01.02 (multiplicative atoms), and the present unit (the local-global decomposition).
Commutative rings and ideals 01.02.06. Pending. The CRT generalises directly from $Z$ to any commutative ring: for pairwise-coprime ideals $I_{1}, \dots, I_{k}$ (in the sense $I_{i} + I_{j} = R$ ), the canonical map $R \to \prod R / I_{i}$ has kernel $⋂ I_{i} = \prod I_{i}$ and induces $R / ⋂ I_{i} ≅ \prod R / I_{i}$ . The chapter-closing synthesis of commutative algebra in 01.02.06 reframes the present unit's content as the dimension-1 / discrete case of the general decomposition principle that organises localisation, completion, and sheaf cohomology.
Finite fields $F_{q}$ and Frobenius 01.02.18 pending. Pending. The base case is $F_{p} = Z / p Z$ , defined here. The general $F_{q}$ for $q = p^{n}$ is constructed as $F_{p} [x] / (f (x))$ for $f$ irreducible of degree $n$ , an instance of polynomial CRT applied to a single maximal ideal. Polynomial CRT in $F_{p} [x]$ — the analogue of integer CRT for the Euclidean domain $F_{p} [x]$ — generalises in 01.02.18 pending (when shipped) to the Frobenius decomposition of $F_{p} [x] / f$ when $f$ factors. Reed-Solomon codes (Theorem 8 above, ^{[Reed-Solomon 1960]}) are the canonical applied target.
Riemann zeta function and the Euler product 21.03.01. Shipped. The Euler product $ζ (s) = \prod_{p} (1 - p^{- s})^{- 1}$ encodes the Chinese remainder decomposition $Z / n ≅ \prod_{p^{e} ∥ n} Z / p^{e}$ into an analytic statement: the multiplicative function $n \mapsto n^{- s}$ factors as a product over prime powers. The Dirichlet character generalisation in 21.03.02 uses the CRT decomposition of $(Z / q)^{\times}$ to factor $L (s, χ) = \prod_{p} (1 - χ (p) p^{- s})^{- 1}$ . The bridge from elementary CRT to analytic number theory is precisely this: every multiplicative arithmetic function decomposes across primes, with the operational content supplied by the present unit.

Historical & philosophical context Master

The Chinese remainder theorem is the oldest theorem in number theory bearing a non-European name. The originator example appears in Sun Zi c. 4th-5th century CE Sunzi Suanjing ^{[Sun Zi]}: "There are certain things whose number is unknown; counted by threes they leave remainder 2, by fives remainder 3, by sevens remainder 2 — what is their number?" The traditional answer 23 is recovered by what would later be named the CRT. Sun Zi gives only the example and a verification, with no general algorithm. The general procedure for arbitrary pairwise-coprime moduli is due to Qin Jiushao 1247 Mathematical Treatise in Nine Sections (Shushu Jiuzhang) ^{[Qin Jiushao 1247]} under the name Da Yan (大衍, "Great Extension"); the Da Yan procedure is essentially the modern $\sum a_{i} N_{i} u_{i}$ formula of Proposition 2, with each $u_{i}$ computed by what amounts to the extended Euclidean algorithm. The same theorem was independently developed in India by Brahmagupta 628 Brahmasphuṭasiddhānta ^{[Brahmagupta 628]} using the Kuṭṭaka ("pulveriser") algorithm — again a Euclidean-style routine — for the same problem of simultaneous linear congruences.

The modern Western formulation is due to Gauss 1801 Disquisitiones Arithmeticae arts. 1-37 (the congruence notation $a \equiv b (mod n)$ , due to Gauss in this work), arts. 38-44 (the CRT proper for pairwise-coprime moduli, with both two-modulus and multi-modulus forms), and arts. 49-89 (the structure theory of $(Z / n)^{\times}$ , including the existence of primitive roots modulo odd prime powers) ^{[Gauss 1801]}. Gauss does not cite Sun Zi or Qin Jiushao — the Chinese mathematical tradition was unknown in Europe at the time — but the name "Chinese remainder theorem" emerged in 19th-century scholarship after the publication of Wylie 1852 Notes on Chinese arithmetic and the subsequent translation and study of the Shushu Jiuzhang. The name was popularised by Dickson 1919 History of the Theory of Numbers Vol. 1 and is standard in 20th-century textbooks.

The ring-theoretic abstraction took shape in the late 19th and early 20th centuries. Dedekind 1871 (in his supplements to Dirichlet's Vorlesungen über Zahlentheorie) introduced ideals in commutative rings and recognised that the coprime-moduli condition $g cd (n_{1}, n_{2}) = 1$ corresponds to the ideal-theoretic statement $(n_{1}) + (n_{2}) = Z$ . Noether 1921 Math. Ann. 83 abstracted the chain conditions; the general CRT for pairwise-coprime ideals in a commutative ring entered the textbook canon with van der Waerden 1930 Moderne Algebra and remains in the same form in Lang 2002 Algebra Ch. II §2 ^{[Lang 2002]}. The polynomial analogue (CRT in $k [x]$ for coprime polynomial moduli) is essentially Lagrange interpolation 1795 Leçons élémentaires sur les mathématiques, predating the integer formulation by Gauss.

The structure theory of $(Z / n)^{\times}$ — cyclic for $n \in {1, 2, 4, p^{e}, 2 p^{e}}$ with $p$ odd; product of two cyclic groups for $n = 2^{e}$ with $e \geq 3$ ; CRT factorisation otherwise — is essentially complete in Gauss 1801 §III. The Carmichael function $λ (n)$ recording the group exponent rather than the order was introduced by Carmichael 1910 Bull. AMS 16, 232 ^{[Carmichael 1910]} and is fundamental in modern cryptographic key-strength estimates: RSA security depends on $λ (N)$ , not $φ (N)$ . The Carmichael numbers — composite $n$ for which $a^{n - 1} \equiv 1 (mod n)$ for all $a$ coprime to $n$ — were classified by Korselt 1899 Math. Ann. 53 and shown to be infinite by Alford-Granville-Pomerance 1994 Annals 139.

The applied legacy is dominated by cryptography and coding theory. Rivest-Shamir-Adleman 1978 CACM 21, 120 introduced RSA based on the asymmetry between exponentiation and discrete-logarithm computation modulo a large semi-prime $N = pq$ . CRT-based decryption — recommended in PKCS#1 v2.2 (RFC 8017) and implemented in essentially every TLS stack — exploits the factorisation of $Z / N$ as $Z / p \times Z / q$ to gain a $4 \times$ speedup. Reed-Solomon 1960 J. SIAM 8, 300 ^{[Reed-Solomon 1960]} introduced their codes via polynomial CRT in $F_{q} [x]$ ; today they protect every CD, DVD, QR code, deep-space transmission, and RAID-6 disk array. Shamir 1979 CACM 22, 612 ^{[Shamir 1979]} introduced secret sharing via polynomial interpolation; the Asmuth-Bloom 1983 IEEE Trans. Inform. Theory IT-29 dual scheme uses pairwise-coprime moduli and the CRT formula of Proposition 2. Schönhage-Strassen 1971 Computing 7, 281 ^{[Schönhage-Strassen 1971]} introduced the CRT-NTT integer-multiplication algorithm that powered arbitrary-precision arithmetic in GMP and Magma for half a century, with the Harvey-van der Hoeven 2021 Annals 193 improvement to $O (n lo g n)$ closing a 1971 question of Schönhage.

Bibliography Master

@book{SunZiSuanjing,
  author    = {Sun Zi},
  title     = {Sunzi Suanjing},
  editor    = {Lam, Lay Yong and Ang, Tian Se},
  publisher = {World Scientific},
  year      = {2004},
  edition   = {2},
  note      = {Chinese mathematical manuscript, c. 4th-5th century CE. The originator example for the Chinese remainder theorem appears in Volume 3, Problem 26. English translation in Lam-Ang 2004 *Fleeting Footsteps*, 2nd edition.}
}

@book{Brahmagupta628,
  author    = {Brahmagupta},
  title     = {Brahmasphu\d{t}asiddh\={a}nta},
  editor    = {Colebrooke, Henry Thomas},
  publisher = {John Murray},
  year      = {1817},
  note      = {Sanskrit treatise, 628 CE. Chapter 12 (Ku\d{t}\d{t}aka) contains the general algorithm for solving simultaneous linear congruences. English translation in Colebrooke 1817 *Algebra, with Arithmetic and Mensuration, from the Sanscrit of Brahmegupta and Bhascara*.}
}

@book{QinJiushao1247,
  author    = {Qin, Jiushao},
  title     = {Mathematical Treatise in Nine Sections (Shushu Jiuzhang)},
  publisher = {Song Dynasty},
  year      = {1247},
  note      = {Chinese mathematical treatise. Chapter 1 contains the Da Yan (大衍) procedure: the first systematic general-modulus CRT algorithm. English exposition: Libbrecht 1973 *Chinese Mathematics in the Thirteenth Century*, MIT Press.}
}

@book{Gauss1801,
  author    = {Gauss, Carl Friedrich},
  title     = {Disquisitiones Arithmeticae},
  publisher = {Gerhard Fleischer},
  address   = {Leipzig},
  year      = {1801},
  note      = {English translation by Arthur A. Clarke, Yale University Press, 1965. Articles 1-37 introduce congruence notation; articles 38-44 develop the CRT; articles 49-89 give the structure theory of $(\mathbb{Z}/n)^\times$.}
}

@article{Carmichael1910,
  author  = {Carmichael, Robert D.},
  title   = {Note on a new number theory function},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {16},
  pages   = {232--238},
  year    = {1910}
}

@article{ReedSolomon1960,
  author  = {Reed, Irving S. and Solomon, Gustave},
  title   = {Polynomial codes over certain finite fields},
  journal = {Journal of the Society for Industrial and Applied Mathematics},
  volume  = {8},
  pages   = {300--304},
  year    = {1960}
}

@article{SchonhageStrassen1971,
  author  = {Sch\"{o}nhage, Arnold and Strassen, Volker},
  title   = {Schnelle Multiplikation gro{\ss}er Zahlen},
  journal = {Computing},
  volume  = {7},
  pages   = {281--292},
  year    = {1971}
}

@article{Shamir1979,
  author  = {Shamir, Adi},
  title   = {How to share a secret},
  journal = {Communications of the ACM},
  volume  = {22},
  pages   = {612--613},
  year    = {1979}
}

@article{AsmuthBloom1983,
  author  = {Asmuth, Charles A. and Bloom, John},
  title   = {A modular approach to key safeguarding},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-29},
  pages   = {208--210},
  year    = {1983}
}

@article{RivestShamirAdleman1978,
  author  = {Rivest, Ronald L. and Shamir, Adi and Adleman, Leonard},
  title   = {A method for obtaining digital signatures and public-key cryptosystems},
  journal = {Communications of the ACM},
  volume  = {21},
  pages   = {120--126},
  year    = {1978}
}

@book{HardyWright2008,
  author    = {Hardy, G. H. and Wright, E. M.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {6},
  publisher = {Oxford University Press},
  year      = {2008},
  note      = {Revised by D. R. Heath-Brown and J. H. Silverman, foreword by A. Wiles. Chapters V-VI contain the elementary theory of congruences, the CRT, and the structure of $(\mathbb{Z}/n)^\times$.}
}

@book{IrelandRosen1990,
  author    = {Ireland, Kenneth and Rosen, Michael},
  title     = {A Classical Introduction to Modern Number Theory},
  edition   = {2},
  series    = {Graduate Texts in Mathematics},
  volume    = {84},
  publisher = {Springer},
  year      = {1990}
}

@book{Lang2002,
  author    = {Lang, Serge},
  title     = {Algebra},
  edition   = {3},
  series    = {Graduate Texts in Mathematics},
  volume    = {211},
  publisher = {Springer},
  year      = {2002},
  note      = {Chapter II §2 develops the CRT for coprime ideals in a commutative ring.}
}

@book{Apostol1976,
  author    = {Apostol, Tom M.},
  title     = {Introduction to Analytic Number Theory},
  series    = {Undergraduate Texts in Mathematics},
  publisher = {Springer},
  year      = {1976}
}

@book{NivenZuckermanMontgomery1991,
  author    = {Niven, Ivan and Zuckerman, Herbert S. and Montgomery, Hugh L.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {5},
  publisher = {John Wiley},
  year      = {1991}
}

Prerequisites

21.01.01
21.01.02

Tier anchors

beginner: Burton 2010 *Elementary Number Theory* 7e §4 (congruences, clock arithmetic, ISBN check digits); Khan Academy 'Modular arithmetic' module
intermediate: Ireland-Rosen 1990 *A Classical Introduction to Modern Number Theory* (Springer GTM 84, 2e) §3; Apostol 1976 *Introduction to Analytic Number Theory* §5; Niven-Zuckerman-Montgomery 1991 *An Introduction to the Theory of Numbers* 5e §2
master: Sun Zi c. 4th-5th c. CE *Sunzi Suanjing* (originator example); Qin Jiushao 1247 *Mathematical Treatise in Nine Sections* (Da Yan procedure); Gauss 1801 *Disquisitiones Arithmeticae* arts. 1-37, 49-89 (canonical modern formulation); Hardy-Wright 2008 *An Introduction to the Theory of Numbers* 6e §§V-VI; Lang 2002 *Algebra* (Springer GTM 211, 3e) Ch. II §2; Niven-Zuckerman-Montgomery 1991 *An Introduction to the Theory of Numbers* 5e §2; Shamir 1979 *CACM* 22 (secret sharing); Schönhage-Strassen 1971 *Computing* 7 (CRT-based fast integer multiplication)

References

Sun Zi — Sunzi Suanjing (Master Sun's Mathematical Manual) · Chinese manuscript, c. 4th-5th century CE. Volume 3, Problem 26 gives the originator example: 'There are certain things whose number is unknown; counted by threes they leave remainder 2, by fives remainder 3, by sevens remainder 2 — what is their number?' The traditional answer 23 is recovered by what would later be named the Chinese remainder theorem. English translation in Lam-Ang 2004 *Fleeting Footsteps* (World Scientific, 2e).
Brahmagupta — Brahmasphuṭasiddhānta · Sanskrit treatise (628 CE), Chapter 12 (Kuṭṭaka — 'pulveriser' algorithm). Independent of Sun Zi, Brahmagupta gives a general procedure for solving simultaneous linear congruences via what is essentially the extended Euclidean algorithm. English translation Colebrooke 1817 *Algebra, with Arithmetic and Mensuration, from the Sanscrit of Brahmegupta and Bhascara* (London: John Murray).
Qin Jiushao — Mathematical Treatise in Nine Sections (Shushu Jiuzhang) · Chinese mathematical treatise (1247 CE), Chapter 1: the Da Yan (大衍, 'Great Extension') procedure giving the first systematic general-modulus solution to simultaneous congruences for arbitrary pairwise-coprime moduli. The first place the modern CRT algorithm appears in print. English exposition in Libbrecht 1973 *Chinese Mathematics in the Thirteenth Century* (MIT Press).
Gauss, C. F. — Disquisitiones Arithmeticae · Leipzig: Gerhard Fleischer, 1801. Articles 1-37 introduce congruence notation $a \equiv b \pmod n$ and develop the elementary theory; Articles 38-44 cover linear congruences and the CRT for pairwise-coprime moduli; Articles 49-89 give the structure theory of $(\mathbb{Z}/n)^\times$, including primitive roots, the order of the group $\varphi(n)$, and the cyclic-decomposition theorem for $p$ an odd prime. The English translation by Clarke 1965 (Yale UP) is the standard modern reference.
Shamir, A. — How to share a secret · *Communications of the ACM* 22 (1979), 612-613. Shamir's $(k, n)$-threshold secret sharing scheme based on polynomial interpolation over $\mathbb{F}_p$, with the CRT-based Asmuth-Bloom 1983 *IEEE Trans. Inform. Theory* IT-29 variant using pairwise-coprime moduli as the alternative threshold construction.
Schönhage, A. & Strassen, V. — Schnelle Multiplikation großer Zahlen · *Computing* 7 (1971), 281-292. The Schönhage-Strassen integer-multiplication algorithm using number-theoretic transforms in $\mathbb{Z}/(2^{2^k} + 1)\mathbb{Z}$, achieving complexity $O(n \log n \log \log n)$ for $n$-bit operands. The CRT-based pointwise multiplication step is the load-bearing ingredient. Superseded asymptotically by Harvey-van der Hoeven 2021 *Annals of Mathematics* 193 at $O(n \log n)$.
Reed, I. S. & Solomon, G. — Polynomial codes over certain finite fields · *Journal of the Society for Industrial and Applied Mathematics* 8 (1960), 300-304. Reed-Solomon codes as evaluation codes over $\mathbb{F}_q$ realised concretely via CRT: a message polynomial is evaluated at distinct points, and the resulting vector is decoded by polynomial CRT (which is the same theorem applied to coprime ideals $(x - a_i)$ in $\mathbb{F}_q[x]$). Used in CDs, DVDs, QR codes, deep-space communication, and RAID-6 disk arrays.
Hardy, G. H. & Wright, E. M. — An Introduction to the Theory of Numbers · Oxford University Press, 6th edition (2008), revised by D. R. Heath-Brown and J. H. Silverman with a foreword by A. Wiles. §§V-VI (congruences, residue classes, Fermat-Euler theorems, the CRT, structure of $(\mathbb{Z}/n)^\times$).
Ireland, K. & Rosen, M. — A Classical Introduction to Modern Number Theory · Springer Graduate Texts in Mathematics 84, 2nd edition (1990), §3. Congruences in $\mathbb{Z}$ as the prototype of localisation at an ideal; CRT in the general commutative-ring setting; the group $(\mathbb{Z}/n)^\times$ via its CRT decomposition; primitive roots.
Lang, S. — Algebra · Springer Graduate Texts in Mathematics 211, 3rd edition (2002), Ch. II §2. The CRT for coprime ideals in a commutative ring: if $I_1, \ldots, I_k$ are pairwise coprime ideals of $R$ ($I_i + I_j = R$ for $i \neq j$), then $R/(I_1 \cap \cdots \cap I_k) \cong R/I_1 \times \cdots \times R/I_k$ as rings.
Apostol, T. M. — Introduction to Analytic Number Theory · Springer Undergraduate Texts in Mathematics (1976), §5. Arithmetic-function framing of congruences; the Euler totient $\varphi(n)$, its multiplicativity via CRT, the formula $\varphi(n) = n \prod_{p \mid n}(1 - 1/p)$, and the Möbius-inversion derivation. Sets up the Dirichlet-series machinery for analytic number theory.
Niven, I., Zuckerman, H. S. & Montgomery, H. L. — An Introduction to the Theory of Numbers · John Wiley, 5th edition (1991), §2. Standard undergraduate development of congruences, linear congruences, the CRT with explicit Bézout-based algorithm, $(\mathbb{Z}/n)^\times$ structure, primitive roots, Wilson's theorem, and the discrete logarithm.
Carmichael, R. D. — Note on a new number theory function · *Bulletin of the American Mathematical Society* 16 (1910), 232-238. Introduces the Carmichael function $\lambda(n)$ as the exponent of $(\mathbb{Z}/n)^\times$ — the least positive integer with $a^{\lambda(n)} \equiv 1 \pmod n$ for every $a$ coprime to $n$. Divides $\varphi(n)$ with equality iff $(\mathbb{Z}/n)^\times$ is cyclic.

Estimated time

beginner: 18m
intermediate: 40m
master: 80m