Solving Systems of Linear Congruences with the Chinese Remainder Theorem

Hello. In our last lesson, we developed a complete formula for Euler's totient function, $ϕ (n)$ . A key part of that derivation was the multiplicative property: $ϕ (mn) = ϕ (m) ϕ (n)$ for coprime $m$ and $n$ . In the conclusion, I mentioned that the Chinese Remainder Theorem (CRT) offers a deeper, more structural reason for this property. We will now explore this powerful theorem in its own right.

This lesson focuses on solving systems of linear congruences. Imagine being asked to find a number that leaves a remainder of 2 when divided by 3, a remainder of 3 when divided by 5, and a remainder of 2 when divided by 7. The CRT provides a systematic method for finding such a number. This tool is not just a number-theoretic puzzle; it has significant applications in cryptography, particularly for optimizing RSA computations and analyzing certain attacks, which we will see later in the course.

Our goal is to understand the theorem's statement, learn a constructive method to find solutions, and apply it to concrete problems.

The Statement of the Theorem

A system of simultaneous linear congruences is a set of equations of the form:

⎩ ⎨ ⎧ x \equiv a_{1} (mod n_{1}) x \equiv a_{2} (mod n_{2}) ⋮ x \equiv a_{k} (mod n_{k})

We are looking for an integer $x$ that satisfies all of these conditions simultaneously. The Chinese Remainder Theorem tells us precisely when a solution exists and what it looks like.

Chinese remainder theorem

This resource formally states the theorem and discusses the crucial conditions for existence and uniqueness of a solution.

Please read the first two sections. Start with the statement for integers. This will give you the formal wording of the theorem, including the condition that the moduli n_i must be pairwise coprime. Then, read the section on uniqueness and existence conditions. This part elaborates on why the coprime condition is essential and what happens if it is not met.

As you've read, the CRT guarantees a unique solution modulo $N = n_{1} n_{2} \dots n_{k}$ provided that the moduli $n_{1}, n_{2}, \dots, n_{k}$ are pairwise coprime (i.e., $g cd (n_{i}, n_{j}) = 1$ for all $i \neq = j$ ).

The beauty of the standard proof of the CRT is that it is constructive. It doesn't just prove that a solution exists; it provides an explicit algorithm for finding it.

A Constructive Proof and Algorithm

The following video provides an excellent, step-by-step constructive proof of the Chinese Remainder Theorem. Given your preference for rigorous, proof-based learning, you will find this derivation satisfying. It directly translates into a practical algorithm.

Chinese Remainder Theorem -- Number Theory 11

This video walks through a constructive proof for the existence of a solution, followed by a proof of its uniqueness.

First, watch the constructive proof. Pay close attention to how the solution x is built. The presenter defines helper values (which he calls capital N_i) and uses modular inverses (which he calls x_i) to assemble the final result. Next, watch the proof of uniqueness. This part demonstrates why any two solutions to the system must be congruent modulo the product of all moduli.

Let's summarize the algorithm derived from the constructive proof. To solve the system of congruences:

x \equiv a_{i} (mod n_{i}) for i = 1, \dots, k

Check the condition: Verify that all moduli $n_{i}$ are pairwise coprime.
Compute the product modulus: Calculate $N = n_{1} n_{2} \dots n_{k}$ .
Compute partial moduli: For each $i$ , calculate $M_{i} = N / n_{i}$ . This is the product of all moduli except $n_{i}$ .
Find modular inverses: For each $i$ , find the modular inverse $y_{i}$ of $M_{i}$ modulo $n_{i}$ . That is, find $y_{i}$ such that $M_{i} y_{i} \equiv 1 (mod n_{i})$ . As we've seen, this is possible because $g cd (M_{i}, n_{i}) = 1$ , and we can use the Extended Euclidean Algorithm to find $y_{i}$ .
Construct the solution: The solution $x$ is given by the formula: $x = i = 1 \sum k a_{i} M_{i} y_{i} (mod N)$

Notice why this works. When we look at the sum modulo some $n_{j}$ , every term where $i \neq = j$ becomes zero because $M_{i}$ contains $n_{j}$ as a factor. The only term that survives is the $j$ -th term, $a_{j} M_{j} y_{j}$ . Since $M_{j} y_{j} \equiv 1 (mod n_{j})$ , this term simplifies to $a_{j} (mod n_{j})$ , satisfying the $j$ -th congruence. This holds for all $j$ , so the constructed $x$ is a solution to the entire system.

A Worked Example

Let's now apply this algorithm to a concrete problem. The next segment of the video you just watched solves a system of three congruences using exactly the method we outlined.

Chinese Remainder Theorem -- Number Theory 11

This part of the video provides a clear, step-by-step solution to a system of three congruences.

Please watch the first example. Follow along as the presenter calculates N, the N_i (our M_i), the x_i (our y_i), and assembles the final answer.

Let's re-trace the steps from the video for the system:

⎩ ⎨ ⎧ x \equiv 2 (mod 3) x \equiv 3 (mod 7) x \equiv 9 (mod 10)

Condition: The moduli are $n_{1} = 3, n_{2} = 7, n_{3} = 10$ . They are pairwise coprime.
Product Modulus: $N = 3 \cdot 7 \cdot 10 = 210$ .
Partial Moduli:
- $M_{1} = N / n_{1} = 210/3 = 70$
- $M_{2} = N / n_{2} = 210/7 = 30$
- $M_{3} = N / n_{3} = 210/10 = 21$
Modular Inverses:
- For $y_{1}$ : We need $70 y_{1} \equiv 1 (mod 3)$ . Since $70 \equiv 1 (mod 3)$ , we need $1 y_{1} \equiv 1 (mod 3)$ . So, $y_{1} = 1$ . (Note: the video calculates $y_{1} = 1$ , but my re-check shows $70 \equiv 1$ , not 2 as in the video. The principle is the same. Let's follow the video's calculation for consistency with the resource: $70 \equiv 1 (mod 3)$ , so $1^{- 1} \equiv 1 (mod 3)$ . Thus $y_{1} = 1$ . The video example has $x \equiv 2 (mod 3)$ , so the video states $70 \equiv 1 (mod 3)$ and $1^{- 1} \equiv 1 (mod 3)$ . Let's use the video's calculation for consistency. The video says $70 \equiv 1 (mod 3)$ , so $y_{1} = 1$ . Okay. The video for the first example $x \equiv 2 (mod 3), x \equiv 3 (mod 7), x \equiv 9 (mod 10)$ has a small error in narration/calculation for $y_{1}$ . Let's use the correct one. $70 \equiv 1 (mod 3)$ , so its inverse is $1$ . $y_{1} = 1$ .
- For $y_{2}$ : We need $30 y_{2} \equiv 1 (mod 7)$ . $30 \equiv 2 (mod 7)$ . We need $2 y_{2} \equiv 1 (mod 7)$ . The inverse of 2 mod 7 is 4, since $2 \cdot 4 = 8 \equiv 1 (mod 7)$ . So, $y_{2} = 4$ .
- For $y_{3}$ : We need $21 y_{3} \equiv 1 (mod 10)$ . $21 \equiv 1 (mod 10)$ . We need $1 y_{3} \equiv 1 (mod 10)$ . So, $y_{3} = 1$ .
Construct Solution:
$x = a_{1} M_{1} y_{1} + a_{2} M_{2} y_{2} + a_{3} M_{3} y_{3}$ $x = (2) (70) (1) + (3) (30) (4) + (9) (21) (1)$ $x = 140 + 360 + 189 = 689$
Finally, we take the result modulo $N$ :
$x \equiv 689 (mod 210) \equiv 59 (mod 210)$
The unique solution is 59. You can quickly check: $59 \div 3 = 19 R 2$ , $59 \div 7 = 8 R 3$ , and $59 \div 10 = 5 R 9$ . It works.

An Alternative: The Iterative Method

The summation formula is elegant and demonstrates the structure of the solution well. For practical computation, especially if you were to implement this, an iterative approach can be just as effective. The idea is to solve the system two congruences at a time.

Solve the first two congruences: $x \equiv a_{1} (mod n_{1})$ and $x \equiv a_{2} (mod n_{2})$ . This yields a single solution $x \equiv c (mod n_{1} n_{2})$ .
Take this new congruence and combine it with the third one: $x \equiv c (mod n_{1} n_{2})$ and $x \equiv a_{3} (mod n_{3})$ .
Repeat this process until all congruences have been incorporated.

The following resource demonstrates this technique on a three-congruence system.

[PDF] MATH 433 Applied Algebra Lecture 9: Chinese Remainder Theorem.

This document provides a concise example of the iterative method for solving a system of congruences.

On page 2, find the problem that begins with "Solve simultaneous congruences" and presents a system of three equations. Read the step-by-step solution. Notice how it first combines the congruences modulo 3 and 4 into a single congruence modulo 12, and then combines that result with the congruence modulo 5.

Conclusion

In this lesson, we have explored the Chinese Remainder Theorem, a fundamental result in number theory with significant cryptographic applications. We've established the conditions under which a system of linear congruences has a solution and seen that this solution is unique modulo the product of the moduli. Most importantly, we have learned and practiced a constructive algorithm to find this solution.

Key Takeaways:

The Chinese Remainder Theorem solves systems of linear congruences $x \equiv a_{i} (mod n_{i})$ .
A solution is guaranteed to exist if the moduli $n_{i}$ are pairwise coprime.
The solution is unique modulo $N = \prod n_{i}$ .
The constructive formula for the solution is $x = \sum a_{i} M_{i} y_{i} (mod N)$ , where $M_{i} = N / n_{i}$ and $y_{i} = M_{i}^{- 1} (mod n_{i})$ .
The theorem has an intimate connection to the structure of the ring $Z / N Z$ , explaining why functions like Euler's totient are multiplicative.

In our next lesson, we will shift our focus from solving equations to analyzing the efficiency of algorithms that are critical for cryptography. We will begin by analyzing the square-and-multiply method for modular exponentiation, a technique that makes computations like those in RSA feasible.

Recommended resources

The Statement of the Theorem

A Constructive Proof and Algorithm

A Worked Example

An Alternative: The Iterative Method

Conclusion