The Chinese remainder theorem
A puzzle from the 3rd-century Chinese text Sunzi Suanjing: there are some objects. Counted in threes, 2 are left over; in fives, 3 are left over; in sevens, 2 are left over. How many objects are there? The answer is 23, and the method behind it splits a ring into simpler pieces.
In Unit 5 we saw that \(\mathbb{Z}/6 \cong \mathbb{Z}/2 \times \mathbb{Z}/3\). Here's the same idea for 12. Put each \(k\) in the grid cell (\(k \bmod 3\), \(k \bmod 4\)):
Theorem: the Chinese remainder theorem
If \(m\) and \(n\) share no common factor, then \(\mathbb{Z}/mn \cong \mathbb{Z}/m \times \mathbb{Z}/n\). More generally, if ideals \(I, J\) of a ring \(R\) satisfy \(I + J = R\), then
\[ R/(I \cap J) \;\cong\; R/I \times R/J. \]Show proof
Map \(r \mapsto (r + I,\ r + J)\). Its kernel is \(I \cap J\), so by the first isomorphism theorem it's enough to show it's onto. Since \(I + J = R\), write \(1 = e + f\) with \(e \in I\), \(f \in J\). Then \(f \equiv 1\) mod \(I\) and \(f \equiv 0\) mod \(J\), while \(e\) does the opposite. To hit \((a + I, b + J)\), take \(r = af + be\). ∎
For \(\mathbb{Z}\): if \(\gcd(m, n) = 1\), Bézout gives \(1 = um + vn\), which is exactly the \(1 = e + f\) of the proof. The elements \(e, f\) are like switches that turn one coordinate on and the other off. For Sunzi's puzzle, apply the theorem twice: modulo \(3 \cdot 5 \cdot 7 = 105\), the conditions pin down a unique answer, \(23\).
The theorem reveals structure. A ring like \(\mathbb{Z}/12\) is really two independent rings side by side. For example, a unit of \(\mathbb{Z}/mn\) is a pair of units, so \(\varphi(mn) = \varphi(m)\varphi(n)\), and \(\varphi(55) = \varphi(5)\varphi(11) = 40\) in the RSA example of Unit 2. The polynomial version, with \(I = (x - a)\) and \(J = (x - b)\), is interpolation: a polynomial is determined mod \((x - a)(x - b)\) by its values at \(a\) and \(b\), the principle behind Unit 10's codes.
Noetherian rings
In the proof that every PID has factorisations (Unit 8), the key step was that a chain of ideals \(I_1 \subseteq I_2 \subseteq \cdots\) can't keep growing forever. Emmy Noether recognised this as the fundamental finiteness property in algebra.
Definition
A ring is Noetherian if every increasing chain of ideals eventually stops: \(I_1 \subseteq I_2 \subseteq \cdots\) implies \(I_k = I_{k+1} = \cdots\) for some \(k\). Equivalently, every ideal is generated by finitely many elements.
Fields, \(\mathbb{Z}\) and every PID are Noetherian, since every ideal has a single generator. The ring \(\mathbb{Q}[x_1, x_2, x_3, \dots]\) of polynomials in infinitely many variables is not: \((x_1) \subsetneq (x_1, x_2) \subsetneq (x_1, x_2, x_3) \subsetneq \cdots\) never stops.
Theorem: Hilbert's basis theorem (1890)
If \(R\) is Noetherian, so is \(R[x]\). Hence \(\mathbb{Z}[x_1, \dots, x_n]\) and \(F[x_1, \dots, x_n]\) are Noetherian for every field \(F\).
Here's what that means concretely. Take any system of polynomial equations in \(n\) variables, even infinitely many equations. The polynomials they generate form an ideal, which by Hilbert's theorem is generated by finitely many of them. So the infinite system is equivalent to a finite one. Hilbert's proof was famously non-constructive (it shows the finite list exists without producing it), prompting the remark "this is not mathematics, it is theology". Today, Gröbner bases compute such lists explicitly, and they're built into every computer algebra system.
Ideals as shapes
Every set of polynomial equations in \(x\) and \(y\) carves out a shape in the plane: the points where all of them vanish. Write \(V(I)\) for the shape of an ideal \(I\) of \(\mathbb{R}[x, y]\) or \(\mathbb{C}[x, y]\).
\((x^2 + y^2 - 1)\)a prime ideal: one piece
\((xy)\)not prime: two pieces
\((x^2 + y^2 - 1,\ y - x^2)\)more equations, smaller shape
This is the start of a dictionary between algebra and geometry:
| Algebra | Geometry |
|---|---|
| an ideal \(I\) | the shape \(V(I)\) where everything in \(I\) vanishes |
| bigger ideal | smaller shape |
| prime ideal | irreducible shape: not a union of two smaller ones |
| maximal ideal \((x - a, y - b)\) | a single point \((a, b)\) |
| the quotient \(\mathbb{C}[x, y]/I\) | the polynomial functions on the shape |
| Krull dimension (Unit 7) | dimension: points 0, curves 1, surfaces 2 |
Over \(\mathbb{C}\), Hilbert's Nullstellensatz (German for "zero-locus theorem") makes the dictionary precise. It says, for instance, that the maximal ideals of \(\mathbb{C}[x, y]\) are exactly the ideals \((x - a, y - b)\): every maximal ideal is a point. It also gives a test for when a system of polynomial equations has no solution: exactly when 1 lies in the ideal, so that \(1 = f_1g_1 + \dots + f_kg_k\) is an algebraic certificate of impossibility.
Grothendieck's great insight in the 1960s was to run the dictionary backwards for every commutative ring: the prime ideals of any ring form a geometric space, its spectrum. Unit 7's picture of \(\operatorname{Spec} \mathbb{Z}[x]\) is an example, with primes as points and polynomials as curves. This fusion of number theory and geometry, arithmetic geometry, is the language in which Fermat's Last Theorem was finally proved in 1995.
Quaternions
Almost everything in this course was about commutative rings. Drop commutativity and a different world appears. Its most famous inhabitant was discovered by William Rowan Hamilton on 16 October 1843, who was so excited that he carved the defining rules into Brougham Bridge in Dublin:
The quaternions \(\mathbb{H}\) are the expressions \(a + bi + cj + dk\) with real \(a, b, c, d\), multiplied using these rules. Hamilton had spent years trying to multiply triples \(a + bi + cj\) and failed; the breakthrough was realising a fourth dimension was needed, and that commutativity had to go.
- A division ring. Every non-zero \(q = a + bi + cj + dk\) has an inverse, \(\bar q / N(q)\), where \(\bar q = a - bi - cj - dk\) and \(N(q) = a^2 + b^2 + c^2 + d^2\). It's like a field in every way except commutativity.
- Rotations. Quaternions with \(N(q) = 1\) describe rotations in 3D space. Video games, animation software and spacecraft attitude control use them because they avoid the "gimbal lock" of angle-based descriptions.
- Four squares. Norms multiply, \(N(pq) = N(p)N(q)\), so products of sums of four squares are sums of four squares. With a quaternion version of the Gaussian-integer argument from Unit 9, this proves Lagrange's four-square theorem (1770): every positive integer is a sum of four squares.
- Nothing else like it. Frobenius proved in 1877 that the only finite-dimensional associative division algebras over \(\mathbb{R}\) are \(\mathbb{R}\), \(\mathbb{C}\) and \(\mathbb{H}\). Going further, to the eight-dimensional octonions, means giving up associativity too.
Non-commutative rings are everywhere once you look: matrix rings, rings of differential operators (where \(\tfrac{d}{dx} \cdot x - x \cdot \tfrac{d}{dx} = 1\), the algebra behind the uncertainty principle in quantum mechanics), and group rings, which underpin representation theory.
Where to go next
Each unit of this course is the doorway to a larger subject:
| If you liked | Explore | The big question |
|---|---|---|
| Units 4, 7, 10: building fields | Galois theory | Why there's no formula for degree-5 equations; which shapes can be constructed with ruler and compass. |
| Units 8, 9: factorisation, \(\mathbb{Z}[i]\) | Algebraic number theory | How primes split in rings of algebraic integers; class groups; quadratic reciprocity. |
| Units 6, 7, 11: ideals, spectra | Commutative algebra and algebraic geometry | The geometry of polynomial equations, from curves to schemes. |
| Unit 10: finite fields | Coding theory and cryptography | Reliable and secure communication; elliptic curves; post-quantum cryptography. |
| Quaternions and matrices | Representation theory | Understanding symmetry by turning group elements into matrices. |
Classic textbooks for a next step include Dummit and Foote's Abstract Algebra, Artin's Algebra, and, for the geometric direction, Cox, Little and O'Shea's Ideals, Varieties, and Algorithms.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. Solve \(x \equiv 1 \pmod 4\), \(x \equiv 2 \pmod 5\).
Show answer
Numbers \(\equiv 2 \pmod 5\): 2, 7, 12, 17, … The first that is \(\equiv 1 \pmod 4\) is 17. So \(x \equiv 17 \pmod{20}\).
2. Is \(\mathbb{Z}/8 \cong \mathbb{Z}/2 \times \mathbb{Z}/4\)? Is \(\mathbb{Z}/20 \cong \mathbb{Z}/4 \times \mathbb{Z}/5\)?
Show answer
First: no. In \(\mathbb{Z}/2 \times \mathbb{Z}/4\), adding any element to itself four times gives 0, but in \(\mathbb{Z}/8\), \(4 \cdot 1 = 4 \neq 0\). (2 and 4 share a factor.) Second: yes, since \(\gcd(4, 5) = 1\).
3. Use the Chinese remainder theorem to find how many solutions \(x^2 = 1\) has in \(\mathbb{Z}/15\).
Show answer
\(\mathbb{Z}/15 \cong \mathbb{Z}/3 \times \mathbb{Z}/5\). In each field \(x^2 = 1\) has 2 solutions (\(\pm 1\)), so there are \(2 \times 2 = 4\) in the product: 1, 4, 11, 14.
4. Compute \((1 + i)(1 + j)\) and \((1 + j)(1 + i)\) in the quaternions.
Show answer
\((1 + i)(1 + j) = 1 + j + i + ij = 1 + i + j + k\). \((1 + j)(1 + i) = 1 + i + j + ji = 1 + i + j - k\). They differ in the sign of \(k\).
5. Which ideal of \(\mathbb{R}[x, y]\) has as its shape the two points \((1, 0)\) and \((-1, 0)\)?
Show answer
\((y,\ x^2 - 1)\): \(y = 0\) gives the horizontal axis, and \(x^2 = 1\) picks out \(x = \pm 1\). It isn't prime, since \((x - 1)(x + 1)\) is in it but neither factor is: the shape has two pieces. By the Chinese remainder theorem, \(\mathbb{R}[x, y]/(y, x^2 - 1) \cong \mathbb{R} \times \mathbb{R}\), one copy of \(\mathbb{R}\) for each point.
6. Find the inverse of the quaternion \(q = 1 + i + j + k\).
Show answer
\(N(q) = 4\) and \(\bar q = 1 - i - j - k\), so \(q^{-1} = \tfrac14(1 - i - j - k)\). Check: \(q\bar q = N(q) = 4\).
Summary and glossary
- Chinese remainder theorem: if \(I + J = R\), then \(R/(I \cap J) \cong R/I \times R/J\). For coprime \(m, n\), \(\mathbb{Z}/mn \cong \mathbb{Z}/m \times \mathbb{Z}/n\).
- A Noetherian ring has no infinite increasing chains of ideals. By Hilbert's basis theorem, polynomial rings over fields are Noetherian: every system of polynomial equations reduces to a finite one.
- Ideals correspond to shapes: bigger ideals give smaller shapes, prime ideals give irreducible shapes, maximal ideals give points.
- The quaternions form a non-commutative division ring that describes 3D rotations and proves every number is a sum of four squares.
- Coprime ideals
- \(I + J = R\).
- Noetherian
- Every ideal is finitely generated.
- \(V(I)\)
- The set of points where every polynomial in \(I\) vanishes.
- Nullstellensatz
- Hilbert's dictionary between ideals and shapes over \(\mathbb{C}\).
- Gröbner basis
- A computable finite generating set for a polynomial ideal.
- Quaternions \(\mathbb{H}\)
- \(a + bi + cj + dk\) with \(i^2 = j^2 = k^2 = ijk = -1\).
- Division ring
- Every non-zero element is invertible; multiplication may not commute.
You've reached the end of the course. Starting from clock arithmetic, you've built fields from polynomials, seen why unique factorisation can fail and how ideals repair it, proved Fermat's two-squares theorem, and classified every finite field. The course map is there whenever you want to revisit a unit.