Linear Congruence Systems

A system of linear congruences has a solution when all congruences are compatible and there exists at least one integer $ x $ that satisfies each individual equation: $$ \begin{cases} a_1 x ≡ b_1 \mod n_1 \\ a_2 x ≡ b_2 \mod n_2 \\ \vdots \\ a_n x ≡ b_n \mod n_n \end{cases} $$

A congruence $ ax \equiv b \mod n $ is considered compatible if the greatest common divisor $ \gcd(a, n) $ divides $ b $.

A system of linear congruences can have one solution, multiple solutions, or no solution at all.

Note: Compatibility is a necessary but not sufficient condition for solving the system. If one or more congruences are incompatible, the system has no solutions. However, even if all congruences are compatible, there may still not be an integer $ x $ that satisfies them all.

A Practical Example
Rewriting the System in an Equivalent Form

A Practical Example

Let's consider the following system:

$$ \begin{cases} 4x ≡ 2 \mod 6 \\ 3x ≡ 1 \mod 5 \end{cases} $$

The first step is to check whether the linear congruences are compatible.

The congruence $ 4x \equiv 2 \mod 6 $ is compatible because $ \gcd(4,6) = 2 $ divides 2.

$$ \gcd(4,6) = 2 \mid 2 $$

Similarly, the congruence $ 3x \equiv 1 \mod 5 $ is compatible since $ \gcd(3,5) = 1 $ divides 1.

$$ \gcd(3,5) = 1 \mid 1 $$

Note: Since both congruences are compatible, we can proceed to find a solution.

Next, we determine whether there is a common solution for both congruences.

The first solution to $ 4x \equiv 2 \mod 6 $ is $ x_0 = 2 $.

$$ 4x \equiv 2 \mod 6 \\ 4(2) \equiv 2 \mod 6 \\ 8 \equiv 2 \mod 6 \\ 2 \equiv 2 \mod 6 $$

The solutions, given $ n=6 $ and $ d = \gcd(4,6) = 2 $, are:

$$ 2 \\ 2+\frac{6}{2} = 5 \\ 2+2\frac{6}{2} = 8 \\ \vdots $$

The first solution to $ 3x \equiv 1 \mod 5 $ is $ x_0 = 2 $.

$$ 3x \equiv 1 \mod 5 \\ 3(2) \equiv 1 \mod 5 \\ 6 \equiv 1 \mod 5 \\ 1 \equiv 1 \mod 5 $$

The solutions, given $ n=5 $ and $ d = \gcd(3,5) = 1 $, are:

$$ 2 \\ 2+\frac{5}{1} = 7 \\ 2+2\frac{5}{1} = 12 \\ \vdots $$

The integer $ x = 2 $ satisfies both congruences:

$$ \begin{cases} 4x ≡ 2 \mod 6 \\ 3x ≡ 1 \mod 5 \end{cases} $$

$$ \begin{cases} 4(2) ≡ 2 \mod 6 \\ 3(2) ≡ 1 \mod 5 \end{cases} $$

$$ \begin{cases} 8 ≡ 2 \mod 6 \\ 6 ≡ 1 \mod 5 \end{cases} $$

$$ \begin{cases} 2 ≡ 2 \mod 6 \\ 1 ≡ 1 \mod 5 \end{cases} $$

Thus, one solution to the system of linear congruences is $ x = 2 $.

Rewriting the System in an Equivalent Form

If the moduli $ n $ in a system of compatible linear congruences are pairwise coprime, meaning $$ \gcd(n_i, n_k) = 1 \quad \text{for} \quad i \neq k $$ then the system can be rewritten in the following equivalent form: $$ \begin{cases} \frac{a_1}{d_1} x ≡ \frac{b_1}{d_1} \mod \frac{n_1}{d_1} \\ \frac{a_2}{d_2} x ≡ \frac{b_2}{d_2} \mod \frac{n_2}{d_2} \\ \vdots \\ \frac{a_n}{d_n} x ≡ \frac{b_n}{d_n} \mod \frac{n_n}{d_n} \end{cases} $$ where $ d_i $ is the greatest common divisor: $$ d_i = \gcd(a_i, n_i) $$

Why is this useful?

Rewriting the system in this equivalent form simplifies finding a solution using the Chinese Remainder Theorem.

Proof

In this form, the values $ n_i/d_i $ are coprime with $ a_i/d_i $, meaning their greatest common divisor is 1:

$$ \gcd\left( \frac{a_i}{d_i}, \frac{n_i}{d_i} \right) = 1 $$

Since 1 is also a divisor of $ b/d $, we have:

$$ \gcd\left( \frac{a_i}{d_i}, \frac{n_i}{d_i} \right) \mid \frac{b_i}{d_i} $$

This guarantees that each congruence in the transformed system has an integer solution $ s_i $.

Note: A congruence $ ax \equiv b \mod n $ has solutions (i.e., is compatible) if and only if $ \gcd(a,n) $ divides $ b $.

Therefore, the system of linear congruences has a solution if and only if there exists an $ x $ such that:

$$ \begin{cases} x ≡ s_1 \mod \frac{n_1}{d_1} \\ x ≡ s_2 \mod \frac{n_2}{d_2} \\ \vdots \\ x ≡ s_n \mod \frac{n_n}{d_n} \end{cases} $$

And so on.