[Introduction to Number Theory Series Part 15] How Does the Chinese Remainder Theorem Solve Several Congruences at Once?

So far we have solved one congruence at a time. But real problems often give several modular conditions at once.

What this post covers

• The basic meaning of the Chinese remainder theorem
• Why pairwise coprime moduli matter
• Two small examples
• The structural idea behind the construction

Key terms

• Chinese remainder theorem: the theorem that combines congruences with pairwise coprime moduli into one congruence class
• congruence: the relation of equal remainders
• modular inverse: the multiplicative inverse modulo n
• coprime: having gcd 1

A basic example

Suppose we want an integer x such that

$$x \equiv 2 \pmod 3$$

and

$$x \equiv 1 \pmod 5.$$

Since 3 and 5 are coprime, the Chinese remainder theorem says there is a solution, and that it is unique modulo 3\cdot 5=15. That means every solution is congruent to 11 modulo 15.

Checking the values 2,5,8,11,14,..., we see that 11 also leaves remainder 1 modulo 5. So

$$x \equiv 11 \pmod {15}.$$

Another example

Solve

$$x \equiv 1 \pmod 4, \qquad x \equiv 2 \pmod 3.$$

The numbers congruent to 1 modulo 4 are 1,5,9,13,..., and among them 5 is congruent to 2 modulo 3. So

$$x \equiv 5 \pmod {12}.$$

Why do coprime moduli matter?

Pairwise coprime moduli behave independently. That independence is what lets us match one remainder condition without destroying the others. In the standard theorem, this pairwise coprime assumption is the key hypothesis.

If the moduli are not coprime, two things can happen:

• the conditions may conflict
• solutions may still exist, but the clean CRT form is no longer automatic

For beginners, the safest first version is the coprime case.

What is the construction idea?

The construction is based on building pieces that behave like this:

• they satisfy one remainder condition
• they become 0 in the other moduli

Modular inverses make those pieces possible.

Common mistakes

1. Applying the theorem without checking coprimeness

The standard clean version requires pairwise coprime moduli.

2. Finding one number and forgetting the modulus of the full answer

The real answer is a congruence class modulo the product of the moduli.

3. Treating CRT as brute-force substitution only

Brute force works for tiny examples, but the theorem is really about structure.

Wrap-up

The Chinese remainder theorem combines several congruence conditions into one congruence class when the moduli are pairwise coprime.

Next we turn to power computations and one of the most famous theorems in number theory: Fermat's little theorem.