The Chinese remainder theorem

Theorem

The Chinese remainder theorem

T-032Home MU-105Threads structure · number

Statement

Let \( k \ge 1 \) and let \( n_1, n_2, \dots, n_k \) be integers with \( n_i \ge 1 \) for every \( i \), which are pairwise coprime: \( \gcd(n_i, n_j) = 1 \) for all \( i \ne j \). Set \( N = n_1 n_2 \cdots n_k \). Then for every choice of integers \( a_1, a_2, \dots, a_k \), the system of simultaneous congruences \[ x \equiv a_1 \pmod{n_1}, \quad x \equiv a_2 \pmod{n_2}, \quad \dots, \quad x \equiv a_k \pmod{n_k} \] has a solution \( x \in \mathbb{Z} \), and any two solutions are congruent modulo \( N \). Equivalently: there is exactly one residue class modulo \( N \) satisfying all \( k \) congruences, i.e. exactly one \( x \) with \( 0 \le x \lt N \). In ring-theoretic form, the map \[ \varphi : \mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}, \qquad [x]_N \mapsto \left( [x]_{n_1}, \dots, [x]_{n_k} \right) \] is a ring isomorphism.

Why it matters

The theorem says that arithmetic modulo a composite number splits into independent arithmetics modulo its pairwise coprime factors — in particular modulo its prime powers, since \( N = p_1^{e_1} \cdots p_r^{e_r} \) has pairwise coprime prime-power factors. A question about \( \mathbb{Z}/N\mathbb{Z} \) (solving equations, counting roots, computing powers) can be answered one prime power at a time and the answers reassembled, with no information lost. This "local-to-global" template recurs throughout algebra and number theory.

Practically, it underlies the multiplicativity of Euler's totient \( \phi \), the counting of solutions of polynomial congruences, fast modular arithmetic (RSA implementations routinely compute modulo \( p \) and \( q \) separately), secret sharing, and coding theory. Structurally, it is the prototype of the isomorphism \( R/(IJ) \cong R/I \times R/J \) for comaximal ideals in any commutative ring.

Hypotheses

Hypothesis.Pairwise coprimality \( \gcd(n_i,n_j)=1 \) for \( i \ne j \): drop it and existence fails — \( x \equiv 0 \pmod 2 \), \( x \equiv 1 \pmod 4 \) has no solution, since any \( x \equiv 1 \pmod 4 \) is odd. Uniqueness modulo the product also fails — \( x \equiv 2 \pmod 4 \), \( x \equiv 2 \pmod 6 \) is satisfied by both \( 2 \) and \( 14 \), which are distinct modulo \( 24 \).

Hypothesis.Coprimality must hold pairwise, not merely for the whole set. With \( n_1=6,\ n_2=10,\ n_3=15 \) we have \( \gcd(6,10,15)=1 \), yet \( x \equiv 0 \pmod 6 \), \( x \equiv 1 \pmod{10} \) is already unsolvable: the first forces \( x \) even, the second forces \( x \) odd. The obstruction is \( \gcd(6,10) = 2 \gt 1 \).

Hypothesis.Positive integer moduli \( n_i \ge 1 \): a congruence modulo \( 0 \) means equality in \( \mathbb{Z} \), and the statement "unique modulo \( N \)" degenerates. (Modulus \( 1 \) is harmless: \( x \equiv a \pmod 1 \) holds for all \( x \), and the factor \( \mathbb{Z}/1\mathbb{Z} \) is the zero ring.)

Hypothesis.Finitely many congruences. For infinitely many pairwise coprime moduli existence fails: enumerate the integers as \( z_1, z_2, z_3, \dots \) and let \( p_i \) be the \( i \)-th prime; the infinite system \( x \equiv z_i + 1 \pmod{p_i} \) has every finite subsystem solvable (by the theorem), yet no integer solves them all — the candidate \( z_i \) is excluded by the \( i \)-th congruence, and every integer is some \( z_i \). The correct infinite analogue lives in the profinite completion \( \widehat{\mathbb{Z}} = \varprojlim \mathbb{Z}/n\mathbb{Z} \cong \prod_p \mathbb{Z}_p \), not in \( \mathbb{Z} \).

Proof

Write \( N = n_1 n_2 \cdots n_k \) and for each \( i \) set \( N_i = N/n_i = \prod_{j \ne i} n_j \). We prove existence constructively, then uniqueness, then the ring-isomorphism form.

\[ \text{Lemma A: if } \gcd(a,c) = 1 \text{ and } \gcd(b,c) = 1, \text{ then } \gcd(ab,c) = 1. \]

By Bézout's lemma there are integers \( u,v,s,t \) with \( au + cv = 1 \) and \( bs + ct = 1 \). Multiplying: \( 1 = (au+cv)(bs+ct) = ab(us) + c(aut + vbs + cvt) \), an integer combination of \( ab \) and \( c \) equal to \( 1 \), so any common divisor of \( ab \) and \( c \) divides \( 1 \). B

\[ \gcd(N_i, n_i) = 1 \quad \text{for each } i. \]

\( N_i = \prod_{j \ne i} n_j \) and \( \gcd(n_j, n_i) = 1 \) for every \( j \ne i \) by the pairwise-coprimality hypothesis. Apply Lemma A repeatedly (formally: induction on the number of factors, the empty product \( 1 \) being coprime to everything). C

\[ \exists\, M_i, y_i \in \mathbb{Z}: \quad N_i M_i + n_i y_i = 1, \quad \text{hence } N_i M_i \equiv 1 \pmod{n_i}. \]

Bézout's lemma applied to the coprime pair \( (N_i, n_i) \) from Step 2. Concretely \( M_i \) is computed by the extended Euclidean algorithm; it is an inverse of \( N_i \) modulo \( n_i \). A

\[ x_0 := \sum_{j=1}^{k} a_j N_j M_j \quad \text{satisfies} \quad x_0 \equiv a_i \pmod{n_i} \ \text{ for every } i. \]

Fix \( i \). For \( j \ne i \), the product \( N_j = \prod_{l \ne j} n_l \) contains the factor \( n_i \), so \( n_i \mid N_j \) and the term \( a_j N_j M_j \equiv 0 \pmod{n_i} \). The single surviving term gives \( x_0 \equiv a_i N_i M_i \equiv a_i \cdot 1 = a_i \pmod{n_i} \) by Step 3. This proves existence. B

\[ \text{Lemma B: if } \gcd(m,n)=1,\ m \mid z,\ n \mid z, \text{ then } mn \mid z. \]

Write \( z = ms \). Then \( n \mid ms \) with \( \gcd(n,m) = 1 \), so by the generalized Euclid lemma (Gauss's lemma: \( n \mid ms \) and \( \gcd(n,m)=1 \) imply \( n \mid s \), proved from Bézout by writing \( 1 = mu + nv \), so \( s = msu + nsv \), and \( n \) divides both terms) we get \( n \mid s \), say \( s = nt \); then \( z = mnt \). C

\[ n_1, \dots, n_k \text{ pairwise coprime, } n_i \mid z \ \forall i \ \Longrightarrow\ N \mid z. \]

Induction on \( k \). Base \( k=1 \) is trivial. Inductive step: \( n_1 \cdots n_{k-1} \mid z \) by the inductive hypothesis, and \( \gcd(n_1 \cdots n_{k-1}, n_k) = 1 \) by Step 2's argument (Lemma A iterated); apply Lemma B to the pair \( (n_1 \cdots n_{k-1},\, n_k) \). C

\[ x \equiv a_i \equiv y \pmod{n_i} \ \forall i \ \Longrightarrow\ x \equiv y \pmod N. \]

If \( x \) and \( y \) both solve the system then \( n_i \mid x - y \) for every \( i \); Step 6 applied to \( z = x-y \) gives \( N \mid x-y \). Conversely any \( y \equiv x_0 \pmod N \) solves the system, since \( n_i \mid N \). So the solution set is exactly the residue class \( x_0 + N\mathbb{Z} \): uniqueness modulo \( N \). A

\[ \varphi : \mathbb{Z}/N\mathbb{Z} \to \prod_{i=1}^k \mathbb{Z}/n_i\mathbb{Z}, \qquad [x]_N \mapsto ([x]_{n_1}, \dots, [x]_{n_k}) \text{ is a ring isomorphism.} \]

Well-defined: \( x \equiv x' \pmod N \) implies \( x \equiv x' \pmod{n_i} \) because \( n_i \mid N \). Ring homomorphism: each coordinate is the canonical reduction map \( \mathbb{Z}/N\mathbb{Z} \to \mathbb{Z}/n_i\mathbb{Z} \), which preserves \( +, \times, 1 \). Injective: \( \varphi([x]_N) = 0 \) means \( n_i \mid x \) for all \( i \), so \( N \mid x \) by Step 6, i.e. \( [x]_N = 0 \); the kernel is trivial. Surjective: either directly by Step 4 (existence hits every target tuple), or by counting — both sides are finite sets of cardinality \( N = \prod n_i \), and an injection between finite sets of equal size is a bijection. B

Conclusion: the system has the solution \( x_0 = \sum_j a_j N_j M_j \), its full solution set is \( x_0 + N\mathbb{Z} \), and \( \mathbb{Z}/N\mathbb{Z} \cong \prod_i \mathbb{Z}/n_i\mathbb{Z} \) as rings. \( \blacksquare \)

Steps 4, 7 and 8 assembled; every auxiliary fact used (Bézout, Lemma A, Gauss's lemma, Lemma B) was proved or named above. A

Result

\[ \gcd(n_i,n_j)=1 \ (i \ne j) \ \Longrightarrow\ \mathbb{Z}/n_1\cdots n_k\mathbb{Z} \ \cong\ \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}, \]\[ \text{so } x \equiv a_i \ (\mathrm{mod}\ n_i),\ 1 \le i \le k, \text{ has exactly one solution modulo } N = n_1 \cdots n_k. \]

Reading. Prescribing a remainder for each of several pairwise coprime moduli is never contradictory and never ambiguous: there is always exactly one answer among \( 0, 1, \dots, N-1 \), and it can be written down explicitly as \( \sum_i a_i N_i M_i \) with \( N_i = N/n_i \) and \( M_i \equiv N_i^{-1} \pmod{n_i} \). Knowing a number modulo each \( n_i \) is exactly the same information as knowing it modulo \( N \).

Scope. Applies to any finite family of pairwise coprime moduli \( n_i \ge 1 \) and arbitrary integer targets \( a_i \). If the moduli are not pairwise coprime, the system is solvable if and only if \( a_i \equiv a_j \pmod{\gcd(n_i,n_j)} \) for all pairs, and then the solution is unique modulo \( \mathrm{lcm}(n_1,\dots,n_k) \), not modulo the product. The isomorphism generalizes verbatim to \( R/(I_1 \cdots I_k) \cong \prod R/I_i \) for pairwise comaximal ideals \( I_i + I_j = R \) in a commutative ring with \( 1 \).

Corollaries & converses

Multiplicativity of Euler's totient. A pair \( ([x]_m,[x]_n) \) is a unit of the product ring iff each coordinate is a unit, so the isomorphism restricts to a group isomorphism \( (\mathbb{Z}/mn\mathbb{Z})^{\times} \cong (\mathbb{Z}/m\mathbb{Z})^{\times} \times (\mathbb{Z}/n\mathbb{Z})^{\times} \) when \( \gcd(m,n)=1 \); counting gives \( \phi(mn) = \phi(m)\phi(n) \).
Root counting is multiplicative. For a polynomial \( f \in \mathbb{Z}[X] \), the number of roots of \( f \) modulo \( N = \prod p_i^{e_i} \) equals \( \prod_i \#\{ \text{roots of } f \bmod p_i^{e_i} \} \). E.g. \( x^2 \equiv 1 \pmod{105} \) has \( 2 \cdot 2 \cdot 2 = 8 \) solutions.
Structure of \( \mathbb{Z}/N\mathbb{Z} \). Every finite cyclic group decomposes as a product of its Sylow (prime-power) parts; CRT is exactly this statement for \( \mathbb{Z}/N\mathbb{Z} \), with the ring structure carried along.
Converse holds. If for moduli \( m, n \ge 1 \) the system \( x \equiv a \ (\mathrm{mod}\ m) \), \( x \equiv b \ (\mathrm{mod}\ n) \) is solvable for every pair \( (a,b) \), then \( \gcd(m,n) = 1 \). Proof: take \( a = 0,\ b = 1 \) and let \( d = \gcd(m,n) \); a solution \( x \) has \( d \mid x \) and \( d \mid x - 1 \), so \( d \mid 1 \).
Non-coprime case (generalized CRT). \( x \equiv a \ (\mathrm{mod}\ m) \), \( x \equiv b \ (\mathrm{mod}\ n) \) is solvable iff \( \gcd(m,n) \mid a - b \), and then the solution is unique modulo \( \mathrm{lcm}(m,n) \) (Problem 5). So uniqueness-modulo-the-product genuinely characterizes coprimality: \( \mathrm{lcm}(m,n) = mn \) iff \( \gcd(m,n)=1 \).

Fails without

Existence fails without pairwise coprimality. \( x \equiv 0 \pmod 2 \), \( x \equiv 1 \pmod 4 \): any solution of the second congruence is odd, contradicting the first. Here \( \gcd(2,4) = 2 \) and \( 2 \nmid 0 - 1 \), violating the compatibility condition of the generalized CRT.
Uniqueness modulo the product fails without coprimality. \( x \equiv 2 \pmod 4 \), \( x \equiv 2 \pmod 6 \) is consistent, but its solutions are \( x \equiv 2 \pmod{12} \) — the classes \( 2 \) and \( 14 \) modulo \( 24 = 4 \cdot 6 \) both work. The correct uniqueness modulus is \( \mathrm{lcm}(4,6) = 12 \), not \( 24 \).
Setwise coprimality is not enough. \( \gcd(6,10,15) = 1 \), yet \( x \equiv 0 \pmod 6 \), \( x \equiv 1 \pmod{10} \), \( x \equiv 0 \pmod{15} \) is unsolvable (parity clash between the first two congruences). The hypothesis must be checked for every pair.
The ring map exists but is not bijective without coprimality. \( \mathbb{Z}/4\mathbb{Z} \not\cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z} \): the left side has an element of additive order \( 4 \), the right side does not (every element satisfies \( x + x = 0 \)). Both have four elements, so the reduction map \( \mathbb{Z}/4\mathbb{Z} \to \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z} \) fails to be injective (indeed \( [0] \) and \( [2] \) have the same image).

Common errors

The "overall gcd" error. Checking \( \gcd(n_1, \dots, n_k) = 1 \) instead of pairwise coprimality. The moduli \( 6, 10, 15 \) pass the first test and fail the theorem.
Inverting modulo the wrong modulus. In the formula \( x_0 = \sum a_i N_i M_i \), the factor \( M_i \) must be the inverse of \( N_i \) modulo \( n_i \) — the small modulus — not modulo \( N \). (Indeed \( N_i \) is not even invertible modulo \( N \) when \( k \ge 2 \), since \( \gcd(N_i, N) = N_i \gt 1 \).)
Dropping the inverse factor entirely. Writing \( x_0 = \sum a_i N_i \). This satisfies \( x_0 \equiv a_i N_i \pmod{n_i} \), which is not \( a_i \) unless \( N_i \equiv 1 \pmod{n_i} \) by luck.
Claiming a unique integer solution. The solution is a unique residue class: infinitely many integers \( x_0 + N t \) all work. "The" solution means the unique representative in \( \{0, \dots, N-1\} \) only by convention.
Wrong uniqueness modulus in the non-coprime case. After correctly solving a consistent non-coprime system, asserting uniqueness modulo \( \prod n_i \) rather than modulo \( \mathrm{lcm}(n_1,\dots,n_k) \).
Exponent confusion in applications. When computing \( a^m \bmod n_i \) in each CRT branch, reducing the exponent \( m \) modulo \( n_i \) instead of modulo the order of \( a \) (or \( \phi(n_i) \) via Euler's theorem, valid when \( \gcd(a,n_i)=1 \)).

Discussion

The problem is ancient. The Sunzi Suanjing (China, c. 3rd–5th century CE) poses: "There are certain things whose number is unknown; counted by threes they leave two, by fives three, by sevens two — how many are there?" (our Worked Example 1, answer \( 23 \)). A general algorithm, the dayan ("great extension") rule, was given by Qin Jiushao in his Shushu Jiuzhang (1247), centuries before Euler and Gauss treated the problem systematically in Europe; Gauss's Disquisitiones Arithmeticae (1801) contains the modern congruence formulation. The name "Chinese remainder theorem" honours this lineage.

The right way to remember the theorem is as a statement about information: a residue modulo \( N \) is exactly the list of its residues modulo the prime-power factors of \( N \) — nothing more, nothing less. Injectivity of \( \varphi \) says the list determines the number mod \( N \); surjectivity says every list occurs. This is why one can, for instance, find the last two digits of \( 3^{100} \) by working modulo \( 4 \) and \( 25 \) separately, or why RSA decryption is routinely performed modulo \( p \) and \( q \) and recombined — a fourfold speedup, since the cost of modular exponentiation grows roughly cubically in the bit-length of the modulus.

Structurally, CRT is the first instance of a local-to-global principle: questions over \( \mathbb{Z}/N\mathbb{Z} \) localize at each prime power. Its natural continuations are Hensel's lemma (lifting solutions from \( \mathbb{Z}/p\mathbb{Z} \) up the tower \( \mathbb{Z}/p^e\mathbb{Z} \), i.e. handling the prime-power factors that CRT cannot split further) and, at the far end, the Hasse principle in Diophantine geometry. CRT also drives Lagrange interpolation: replacing \( \mathbb{Z} \) by the polynomial ring \( F[X] \) over a field, the pairwise coprime moduli \( X - c_1, \dots, X - c_k \) give \( F[X]/\prod(X-c_i) \cong F^k \), and "solve the congruences \( f \equiv y_i \pmod{X - c_i} \)" is precisely "find a polynomial with \( f(c_i) = y_i \)"; the idempotent elements \( N_i M_i \) become the Lagrange basis polynomials.

In full generality, let \( R \) be a commutative ring with identity and \( I_1, \dots, I_k \) ideals that are pairwise comaximal: \( I_i + I_j = R \) for \( i \ne j \). Then \( I_1 \cap \cdots \cap I_k = I_1 I_2 \cdots I_k \) and the canonical map \( R/\bigcap I_i \to \prod R/I_i \) is a ring isomorphism; the proof is the same idempotent construction as Steps 3–4, with Bézout's identity replaced by choosing \( e_i \in \bigcap_{j\ne i} I_j \) with \( e_i \equiv 1 \bmod I_i \). Taking \( R = \mathbb{Z} \), \( I_i = n_i\mathbb{Z} \) recovers the classical theorem, since \( n\mathbb{Z} + m\mathbb{Z} = \gcd(m,n)\mathbb{Z} \). The inverse limit of the system \( \mathbb{Z}/n\mathbb{Z} \) over all \( n \) (ordered by divisibility) is the profinite completion \( \widehat{\mathbb{Z}} \cong \prod_p \mathbb{Z}_p \) — an isomorphism that is itself CRT pushed to the limit, and the ambient setting for the infinite systems of congruences excluded by the finiteness hypothesis.

Common misconceptions. CRT does not say that every system of congruences is solvable — compatibility is automatic only for pairwise coprime moduli. It does not produce the smallest solution directly: the constructive formula usually outputs a large representative that must be reduced modulo \( N \). And the isomorphism \( \mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} \) is emphatically false without coprimality, even when the two sides have equal cardinality (\( m = n = 2 \) above).

Worked examples

Example 1 (the Sunzi problem). Solve \( x \equiv 2 \pmod 3 \), \( x \equiv 3 \pmod 5 \), \( x \equiv 2 \pmod 7 \).

\[ \gcd(3,5) = \gcd(3,7) = \gcd(5,7) = 1, \qquad N = 3 \cdot 5 \cdot 7 = 105. \]

Verify the pairwise-coprimality hypothesis; the theorem now guarantees a unique solution modulo \( 105 \). A

\[ N_1 = 35,\ N_2 = 21,\ N_3 = 15; \qquad 35 \equiv 2 \ (3),\quad 21 \equiv 1 \ (5),\quad 15 \equiv 1 \ (7). \]

Compute each \( N_i = N/n_i \) and reduce it modulo its own \( n_i \), preparing to invert. A

\[ M_1 = 2 \ (\text{since } 2 \cdot 2 = 4 \equiv 1 \bmod 3), \qquad M_2 = 1, \qquad M_3 = 1. \]

Inverses of \( N_i \) modulo \( n_i \), from Step 3 of the proof (extended Euclid; here small enough to spot by inspection). B

\[ x_0 = a_1 N_1 M_1 + a_2 N_2 M_2 + a_3 N_3 M_3 = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233. \]

The explicit solution formula from Step 4 of the proof. A

\[ 233 = 2 \cdot 105 + 23 \equiv 23 \pmod{105}; \qquad 23 = 7\cdot3 + 2,\ 23 = 4\cdot5+3,\ 23 = 3\cdot7+2. \ \checkmark \]

Reduce to the canonical representative and check all three congruences directly. A

\[ x \equiv 23 \pmod{105}. \]

Reading. The unique residue class solving Sunzi's puzzle; the smallest positive answer is \( 23 \).

Scope. All integer solutions are \( 23 + 105t \), \( t \in \mathbb{Z} \).

Example 2 (fast modular exponentiation). Compute \( 3^{100} \bmod 77 \) by splitting \( 77 = 7 \cdot 11 \).

\[ \gcd(7,11) = 1, \quad 77 = 7 \cdot 11: \text{ it suffices to find } 3^{100} \bmod 7 \text{ and } \bmod 11, \text{ then recombine.} \]

CRT in the "information" direction: a residue mod \( 77 \) is determined by its pair of residues mod \( 7 \) and mod \( 11 \) (injectivity of \( \varphi \)). B

\[ 3^{6} \equiv 1 \pmod 7 \ \Rightarrow\ 3^{100} = 3^{6 \cdot 16 + 4} \equiv 3^4 = 81 = 77 + 4 \equiv 4 \pmod 7. \]

Fermat's little theorem with the prime \( 7 \) and \( 7 \nmid 3 \); reduce the exponent modulo \( 6 \), not modulo \( 7 \). B

\[ 3^5 = 243 = 22 \cdot 11 + 1 \equiv 1 \pmod{11} \ \Rightarrow\ 3^{100} = (3^5)^{20} \equiv 1 \pmod{11}. \]

The multiplicative order of \( 3 \) modulo \( 11 \) is \( 5 \) (a divisor of \( \phi(11) = 10 \), as Lagrange's theorem requires); using the exact order shortens the computation. A

\[ \text{Solve } x \equiv 4 \ (7),\ x \equiv 1 \ (11): \quad N_1 = 11 \equiv 4\ (7),\ M_1 = 2\ (4 \cdot 2 = 8 \equiv 1);\quad N_2 = 7,\ M_2 = 8\ (7 \cdot 8 = 56 \equiv 1 \bmod 11). \]

Set up the CRT reconstruction data: invert each \( N_i \) modulo \( n_i \). A

\[ x_0 = 4 \cdot 11 \cdot 2 + 1 \cdot 7 \cdot 8 = 88 + 56 = 144 \equiv 144 - 77 = 67 \pmod{77}. \quad \text{Check: } 67 = 9\cdot7+4,\ 67 = 6\cdot11+1. \ \checkmark \]

Solution formula, then reduction modulo \( 77 \) and a direct verification of both congruences. A

\[ 3^{100} \equiv 67 \pmod{77}. \]

Reading. Two small exponentiations (mod \( 7 \), mod \( 11 \)) plus one CRT recombination replace a single large one mod \( 77 \) — the same trick RSA implementations use with \( n = pq \).

Scope. Valid because \( 7 \) and \( 11 \) are coprime; the branch computations used Fermat's little theorem, which needs \( \gcd(3, 7) = \gcd(3, 11) = 1 \).

Problems

Solve \( x \equiv 1 \pmod 4 \), \( x \equiv 2 \pmod 9 \), giving all integer solutions.
Solution

\( \gcd(4,9) = 1 \), \( N = 36 \). \( N_1 = 9 \equiv 1 \pmod 4 \), so \( M_1 = 1 \). \( N_2 = 4 \); we need \( 4 M_2 \equiv 1 \pmod 9 \), and \( 4 \cdot 7 = 28 = 27 + 1 \equiv 1 \), so \( M_2 = 7 \). Then \[ x_0 = 1 \cdot 9 \cdot 1 + 2 \cdot 4 \cdot 7 = 9 + 56 = 65 \equiv 29 \pmod{36}. \] Check: \( 29 = 7 \cdot 4 + 1 \) and \( 29 = 3 \cdot 9 + 2 \). All solutions: \( x = 29 + 36t \), \( t \in \mathbb{Z} \).
Find the smallest positive integer that leaves remainder \( 2 \) on division by \( 3 \), remainder \( 3 \) on division by \( 4 \), and remainder \( 4 \) on division by \( 5 \).
Solution

Each condition says \( x \equiv -1 \) modulo the respective modulus: \( 2 \equiv -1 \ (3) \), \( 3 \equiv -1 \ (4) \), \( 4 \equiv -1 \ (5) \). Since \( x = -1 \) solves all three simultaneously and \( 3, 4, 5 \) are pairwise coprime, CRT's uniqueness clause says the full solution set is \( x \equiv -1 \pmod{60} \). The smallest positive solution is \( 60 - 1 = 59 \). (Check: \( 59 = 19\cdot3+2 = 14\cdot4+3 = 11\cdot5+4 \).) Note how spotting the common shift \( -1 \) avoided the general formula entirely — uniqueness is what licenses the shortcut.
Using the ring isomorphism form of CRT, prove that Euler's totient is multiplicative: \( \phi(mn) = \phi(m)\phi(n) \) whenever \( \gcd(m,n) = 1 \).
Solution

Let \( \varphi : \mathbb{Z}/mn\mathbb{Z} \to \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z} \) be the CRT ring isomorphism. A ring isomorphism maps units to units bijectively: \( u \) is a unit iff there is \( v \) with \( uv = 1 \), and applying \( \varphi \) or \( \varphi^{-1} \) preserves such equations. In a product ring, \( (a,b) \) is a unit iff \( a \) and \( b \) are both units (invert coordinatewise; conversely a coordinate of an invertible pair is invertible with inverse the coordinate of the inverse). Hence \[ (\mathbb{Z}/mn\mathbb{Z})^{\times} \cong (\mathbb{Z}/m\mathbb{Z})^{\times} \times (\mathbb{Z}/n\mathbb{Z})^{\times} \] as groups. Taking cardinalities and using \( \phi(r) = \#(\mathbb{Z}/r\mathbb{Z})^{\times} \) (a residue \( [a]_r \) is a unit iff \( \gcd(a,r) = 1 \), by Bézout) gives \( \phi(mn) = \phi(m)\,\phi(n) \).
Find all solutions of \( x^2 \equiv 1 \pmod{91} \).
Solution

\( 91 = 7 \cdot 13 \) with \( \gcd(7,13)=1 \), so by CRT, \( x^2 \equiv 1 \ (91) \) iff \( x^2 \equiv 1 \ (7) \) and \( x^2 \equiv 1 \ (13) \). Modulo a prime \( p \), \( x^2 \equiv 1 \) means \( p \mid (x-1)(x+1) \), so by Euclid's lemma \( x \equiv \pm 1 \pmod p \): exactly two square roots of \( 1 \) for \( p \gt 2 \). This yields \( 2 \times 2 = 4 \) sign patterns; solve each pair:

\( (+1,+1) \): \( x \equiv 1 \pmod{91} \). \( (-1,-1) \): \( x \equiv -1 \equiv 90 \pmod{91} \).

\( (+1,-1) \): \( x \equiv 1 \ (7),\ x \equiv 12 \ (13) \). With \( N_1 = 13 \equiv 6 \ (7) \), \( 6 \cdot 6 = 36 \equiv 1 \ (7) \) so \( M_1 = 6 \); \( N_2 = 7 \), \( 7 \cdot 2 = 14 \equiv 1 \ (13) \) so \( M_2 = 2 \). Then \( x_0 = 1 \cdot 13 \cdot 6 + 12 \cdot 7 \cdot 2 = 78 + 168 = 246 \equiv 246 - 2\cdot91 = 64 \pmod{91} \). Check: \( 64 = 9\cdot7+1 \), \( 64 = 4\cdot13+12 \).

\( (-1,+1) \): the negative of the previous class, \( x \equiv -64 \equiv 27 \pmod{91} \). Check: \( 27 = 3\cdot7+6 \equiv -1 \ (7) \), \( 27 = 2\cdot13+1 \equiv 1 \ (13) \).

Solutions: \( x \equiv 1,\ 27,\ 64,\ 90 \pmod{91} \). (Four square roots of unity — impossible modulo a prime, and exactly the multiplicativity of root counts predicted by CRT.)
(Generalized CRT.) Let \( m, n \ge 1 \) and \( d = \gcd(m,n) \). Prove that the system \( x \equiv a \pmod m \), \( x \equiv b \pmod n \) has a solution if and only if \( d \mid a - b \), and that when it does, the solution is unique modulo \( \mathrm{lcm}(m,n) \). Deduce the converse statement: if the system is solvable for every pair \( (a,b) \), then \( \gcd(m,n) = 1 \).
Solution

Necessity. If \( x \) solves both, then \( d \mid m \mid x - a \) and \( d \mid n \mid x - b \), so \( d \mid (x-b) - (x-a) = a - b \).

Sufficiency. Suppose \( d \mid a - b \). Every solution of the first congruence has the form \( x = a + mt \), \( t \in \mathbb{Z} \); it solves the second iff \( mt \equiv b - a \pmod n \). This is a linear congruence in \( t \); by the standard solvability criterion (itself a consequence of Bézout: \( m t \equiv c \ (\mathrm{mod}\ n) \) is solvable iff \( \gcd(m,n) \mid c \), since the set \( \{ mt + nu \} \) is exactly \( d\mathbb{Z} \)), it is solvable precisely because \( d \mid b - a \). So a solution \( x \) exists.

Uniqueness modulo the lcm. If \( x, y \) both solve the system, then \( m \mid x - y \) and \( n \mid x - y \), so \( x - y \) is a common multiple of \( m \) and \( n \), hence \( \mathrm{lcm}(m,n) \mid x - y \) (the lcm divides every common multiple: divide a common multiple \( z \) by \( L = \mathrm{lcm}(m,n) \) with remainder, \( z = qL + r \), \( 0 \le r \lt L \); then \( r \) is itself a common multiple, forcing \( r = 0 \) by minimality of \( L \)). Conversely \( x + L\mathbb{Z} \) all solve it, since \( m \mid L \) and \( n \mid L \). So the solution set is one class modulo \( L \).

Converse. If the system is solvable for all \( (a,b) \), take \( a = 0 \), \( b = 1 \): solvability forces \( d \mid 0 - 1 = -1 \), so \( d = 1 \). Together with the classical theorem this shows pairwise coprimality is exactly the condition making all target tuples achievable — and since \( mn = d \cdot \mathrm{lcm}(m,n) \), it is also exactly the condition under which "unique mod \( \mathrm{lcm} \)" becomes "unique mod the product".