Chinese Remainder Theorem: Constructive Solutions

students, imagine you have a calendar with three alarms going off at different times ⏰. One rings every $3$ hours, another every $5$ hours, and another every $7$ hours. Instead of checking hour by hour, number theory gives a smart way to construct the exact hour when all the timing rules line up. That idea is at the heart of constructive solutions in the Chinese Remainder Theorem (CRT).

In this lesson, you will learn how to:

explain what a constructive solution means in CRT,
build solutions step by step rather than guessing,
use number theory tools like modular inverses,
connect the method to the full Chinese Remainder Theorem,
check your work with real examples.

Constructive solutions matter because CRT is not just a statement that a solution exists. It also gives a practical method for finding it. That makes it useful in mathematics, coding, cryptography, and scheduling problems 🔍.

What a constructive solution means

A constructive solution is a method for actually finding the number that satisfies several congruences at once. In other words, instead of only proving that a solution exists, we build one.

Suppose we want to find a number $x$ such that

$$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}.$$

If the moduli $n_1, n_2, \dots, n_k$ are pairwise coprime, then CRT says there is exactly one solution modulo

$$N = n_1 n_2 \cdots n_k.$$

A constructive solution tells us how to actually compute that $x$.

The key idea is to build $x$ from pieces that “turn on” for one congruence and “turn off” for the others. This often uses products of the moduli and modular inverses.

The main construction idea

Let

$$N = n_1 n_2 \cdots n_k.$$

For each congruence, define

$$N_i = \frac{N}{n_i}.$$

Now $N_i$ is divisible by every modulus except $n_i$. That means $N_i \equiv 0 \pmod{n_j}$ for every $j \neq i$. So $N_i$ already helps with all the other conditions.

But we also need $N_i$ to give the correct remainder modulo $n_i$. Since $N_i$ and $n_i$ are coprime, there exists a number $M_i$ such that

$$N_i M_i \equiv 1 \pmod{n_i}.$$

This $M_i$ is a modular inverse of $N_i$ modulo $n_i$.

Then the solution is constructed by

$$x \equiv \sum_{i=1}^{k} a_i N_i M_i \pmod{N}.$$

Why does this work? For each term $a_i N_i M_i$:

modulo $n_i$, it becomes $a_i \cdot 1 = a_i$,
modulo any other $n_j$, it becomes $0$ because $N_i$ is divisible by $n_j$.

So when all terms are added, the total has the right remainder for every modulus.

A worked example with three congruences

Let’s solve:

$$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 2 \pmod{7}.$$

Here the moduli $3$, $5$, and $7$ are pairwise coprime, so CRT applies.

First compute

$$N = 3 \cdot 5 \cdot 7 = 105.$$

Now find each $N_i$:

$$N_1 = \frac{105}{3} = 35, \quad N_2 = \frac{105}{5} = 21, \quad N_3 = \frac{105}{7} = 15.$$

Next find inverses.

For $N_1 = 35$ modulo $3$

We need $35M_1 \equiv 1 \pmod{3}$. Since $35 \equiv 2 \pmod{3}$, we want

$$2M_1 \equiv 1 \pmod{3}.$$

A solution is $M_1 = 2$, because $2 \cdot 2 = 4 \equiv 1 \pmod{3}$.

For $N_2 = 21$ modulo $5$

We need $21M_2 \equiv 1 \pmod{5}$. Since $21 \equiv 1 \pmod{5}$, we can take

$$M_2 = 1.$$

For $N_3 = 15$ modulo $7$

We need $15M_3 \equiv 1 \pmod{7}$. Since $15 \equiv 1 \pmod{7}$, we can take

$$M_3 = 1.$$

Now build the solution:

$$x \equiv 2(35)(2) + 3(21)(1) + 2(15)(1) \pmod{105}.$$

Compute the sum:

$$x \equiv 140 + 63 + 30 = 233 \pmod{105}.$$

Reduce modulo $105$:

$$233 \equiv 23 \pmod{105}.$$

So a solution is

$$x \equiv 23 \pmod{105}.$$

Check it:

$23 \equiv 2 \pmod{3}$,
$23 \equiv 3 \pmod{5}$,
$23 \equiv 2 \pmod{7}$.

Everything matches ✅.

Why the method works

The construction works because of two facts:

$N_i$ is divisible by all moduli except $n_i$.
The inverse $M_i$ makes $N_i M_i \equiv 1 \pmod{n_i}$.

So the term $a_i N_i M_i$ behaves like a “selector” for the $i$th congruence.

This is a powerful idea. Instead of searching for the answer among many numbers, we assemble it from pieces that already know what to do.

Here is the logic in compact form:

For the $i$th congruence, the term $a_i N_i M_i$ contributes $a_i$ modulo $n_i$.
For every other congruence, the same term contributes $0$.
Adding all terms gives a number that satisfies all congruences simultaneously.

Because the solution is unique modulo $N$, any equivalent answer such as $23 + 105t$ for any integer $t$ is also a correct solution.

Finding modular inverses in practice

To use constructive solutions well, you need a way to find modular inverses. A modular inverse of $r$ modulo $m$ is a number $s$ such that

$$rs \equiv 1 \pmod{m}.$$

This exists exactly when $\gcd(r,m)=1$.

There are two common ways to find it:

1. Trial and checking small numbers

This works when the modulus is small. For example, to find the inverse of $4$ modulo $9$, test multiples:

$$4 \cdot 7 = 28 \equiv 1 \pmod{9},$$

so the inverse is $7$.

2. The Extended Euclidean Algorithm

This is the standard method for larger numbers. It finds integers $u$ and $v$ such that

$$ru + mv = 1.$$

Then $u$ is the inverse of $r$ modulo $m$.

For example, if you want the inverse of $11$ modulo $26$, the algorithm can produce values with

$$11u + 26v = 1.$$

Then $u \equiv 11^{-1} \pmod{26}$.

In constructive CRT problems, the Extended Euclidean Algorithm is especially useful because the needed inverses can be large.

A second example with slightly larger numbers

Solve

$$x \equiv 1 \pmod{4}, \quad x \equiv 4 \pmod{9}, \quad x \equiv 6 \pmod{11}.$$

The moduli are pairwise coprime, so CRT applies.

First compute

$$N = 4 \cdot 9 \cdot 11 = 396.$$

Then

$$N_1 = 99, \quad N_2 = 44, \quad N_3 = 36.$$

Now find inverses:

$99 \equiv 3 \pmod{4}$, and $3^{-1} \equiv 3 \pmod{4}$, so $M_1 = 3$.
$44 \equiv 8 \pmod{9}$, and $8^{-1} \equiv 8 \pmod{9}$, so $M_2 = 8$.
$36 \equiv 3 \pmod{11}$, and $3^{-1} \equiv 4 \pmod{11}$, so $M_3 = 4$.

Construct:

$$x \equiv 1(99)(3) + 4(44)(8) + 6(36)(4) \pmod{396}.$$

$$x \equiv 297 + 1408 + 864 = 2569 \pmod{396}.$$

Reduce:

$$2569 \equiv 97 \pmod{396}.$$

Check:

$97 \equiv 1 \pmod{4}$,
$97 \equiv 4 \pmod{9}$,
$97 \equiv 9 \pmod{11}$.

Wait — the last check shows $97 \not\equiv 6 \pmod{11}$. That means we made a calculation mistake in the construction or reduction. Let’s correct it carefully.

For modulo $11$, since $36 \equiv 3 \pmod{11}$, we need $3M_3 \equiv 1 \pmod{11}$. Indeed $M_3=4$ works because $3 \cdot 4 = 12 \equiv 1 \pmod{11}$.

Now compute the third term correctly:

$$6 \cdot 36 \cdot 4 = 864.$$

That part is fine. The total is still $2569$. Reduce modulo $396$:

$$396 \cdot 6 = 2376, \quad 2569 - 2376 = 193.$$

$$x \equiv 193 \pmod{396}.$$

Check again:

$193 \equiv 1 \pmod{4}$,
$193 \equiv 4 \pmod{9}$,
$193 \equiv 6 \pmod{11}$.

Now it works ✅. This example shows why checking your final answer is important.

Connection to the broader Chinese Remainder Theorem

Constructive solutions are the practical side of CRT. The theorem tells us:

a solution exists when the moduli are pairwise coprime,
the solution is unique modulo the product $N$.

The constructive method explains how to find that solution. So the lesson “constructive solutions” sits right inside the larger CRT topic: it turns an existence theorem into an algorithm.

That algorithmic side is why CRT is so useful in applications. For example, computers can break a hard problem into smaller mod problems, solve them quickly, and then rebuild the answer using CRT 🧩.

Conclusion

students, constructive solutions in the Chinese Remainder Theorem show how to build a number that satisfies several congruences at once. The main strategy is to use the product $N$ of all moduli, form the pieces $N_i = N/n_i$, and multiply by modular inverses so each piece matches exactly one congruence. This gives a direct, reliable method for solving systems of congruences.

The important ideas are:

CRT guarantees a unique solution modulo $N$ when the moduli are pairwise coprime,
constructive solutions provide the method to find that solution,
modular inverses are the key tool,
checking the final answer is essential.

With practice, this process becomes a powerful and systematic way to solve number theory problems.

Study Notes

Constructive solutions mean finding an actual number that satisfies several congruences, not just proving one exists.
For pairwise coprime moduli $n_1, n_2, \dots, n_k$, the solution is unique modulo $N = n_1 n_2 \cdots n_k$.
Define $N_i = N/n_i$.
Find $M_i$ such that $N_iM_i \equiv 1 \pmod{n_i}$; this $M_i$ is a modular inverse.
The CRT construction is

$$x \equiv \sum_{i=1}^{k} a_iN_iM_i \pmod{N}.$$

Each term is designed to be correct for one modulus and $0$ for the others.
Modular inverses can be found by testing small numbers or using the Extended Euclidean Algorithm.
Always verify the final answer by substituting it back into every congruence.
Constructive solutions connect CRT to real-world problem solving in scheduling, computing, and cryptography.