Simultaneous Congruences and the CRT

Simultaneous Congruences#

Suppose that instead of one linear congruence, we now want to solve several of them at the same time; that is, given $a_i, c_i \in \mathbb{Z}$ and $n_i \in \mathbb{Z}^+$, we want to find every $x$ satisfying the whole system of simultaneous congruences

$$\begin{align*} a_1 x &\equiv c_1 \pmod{n_1}, \\ a_2 x &\equiv c_2 \pmod{n_2}, \\ &\ \ \vdots \\ a_t x &\equiv c_t \pmod{n_t}. \end{align*}$$

Each individual congruence is solved exactly as in Linear Congruences and Diophantine Equations; the new part is stitching the answers together so that one value of $x$ works for every modulus simultaneously.

The Substitution Method#

The general method is repeated substitution:

• Solve the first congruence for $x$, and write $x$ in terms of a parameter $k_1 \in \mathbb{Z}$.
• Substitute this expression for $x$ into the second congruence.
• Solve that congruence for $k_1$, and write $k_1$ in terms of a new parameter $k_2 \in \mathbb{Z}$.
• Rewrite $x$ in terms of $k_2$, and substitute it into the third congruence.
• Repeat until every congruence has been used. The final expression for $x$ in terms of $k_t$, for all $k_t \in \mathbb{Z}$, describes every solution.

Basically, solving the first congruence narrows $x$ down to one family of integers; each later congruence then filters that family further, and the parameter $k_i$ just keeps track of whatever freedom is left. If the system has no solution at all, this is not a problem for the method; one of the intermediate congruences will simply turn out to be unsolvable, and we can stop there.

Example. Solve $3x \equiv 4 \pmod 5$, $5x \equiv 6 \pmod 7$, and $7x \equiv 8 \pmod 9$ simultaneously.
Starting with the first congruence; since $3 \cdot 2 = 6 \equiv 1 \pmod 5$, the inverse of $3$ modulo $5$ is $2$,

$$\begin{align*} 3x &\equiv 4 \pmod 5 \\ 6x &\equiv 8 \pmod 5 && \text{(multiplying both sides by } 2\text{)} \\ x &\equiv 3 \pmod 5 \\ x &= 3 + 5k_1, \quad k_1 \in \mathbb{Z}. \end{align*}$$

Substituting this into the second congruence,

$$\begin{align*} 5(3 + 5k_1) &\equiv 6 \pmod 7 \\ 15 + 25k_1 &\equiv 6 \pmod 7 \\ 1 + 4k_1 &\equiv 6 \pmod 7 && (15 \equiv 1 \text{ and } 25 \equiv 4 \bmod 7) \\ 4k_1 &\equiv 5 \pmod 7 \\ 8k_1 &\equiv 10 \pmod 7 && \text{(multiplying by } 2 \text{, the inverse of } 4\text{)} \\ k_1 &\equiv 3 \pmod 7 \\ k_1 &= 3 + 7k_2, \quad k_2 \in \mathbb{Z}. \end{align*}$$

Rewriting $x$ in terms of $k_2$,

$$\begin{align*} x &= 3 + 5(3 + 7k_2) \\ &= 18 + 35k_2, \end{align*}$$

and substituting this into the third congruence,

$$\begin{align*} 7(18 + 35k_2) &\equiv 8 \pmod 9 \\ 126 + 245k_2 &\equiv 8 \pmod 9 \\ 0 + 2k_2 &\equiv 8 \pmod 9 && (126 = 14 \times 9 \text{ and } 245 = 27 \times 9 + 2) \\ k_2 &\equiv 4 \pmod 9 && \text{(dividing by } 2 \text{, valid as } \gcd(2,9)=1\text{)} \\ k_2 &= 4 + 9k_3, \quad k_3 \in \mathbb{Z}. \end{align*}$$

Finally,

$$\begin{align*} x &= 18 + 35(4 + 9k_3) \\ &= 158 + 315k_3. \end{align*}$$

Therefore, the solution is $x \equiv 158 \pmod{315}$; notice how the final modulus $315 = 5 \times 7 \times 9$ is the product of all three original moduli.

It is always worth checking the answer by substituting it back into each original congruence:

$$\begin{align*} 3(158) &= 474 = 94(5) + 4 &&\Rightarrow\ 3x \equiv 4 \pmod 5, \\ 5(158) &= 790 = 112(7) + 6 &&\Rightarrow\ 5x \equiv 6 \pmod 7, \\ 7(158) &= 1106 = 122(9) + 8 &&\Rightarrow\ 7x \equiv 8 \pmod 9. \end{align*}$$

All three hold, so $x \equiv 158 \pmod{315}$ is correct. This check takes seconds and catches basically every arithmetic slip, so it is well worth doing in an exam.

Systems with No Solution#

Example. Solve $5x \equiv 1 \pmod 6$, $4x \equiv 5 \pmod 7$, and $3x \equiv 2 \pmod 8$ simultaneously.
For the first congruence, notice that $5 \equiv -1 \pmod 6$,

$$\begin{align*} 5x &\equiv 1 \pmod 6 \\ -x &\equiv 1 \pmod 6 \\ x &\equiv -1 \equiv 5 \pmod 6 \\ x &= 5 + 6k_1, \quad k_1 \in \mathbb{Z}. \end{align*}$$

Substituting into the second congruence,

$$\begin{align*} 4(5 + 6k_1) &\equiv 5 \pmod 7 \\ 20 + 24k_1 &\equiv 5 \pmod 7 \\ 6 + 3k_1 &\equiv 5 \pmod 7 \\ 3k_1 &\equiv -1 \equiv 6 \pmod 7 \\ k_1 &\equiv 2 \pmod 7 && \text{(dividing by } 3 \text{, valid as } \gcd(3,7)=1\text{)} \\ k_1 &= 2 + 7k_2, \quad k_2 \in \mathbb{Z}, \end{align*}$$

so $x = 5 + 6(2 + 7k_2) = 17 + 42k_2$. Substituting into the third congruence,

$$\begin{align*} 3(17 + 42k_2) &\equiv 2 \pmod 8 \\ 51 + 126k_2 &\equiv 2 \pmod 8 \\ 3 + 6k_2 &\equiv 2 \pmod 8 \\ 6k_2 &\equiv -1 \equiv 7 \pmod 8. \end{align*}$$

Here $\gcd(6, 8) = 2$ and $2 \nmid 7$, so by the existence theorem this congruence has no solution. Therefore, the system has no simultaneous solution.

Alternatively, we could have seen this coming without doing any substitution. Reducing the first and third congruences on their own gives $x \equiv 5 \pmod 6$ and (multiplying $3x \equiv 2 \pmod 8$ by $3$, since $3 \cdot 3 = 9 \equiv 1 \pmod 8$) $x \equiv 6 \pmod 8$. Working modulo $\text{lcm}(6,8) = 24$: any solution of the first congruence must be $5, 11, 17$ or $23$ modulo $24$, while any solution of the third must be $6, 14$ or $22$ modulo $24$. There is no overlap between the two lists, so no $x$ can satisfy both. Even quicker: $x \equiv 5 \pmod 6$ forces $x$ to be odd, while $x \equiv 6 \pmod 8$ forces $x$ to be even.

It is important to remember that when the moduli share common factors, a simultaneous solution is not guaranteed to exist; the substitution method will always expose this by producing an unsolvable congruence part-way through.

The Chinese Remainder Theorem#

The failure above happened because $6$ and $8$ share a factor of $2$. If we forbid that from happening — i.e. if every pair of moduli is coprime — then it turns out the system can never be inconsistent.

Basically, when the moduli have nothing in common, the remainders $(c_1, c_2, \dots, c_t)$ act like independent coordinates; no congruence can interfere with another, so you can always find a number hitting all of the required remainders at once, and exactly one such number exists in each window of length $n_1 n_2 \dots n_t$.

Proof (sketch). Uniqueness falls out of the substitution method: in the final expression for $x$, the parameter $k_t$ ends up multiplied by all of the moduli, so any two solutions differ by a multiple of $n_1 n_2 \dots n_t$. Existence is a counting argument; each of the $n_1 n_2 \dots n_t$ elements of $\mathbb{Z}_{n_1 n_2 \dots n_t}$ has some tuple of residues $(c_1, \dots, c_t)$, no two elements can share the same tuple (by the uniqueness we just argued), and there are exactly $n_1 n_2 \dots n_t$ possible tuples; so every tuple, including the one we want, is achieved by exactly one element.

It is important to note that the CRT only tells you a solution exists; to actually find it, you still run the substitution method. Also notice that the theorem is stated for congruences of the form $x \equiv c_i$; if you are given $a_i x \equiv c_i$ instead, solve each congruence individually first to reduce it to that form.

Example. Solve the system of congruences

$$\begin{align*} x &\equiv 3 \pmod 7, \\ x &\equiv 2 \pmod 8, \\ x &\equiv 1 \pmod 9. \end{align*}$$

The moduli are pairwise coprime ($\gcd(7,8) = \gcd(7,9) = \gcd(8,9) = 1$), so the CRT guarantees a unique solution modulo $7 \times 8 \times 9 = 504$ before we even start.
The first congruence gives $x = 3 + 7k_1$ for $k_1 \in \mathbb{Z}$ immediately. Substituting into the second,

$$\begin{align*} 3 + 7k_1 &\equiv 2 \pmod 8 \\ 7k_1 &\equiv -1 \pmod 8 \\ -k_1 &\equiv -1 \pmod 8 && (7 \equiv -1 \bmod 8) \\ k_1 &\equiv 1 \pmod 8 \\ k_1 &= 1 + 8k_2, \quad k_2 \in \mathbb{Z}, \end{align*}$$

so $x = 3 + 7(1 + 8k_2) = 10 + 56k_2$. Substituting into the third,

$$\begin{align*} 10 + 56k_2 &\equiv 1 \pmod 9 \\ 1 + 2k_2 &\equiv 1 \pmod 9 && (10 \equiv 1 \text{ and } 56 \equiv 2 \bmod 9) \\ 2k_2 &\equiv 0 \pmod 9 \\ k_2 &\equiv 0 \pmod 9 && \text{(dividing by } 2 \text{, valid as } \gcd(2,9)=1\text{)} \\ k_2 &= 9k_3, \quad k_3 \in \mathbb{Z}. \end{align*}$$

Finally,

$$\begin{align*} x &= 10 + 56(9k_3) \\ &= 10 + 504k_3. \end{align*}$$

Therefore, the solution is $x \equiv 10 \pmod{504}$; checking, $10 = 7 + 3$, $10 = 8 + 2$ and $10 = 9 + 1$, so all three congruences hold.

Example. (The original puzzle of Sun Tzu.) Find the smallest positive integer 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 is just the system $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 2 \pmod 7$. The moduli $3, 5, 7$ are pairwise coprime, so by the CRT there is a unique solution modulo $3 \times 5 \times 7 = 105$.
From the first congruence, $x = 2 + 3k_1$ for $k_1 \in \mathbb{Z}$. Substituting into the second,

$$\begin{align*} 2 + 3k_1 &\equiv 3 \pmod 5 \\ 3k_1 &\equiv 1 \pmod 5 \\ 6k_1 &\equiv 2 \pmod 5 && \text{(multiplying by } 2 \text{, the inverse of } 3\text{)} \\ k_1 &\equiv 2 \pmod 5 \\ k_1 &= 2 + 5k_2, \quad k_2 \in \mathbb{Z}, \end{align*}$$

so $x = 2 + 3(2 + 5k_2) = 8 + 15k_2$. Substituting into the third,

$$\begin{align*} 8 + 15k_2 &\equiv 2 \pmod 7 \\ 1 + k_2 &\equiv 2 \pmod 7 && (8 \equiv 1 \text{ and } 15 \equiv 1 \bmod 7) \\ k_2 &\equiv 1 \pmod 7 \\ k_2 &= 1 + 7k_3, \quad k_3 \in \mathbb{Z}, \end{align*}$$

giving

$$\begin{align*} x &= 8 + 15(1 + 7k_3) \\ &= 23 + 105k_3. \end{align*}$$

Therefore, the smallest positive such integer is $x = 23$; indeed $23 = 7(3) + 2 = 4(5) + 3 = 3(7) + 2$.

The Generalised Chinese Remainder Theorem#

You already know what an lcm is, so I'm not gonna write much;

For two integers there is a handy formula linking it to the gcd,

$$\boxed{\text{lcm}(a,b) = \frac{ab}{\gcd(a,b)}.}$$

For more than two numbers, the quickest approach by hand is to prime factorise everything and take the highest power of each prime that appears.

Basically, this version drops the requirement that the moduli be pairwise coprime, but it charges a price twice over: it no longer promises that a solution exists (you have to be told that, or discover it yourself), and the uniqueness is only modulo the lcm of the moduli rather than their product. The reason the lcm appears is that during the solving process we divide congruences through by the relevant gcds, which shrinks the moduli; whatever overlap the moduli share only gets counted once. Notice that when the moduli are pairwise coprime, $\text{lcm}(n_1, \dots, n_t) = n_1 n_2 \dots n_t$, so this genuinely generalises the ordinary CRT.

Proof (sketch). The argument is the same as for the ordinary CRT; running the substitution method, the final parameter is multiplied by the moduli with the shared gcd factors divided out, which is precisely the lcm.

Example. Given that $x = 100$ is a solution to the system of congruences

$$\begin{align*} 5x &\equiv 2 \pmod 6, \\ 6x &\equiv 5 \pmod 7, \\ 7x &\equiv 4 \pmod 8, \\ 8x &\equiv 8 \pmod 9, \end{align*}$$

find all solutions to the system.
First check the hypotheses: $\gcd(5,6) = \gcd(6,7) = \gcd(7,8) = \gcd(8,9) = 1$, and we are told a solution exists, so the Generalised CRT applies; the solution is unique modulo $\text{lcm}(6,7,8,9)$. Prime factorising,

$$6 = 2 \times 3, \quad 7 = 7, \quad 8 = 2^3, \quad 9 = 3^2,$$

so taking the highest power of each prime,

$$\begin{align*} \text{lcm}(6,7,8,9) &= 2^3 \times 3^2 \times 7 \\ &= 504. \end{align*}$$

Therefore, the complete solution is $x \equiv 100 \pmod{504}$; no substitution work needed at all. As a sanity check on the given solution,

$$\begin{align*} 5(100) &= 500 = 83(6) + 2, \\ 6(100) &= 600 = 85(7) + 5, \\ 7(100) &= 700 = 87(8) + 4, \\ 8(100) &= 800 = 88(9) + 8, \end{align*}$$

so $x = 100$ really does satisfy all four congruences. Note that the moduli here are not pairwise coprime ($\gcd(6,8) = 2$ and $\gcd(6,9) = 3$), which is exactly why the answer is unique modulo $504$ and not modulo $6 \times 7 \times 8 \times 9 = 3024$.

The Consistency Condition#

When only two congruences with non-coprime moduli are involved, there is a quick test for whether a solution exists at all.

Basically, both congruences are making a claim about $x$ modulo the shared factor $\gcd(n_1, n_2)$, and those two claims had better agree; if they do, everything else is independent and the system behaves like a coprime one.

Example. Solve $x \equiv 1 \pmod 4$ and $x \equiv 5 \pmod 6$ simultaneously.
Checking consistency first: $\gcd(4, 6) = 2$ and $2 \mid (5 - 1)$, so a solution exists and will be unique modulo $\text{lcm}(4,6) = 12$. Writing $x = 1 + 4k_1$ and substituting into the second congruence,

$$\begin{align*} 1 + 4k_1 &\equiv 5 \pmod 6 \\ 4k_1 &\equiv 4 \pmod 6 \\ 2k_1 &\equiv 2 \pmod 3 && \text{(dividing everything, modulus included, by } 2\text{)} \\ k_1 &\equiv 1 \pmod 3 && \text{(dividing by } 2 \text{, valid as } \gcd(2,3)=1\text{)} \\ k_1 &= 1 + 3k_2, \quad k_2 \in \mathbb{Z}. \end{align*}$$

Therefore,

$$\begin{align*} x &= 1 + 4(1 + 3k_2) \\ &= 5 + 12k_2, \end{align*}$$

i.e. $x \equiv 5 \pmod{12}$. Notice how the final modulus is $\text{lcm}(4,6) = 12$ and not $4 \times 6 = 24$; the division by $2$ in the middle of the working is exactly where the difference comes from. Checking: $5 = 4 + 1$ and $5 = 0(6) + 5$, so both congruences hold.

Example. Show that the system $x \equiv 2 \pmod 4$ and $x \equiv 3 \pmod 6$ has no solution.
Using the consistency condition: $\gcd(4,6) = 2$, but $c_1 - c_2 = 2 - 3 = -1$ and $2 \nmid -1$; so the system is inconsistent and we are done. To see the same thing through the substitution method, write $x = 2 + 4k_1$ and substitute,

$$\begin{align*} 2 + 4k_1 &\equiv 3 \pmod 6 \\ 4k_1 &\equiv 1 \pmod 6, \end{align*}$$

and since $\gcd(4,6) = 2$ with $2 \nmid 1$, there is no solution for $k_1$. Therefore, the system has no solution; intuitively, the first congruence forces $x$ to be even while the second forces $x$ to be odd, and both claims are statements about $x$ modulo the common factor $2$.

The CRT Algorithm (Extension)#

There is also a direct formula-style algorithm for coprime systems, which builds the answer in one hit rather than by repeated substitution. Given the system $x \equiv c_i \pmod{n_i}$ for $1 \leq i \leq t$ with $\gcd(n_i, n_j) = 1$ for all $i \neq j$:

• Set $n = n_1 n_2 \dots n_t$.
• For each $i$, solve the congruence $\frac{n}{n_i} x_i \equiv 1 \pmod{n_i}$ for $x_i$.
• The general solution is

$$\boxed{x \equiv \frac{n}{n_1}x_1 c_1 + \frac{n}{n_2}x_2 c_2 + \dots + \frac{n}{n_t}x_t c_t \pmod n.}$$

The trick making this work is that each term $\frac{n}{n_i}x_i c_i$ is congruent to $c_i$ modulo $n_i$ (since $\frac{n}{n_i}x_i \equiv 1 \pmod{n_i}$), but is congruent to $0$ modulo every other $n_j$ (since $n_j \mid \frac{n}{n_i}$); so the terms never interfere with each other, and the sum hits the right remainder for every modulus at once.

This algorithm is not recommended for solving by hand; the multiplications and reductions in the final step are time-consuming, and you still have to solve just as many linear congruences as the substitution method requires. It is mainly of interest because it gives an explicit construction for the CRT (and computers like it).

Example. Use the CRT Algorithm to solve the earlier system $x \equiv 3 \pmod 7$, $x \equiv 2 \pmod 8$, and $x \equiv 1 \pmod 9$.
Here $n = 7 \times 8 \times 9 = 504$, and $\frac{n}{n_1} = 72$, $\frac{n}{n_2} = 63$, $\frac{n}{n_3} = 56$. Solving the three auxiliary congruences:

$$\begin{align*} 72x_1 &\equiv 1 \pmod 7 \\ 2x_1 &\equiv 1 \pmod 7 && (72 = 10 \times 7 + 2) \\ x_1 &\equiv 4 \pmod 7 && (2 \times 4 = 8 \equiv 1 \bmod 7), \end{align*}$$

$$\begin{align*} 63x_2 &\equiv 1 \pmod 8 \\ -x_2 &\equiv 1 \pmod 8 && (63 \equiv -1 \bmod 8) \\ x_2 &\equiv 7 \pmod 8, \end{align*}$$

$$\begin{align*} 56x_3 &\equiv 1 \pmod 9 \\ 2x_3 &\equiv 1 \pmod 9 && (56 = 6 \times 9 + 2) \\ x_3 &\equiv 5 \pmod 9 && (2 \times 5 = 10 \equiv 1 \bmod 9). \end{align*}$$

Assembling the general solution,

$$\begin{align*} x &\equiv 72(4)(3) + 63(7)(2) + 56(5)(1) \pmod{504} \\ &\equiv 864 + 882 + 280 \pmod{504} \\ &\equiv 2026 \pmod{504} \\ &\equiv 10 \pmod{504} && (2026 = 4 \times 504 + 10). \end{align*}$$

Therefore, $x \equiv 10 \pmod{504}$, agreeing with the substitution method; but notice how much heavier the arithmetic was for the same answer.

Classic Puzzles and Applications#

CRT problems love to disguise themselves as word problems; the skill being tested is translating "remainder" language into a congruence system, deciding which theorem applies, and then grinding through the substitution method.

Example. (Brahmagupta's egg basket.) A basket contains some eggs. When the eggs are removed $2, 3, 4, 5$ or $6$ at a time, one egg is always left over; when they are removed $7$ at a time, none are left over. What is the smallest possible number of eggs in the basket?
Translating into congruences, we need

$$x \equiv 1 \pmod{2, 3, 4, 5, 6} \quad \text{and} \quad x \equiv 0 \pmod 7.$$

The first five moduli are certainly not pairwise coprime, so we cannot throw the CRT at this directly. Instead, notice that the five congruences $x \equiv 1$ all say the same thing: $x - 1$ is divisible by each of $2, 3, 4, 5, 6$, which happens exactly when $x - 1$ is divisible by their lcm. Since $\text{lcm}(2,3,4,5,6) = 60$, the whole first batch collapses into the single congruence

$$x \equiv 1 \pmod{60}.$$

Now $\gcd(60, 7) = 1$, so by the Chinese Remainder Theorem the reduced system has a unique solution modulo $60 \times 7 = 420$. Writing $x = 1 + 60k$ and substituting into $x \equiv 0 \pmod 7$,

$$\begin{align*} 1 + 60k &\equiv 0 \pmod 7 \\ 1 + 4k &\equiv 0 \pmod 7 && (60 = 8 \times 7 + 4) \\ 4k &\equiv 6 \pmod 7 \\ 8k &\equiv 12 \pmod 7 && \text{(multiplying by } 2 \text{, the inverse of } 4\text{)} \\ k &\equiv 5 \pmod 7 \\ k &= 5 + 7m, \quad m \in \mathbb{Z}, \end{align*}$$

so

$$\begin{align*} x &= 1 + 60(5 + 7m) \\ &= 301 + 420m. \end{align*}$$

Therefore, the smallest possible number of eggs is $301$; indeed $301 = 43 \times 7$, and $301 = 300 + 1$ leaves remainder $1$ on division by each of $2, 3, 4, 5$ and $6$ since $60 \mid 300$.

Example. A general lines up her soldiers in rows of $7$ and finds $3$ left over; in rows of $8$, $5$ are left over; in rows of $9$, $2$ are left over. Given that she has between $1000$ and $1500$ soldiers, exactly how many does she have?
The system is $x \equiv 3 \pmod 7$, $x \equiv 5 \pmod 8$, $x \equiv 2 \pmod 9$, with pairwise coprime moduli; so the CRT promises a unique answer modulo $504$, and the range restriction of width $500 < 504$ will then pin down a single number.
From the first congruence, $x = 3 + 7k_1$ for $k_1 \in \mathbb{Z}$. Substituting into the second,

$$\begin{align*} 3 + 7k_1 &\equiv 5 \pmod 8 \\ 7k_1 &\equiv 2 \pmod 8 \\ -k_1 &\equiv 2 \pmod 8 && (7 \equiv -1 \bmod 8) \\ k_1 &\equiv -2 \equiv 6 \pmod 8 \\ k_1 &= 6 + 8k_2, \quad k_2 \in \mathbb{Z}, \end{align*}$$

so $x = 3 + 7(6 + 8k_2) = 45 + 56k_2$. Substituting into the third,

$$\begin{align*} 45 + 56k_2 &\equiv 2 \pmod 9 \\ 0 + 2k_2 &\equiv 2 \pmod 9 && (45 = 5 \times 9 \text{ and } 56 = 6 \times 9 + 2) \\ k_2 &\equiv 1 \pmod 9 && \text{(dividing by } 2 \text{, valid as } \gcd(2,9)=1\text{)} \\ k_2 &= 1 + 9k_3, \quad k_3 \in \mathbb{Z}, \end{align*}$$

giving

$$\begin{align*} x &= 45 + 56(1 + 9k_3) \\ &= 101 + 504k_3. \end{align*}$$

The solutions are $101, 605, 1109, 1613, \dots$, and the only one lying between $1000$ and $1500$ is $x = 101 + 2(504) = 1109$.
Therefore, the general has exactly $1109$ soldiers; checking, $1109 = 158(7) + 3 = 138(8) + 5 = 123(9) + 2$.