So far, we've focused on solving individual modular arithmetic equations. But what happens when a number must satisfy several conditions at once? For example, imagine you're looking for a number $x$ 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.

This scenario can be written as a system of simultaneous congruences:

Finding an $x$ that works for all three equations requires a more powerful tool. The Chinese Remainder Theorem (CRT) provides a systematic way to solve such systems, provided the moduli meet a specific condition.

The Chinese Remainder Theorem states that if you have a system of congruences where the moduli are pairwise coprime, there is a unique solution for $x$ modulo the product of all the moduli. Pairwise coprime means that for any two moduli in the system, their greatest common divisor is 1.

The theorem not only guarantees a solution but also gives us a constructive algorithm to find it.

The core idea is to build the solution piece by piece. For each congruence $x \equiv a_i \pmod{n_i}$, we'll construct a term that satisfies this specific congruence while being equivalent to 0 for all other moduli. Summing these terms gives us the final solution.

Here’s the step-by-step process:

1. Calculate the total product. First, compute $N = n_1 \cdot n_2 \cdot \ldots \cdot n_k$. This will be the modulus of our final unique solution.

2. Isolate each congruence. For each congruence $i$ from 1 to $k$, we define $N_i = N / n_i$. This value $N_i$ is the product of all moduli except $n_i$. By its construction, $N_i$ is a multiple of every $n_j$ (where $j \neq i$), which means $N_i \equiv 0 \pmod{n_j}$.

3. Find the modular inverse. We need to find a number that, when multiplied by $N_i$, is congruent to 1 modulo $n_i$. This is the modular multiplicative inverse of $N_i$ modulo $n_i$. We can find it because we know $\gcd(N_i, n_i) = 1$ (since all the moduli are pairwise coprime). Let's call this inverse $y_i$.

4. Construct the solution. The full solution $x$ is the sum of terms, where each term corresponds to one of the original congruences. The final sum is taken modulo $N$.

Let's solve the system from the beginning:

$x \equiv 2 \pmod{3}$ $x \equiv 3 \pmod{5}$ $x \equiv 2 \pmod{7}$

The moduli 3, 5, and 7 are all prime, so they are pairwise coprime.

1. Total product: $N = 3 \cdot 5 \cdot 7 = 105$.

2. Calculate each $N_i$ and its inverse $y_i$:

   • For $n_1=3$: $N_1 = 105 / 3 = 35$. We need $y_1 \equiv 35^{-1} \pmod{3}$. Since $35 \equiv 2 \pmod{3}$, we need $2^{-1} \pmod{3}$, which is 2. So, $y_1 = 2$.
   • For $n_2=5$: $N_2 = 105 / 5 = 21$. We need $y_2 \equiv 21^{-1} \pmod{5}$. Since $21 \equiv 1 \pmod{5}$, we need $1^{-1} \pmod{5}$, which is 1. So, $y_2 = 1$.
   • For $n_3=7$: $N_3 = 105 / 7 = 15$. We need $y_3 \equiv 15^{-1} \pmod{7}$. Since $15 \equiv 1 \pmod{7}$, we need $1^{-1} \pmod{7}$, which is 1. So, $y_3 = 1$.

3. Construct the solution:

4. Find the final result modulo $N$: $x \equiv 233 \pmod{105}$. $233 = 2 \cdot 105 + 23$, so $x \equiv 23 \pmod{105}$. The smallest positive integer solution is 23.

In competitive programming, the CRT is a powerful technique for problems involving large numbers. If you need to compute a result modulo some large composite number $M$, you can sometimes compute it modulo each of the prime power factors of $M$ and then combine the results using the CRT. This breaks a large, difficult problem into several smaller, more manageable ones.

Here is a C++ implementation. It relies on the Extended Euclidean Algorithm function extendedGcd we developed previously to find modular inverses.

Notice the use of __int128. The intermediate products $a_i \cdot N_i \cdot y_i$ can easily exceed the capacity of a long long, even if the final solution fits. Using a 128-bit integer type is a safe way to handle these large intermediate values before taking the final modulo.

With the Chinese Remainder Theorem, you can now solve systems of congruences, a technique that opens the door to more advanced number theory problems.