Systems of Congruences

Several Congruences at Once

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

For example,

and

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

Testing small values, we find

and

Thus

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

and

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

the two congruences must agree modulo $2$. But

Thus the system is incompatible.

Two Congruences

Consider the system

This system has a solution if and only if

Equivalently,

This condition is necessary because any solution $x$ satisfies

and

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

write

for some integer $k$.

Substitute this into the second congruence:

Thus

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

This recovers the compatibility condition.

Once $k$ is found, the value

gives a solution to the original system.

Example with Coprime Moduli

Solve

Write

Substitute into the second congruence:

Hence

Since

we get

Thus

Therefore

So the solution is

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

Example with Non-Coprime Moduli

Solve

We have

Since

the system is compatible.

Write

Substitute:

Thus

Divide by

This gives

Since

we obtain

Therefore

Thus

The combined modulus is

General Form of the Solution

If the system

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

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

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

Several Congruences

For a system

compatibility must hold pairwise:

for all $i,j$.

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

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:

whenever

Then every system

has a unique solution modulo

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.