Back to the on-screen lesson ·
Several congruences at once: for coprime moduli the system is one congruence modulo the product, and the correspondence is a bijection.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to decide whether a system of congruences has a solution, construct the solution by weighting each remainder with a partial product and its inverse, state the theorem as a bijection between one modulus and a product of coprime ones, say exactly where the coprimality hypothesis is used, and handle a system whose moduli are not coprime.
Lesson 8 solved $ax \equiv b \pmod n$ completely: a gcd decides whether there are solutions, how many, and how far apart.
A system asks something different. $x \equiv 2 \pmod 3$ and $x \equiv 3 \pmod 5$ are each easy on their own; the question is whether some integer satisfies both, and how many do. Searching finds $8$ and then $23$ and then $38$ — a pattern with period $15$, which is $3 \times 5$. This lesson says that is not a coincidence, says exactly when it happens, and builds the answer without searching.
A system of congruences is a list $x \equiv a_i \pmod{n_i}$, all to be satisfied at once.
Moduli are pairwise coprime when $\gcd(n_i, n_j) = 1$ for every $i \ne j$. That is stronger than having no factor common to all of them: $6, 10, 15$ have gcd $1$ overall and no two of them are coprime.
The partial product for the $i$-th congruence is $N_i = N / n_i$, where $N = \prod n_j$ — the product of all the other moduli. It is divisible by every modulus except $n_i$, which is exactly what makes it useful.
A residue number system represents an integer by its remainders against a fixed set of coprime moduli. The theorem is what says the representation is faithful.
Chinese remainder theorem. Let $n_1, \ldots, n_k$ be pairwise coprime and $N = n_1 \cdots n_k$. Then the system $x \equiv a_i \pmod{n_i}$ has a solution, and it is unique modulo $N$.
The construction. For each $i$ put $N_i = N/n_i$. Since $\gcd(N_i, n_i) = 1$, there is an inverse $y_i$ with $N_i y_i \equiv 1 \pmod{n_i}$. Set $$x = \sum_i a_i N_i y_i.$$ Modulo $n_i$, every term but the $i$-th carries a factor $n_i$ and vanishes, and the $i$-th is $a_i \cdot 1 = a_i$. So every congruence holds.
The design principle is worth stating on its own: each term is right for its own modulus and invisible to all the others. That is how a solution to several conditions at once is built out of solutions to each.
The uniqueness, and the better way to see the whole theorem: the map $$\mathbb{Z}_N \;\longrightarrow\; \mathbb{Z}_{n_1} \times \cdots \times \mathbb{Z}_{n_k}, \qquad x \mapsto (x \bmod n_1, \ldots, x \bmod n_k)$$ is injective, because two residues with the same image differ by a multiple of every $n_i$, hence of $N$ when the moduli are pairwise coprime. Both sides have $N$ elements, so injective forces bijective. It respects addition and multiplication, so it is a ring isomorphism.
Where coprimality is spent. In exactly one place: divisible by each $n_i$ implies divisible by $N$. That is false for $2$ and $4$, and the theorem fails there — $x \equiv 1 \pmod 2$, $x \equiv 2 \pmod 4$ has no solution, since the second congruence already forces $x$ even.
Another way: steps
Another way: example
$x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$. $N = 105$. $N_1 = 35$ and $35 \equiv 2 \pmod 3$, whose inverse is $2$; $N_2 = 21 \equiv 1 \pmod 5$, inverse $1$; $N_3 = 15 \equiv 1 \pmod 7$, inverse $1$. So $x = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}$.
The theorem is introduced as a way of combining congruences, and most of its working life is spent going the other way: taking a modulus apart.
Because $\mathbb{Z}_{N} \cong \mathbb{Z}_{n_1} \times \cdots \times \mathbb{Z}_{n_k}$ as rings, any question about arithmetic modulo $N$ can be asked separately modulo each prime power in $N$ and the answers reassembled. Three consequences shape the rest of this course.
The totient is multiplicative. A residue is a unit modulo $N$ exactly when it is a unit modulo each $n_i$, so the units correspond to tuples of units and $\varphi(N) = \prod \varphi(n_i)$ for coprime $n_i$. Lesson 12 states that as a fact about counting; this is why it is true.
Solving is done prime power by prime power. To solve $x^2 \equiv 1 \pmod{35}$, solve it modulo $5$ (giving $x \equiv \pm 1$) and modulo $7$ (again $\pm 1$), then recombine: four solutions, $1, 6, 29, 34$. Counting solutions modulo a composite is multiplying the counts modulo its prime powers.
RSA is fast because of it. Decryption modulo $n = pq$ is done modulo $p$ and modulo $q$ separately — numbers half the size, exponents reduced by Fermat rather than Euler — and recombined. It is roughly four times faster, and every implementation does it.
There is a fourth, more practical use: residue number systems. Represent an integer by its remainders against a fixed set of coprime moduli, and addition and multiplication become componentwise, with no carries between components. The components are independent, so the arithmetic parallelises perfectly. What such a system is bad at is comparison — deciding which of two numbers is larger requires reconstructing them — and that is why it has stayed a specialist technique rather than a general one.
Assuming a system is always solvable. It is guaranteed only for pairwise coprime moduli. $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 6$ has no solution; $x \equiv 1 \pmod 4$ and $x \equiv 3 \pmod 6$ has one, modulo $12$ rather than $24$. Non-coprime moduli need the compatibility condition $a_i \equiv a_j \pmod{\gcd(n_i, n_j)}$, and then the answer is unique modulo the lcm.
Reading pairwise as jointly. $6, 10, 15$ have no common factor across all three, and no two of them are coprime. The theorem does not apply.
Inverting the partial product against the wrong modulus. $N_i$ is inverted modulo $n_i$ — its own — not modulo $N$ and not modulo another $n_j$. Modulo $N$ it is not invertible at all.
Reporting the residue without the modulus. The answer is a class modulo $N$. The number alone is one representative of infinitely many.
Forgetting to reduce. $\sum a_i N_i y_i$ is usually much larger than $N$. It is a correct solution, and it is not the least residue.
$x \equiv 3 \pmod 4$ and $x \equiv 5 \pmod 6$. The moduli share a factor of $2$, so the theorem does not apply and the system may have no solution.
Check the hypothesis before the method.
Test compatibility: modulo $\gcd(4, 6) = 2$, the first says $x \equiv 1$ and the second says $x \equiv 1$. They agree, so a solution exists.
The extra condition that replaces coprimality.
Searching the classes modulo $\operatorname{lcm}(4, 6) = 12$ gives $x \equiv 11$. Unique modulo $12$, not modulo $24$.
The modulus of the answer is the lcm, not the product.
How many $x$ satisfy $x^2 \equiv 1 \pmod{105}$? Split: $105 = 3 \cdot 5 \cdot 7$, all coprime.
The isomorphism turns one question into three.
Modulo each prime, $x^2 \equiv 1$ has exactly two solutions, $\pm 1$, because a prime modulus admits no zero divisors.
Two, three times over.
So there are $2 \cdot 2 \cdot 2 = 8$ solutions modulo $105$ — far more than the two an equation over the rationals would have, and each comes from one choice of sign per prime.
Counting multiplies across the factors.
$\gcd(4, 9) = 1$, so there is one solution modulo $36$.
Existence and the modulus, before any work.
Partial products: $N_1 = 9 \equiv 1 \pmod 4$, inverse $1$; $N_2 = 4 \equiv 4 \pmod 9$, and $4 \cdot 7 = 28 \equiv 1$, so the inverse is $7$.
Each inverted against its own modulus.
$x = 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$.
You are solving $x \equiv 1 \pmod{4}$ and $x \equiv 2 \pmod{5}$. Put the steps into the order you carry them out.
Number the steps in order (write the number in the box):
Find the least residue $x$ with $x \equiv 1 \pmod{3}$ and $x \equiv 3 \pmod{13}$.
Answer:
For the system with moduli $3$ and $11$, give each partial product and its inverse against its own modulus.
| Partial product | Its inverse | |
|---|---|---|
| For the congruence modulo $3$ | ||
| For the congruence modulo $11$ |
$x \equiv a \pmod{6}$ and $x \equiv b \pmod{7}$. The pair is equivalent to a single congruence. What is its modulus?
Answer:
Solve $x \equiv 3 \pmod{5}$ and $x \equiv 3 \pmod{9}$. Give the least residue and the modulus it is unique for.
solution a, modulus c
Build the proof that the system of congruences modulo $4$ and modulo $5$ has exactly one solution modulo $20$.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
You are solving $x \equiv 3 \pmod{4}$ and $x \equiv 2 \pmod{7}$. Put the steps into the order you carry them out.
Number the steps in order (write the number in the box):
You can solve a system of congruences with coprime moduli and say what modulus the answer is unique for. Say in your own words why each term of the construction is invisible to every modulus but its own. Next: the everyday tests this theory explains.
9. Your turn: find the least positive $x$ with $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 9$, step 3