# Systems of Congruences

## Several Congruences at Once

A system of congruences asks for an integer satisfying several congruence conditions simultaneously.

For example,

$$
x\equiv2\pmod3
$$

and

$$
x\equiv3\pmod5
$$

form a system. A solution is an integer $x$ that satisfies both congruences.

Testing small values, we find

$$
8\equiv2\pmod3
$$

and

$$
8\equiv3\pmod5.
$$

Thus

$$
x=8
$$

is one solution. Since congruence conditions repeat periodically, there are infinitely many integer solutions, but they usually form one or more residue classes modulo a larger modulus.

## Compatible Conditions

Not every system of congruences has a solution.

Consider

$$
x\equiv1\pmod4
$$

and

$$
x\equiv2\pmod6.
$$

The first congruence says that $x$ is odd. The second says that $x$ is even. These conditions cannot both hold. Therefore the system has no solution.

The obstruction comes from the fact that the moduli $4$ and $6$ are not coprime. Since

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

the two congruences must agree modulo $2$. But

$$
1\not\equiv2\pmod2.
$$

Thus the system is incompatible.

## Two Congruences

Consider the system

$$
x\equiv a\pmod m,
$$

$$
x\equiv b\pmod n.
$$

This system has a solution if and only if

$$
a\equiv b\pmod{\gcd(m,n)}.
$$

Equivalently,

$$
\gcd(m,n)\mid(a-b).
$$

This condition is necessary because any solution $x$ satisfies

$$
x-a\equiv0\pmod m
$$

and

$$
x-b\equiv0\pmod n.
$$

Hence $x\equiv a$ modulo every divisor of $m$, and $x\equiv b$ modulo every divisor of $n$. In particular, modulo $\gcd(m,n)$, the two residues must agree.

It is also sufficient, as follows from the Euclidean algorithm.

## Reduction to a Linear Congruence

To solve

$$
x\equiv a\pmod m,
$$

write

$$
x=a+mk
$$

for some integer $k$.

Substitute this into the second congruence:

$$
a+mk\equiv b\pmod n.
$$

Thus

$$
mk\equiv b-a\pmod n.
$$

This is a linear congruence in $k$. It is solvable exactly when

$$
\gcd(m,n)\mid(b-a).
$$

This recovers the compatibility condition.

Once $k$ is found, the value

$$
x=a+mk
$$

gives a solution to the original system.

## Example with Coprime Moduli

Solve

$$
x\equiv2\pmod3,
$$

$$
x\equiv3\pmod5.
$$

Write

$$
x=2+3k.
$$

Substitute into the second congruence:

$$
2+3k\equiv3\pmod5.
$$

Hence

$$
3k\equiv1\pmod5.
$$

Since

$$
3^{-1}\equiv2\pmod5,
$$

we get

$$
k\equiv2\pmod5.
$$

Thus

$$
k=2+5t.
$$

Therefore

$$
x=2+3(2+5t)=8+15t.
$$

So the solution is

$$
x\equiv8\pmod{15}.
$$

The modulus $15$ is the product $3\cdot5$, since the original moduli are coprime.

## Example with Non-Coprime Moduli

Solve

$$
x\equiv3\pmod6,
$$

$$
x\equiv7\pmod{10}.
$$

We have

$$
\gcd(6,10)=2.
$$

Since

$$
3\equiv7\pmod2,
$$

the system is compatible.

Write

$$
x=3+6k.
$$

Substitute:

$$
3+6k\equiv7\pmod{10}.
$$

Thus

$$
6k\equiv4\pmod{10}.
$$

Divide by

$$
\gcd(6,10)=2.
$$

This gives

$$
3k\equiv2\pmod5.
$$

Since

$$
3^{-1}\equiv2\pmod5,
$$

we obtain

$$
k\equiv4\pmod5.
$$

Therefore

$$
x=3+6(4+5t)=27+30t.
$$

Thus

$$
x\equiv27\pmod{30}.
$$

The combined modulus is

$$
\operatorname{lcm}(6,10)=30.
$$

## General Form of the Solution

If the system

$$
x\equiv a\pmod m,
$$

$$
x\equiv b\pmod n
$$

has a solution, then all solutions form one residue class modulo

$$
\operatorname{lcm}(m,n).
$$

This means that if $x_0$ is one solution, then every solution is given by

$$
x\equiv x_0\pmod{\operatorname{lcm}(m,n)}.
$$

The least common multiple appears because it is the smallest positive period shared by both congruence conditions.

## Several Congruences

For a system

$$
x\equiv a_1\pmod{n_1},
$$

$$
x\equiv a_2\pmod{n_2},
$$

$$
\cdots
$$

$$
x\equiv a_r\pmod{n_r},
$$

compatibility must hold pairwise:

$$
a_i\equiv a_j\pmod{\gcd(n_i,n_j)}
$$

for all $i,j$.

When the system is compatible, the solutions form one residue class modulo

$$
\operatorname{lcm}(n_1,n_2,\ldots,n_r).
$$

A practical way to solve such a system is to combine two congruences at a time.

## Pairwise Coprime Moduli

The cleanest case occurs when the moduli are pairwise coprime:

$$
\gcd(n_i,n_j)=1
$$

whenever

$$
i\ne j.
$$

Then every system

$$
x\equiv a_i\pmod{n_i}
$$

has a unique solution modulo

$$
N=n_1n_2\cdots n_r.
$$

This is the Chinese remainder theorem, which will be studied next.

Pairwise coprimality removes all compatibility obstructions because every pair of residues automatically agrees modulo $1$.

## Role in Number Theory

Systems of congruences allow several local arithmetic conditions to be imposed simultaneously.

They appear in divisibility problems, calendar calculations, periodic sequences, modular equations, cryptography, and algebraic number theory.

The central question is compatibility. When moduli overlap through common divisors, the residues must agree on that overlap. When the moduli are coprime, the conditions are independent and can always be combined into a single congruence.