Systems of Linear Congruences

In algebra, sometimes we have multiple linear equations, say for example $x + y = 3$ and $x + 2y = 4$, and we might want to find all values $x, y \in \mathbb{R}$ which satisfy (in this case) both equations simultaneously. In this trivial example, if we plug in $y = 3 - x$ (the first equation) into the second equation we get:

(1)

\begin{align} \quad x + 2(3 - x) &= 4 \\ \quad x + 6 - 2x &= 4 \\ \quad x &= 2 \end{align}

So if $x = 2$ then $y = 1$. So the only solution to this small system of linear equations is $(x, y) = (2, 1)$ which can easily be seen as the intersection of these two lines in the plane:

Now suppose that we have some linear congruences. Then we can consider solving a system of linear congruences. For example, consider the following system of linear congruences:

(2)

\begin{align} \quad 2x & \equiv 1 \pmod 3 \\ \quad x & \equiv 2 \pmod 4 \end{align}

All solutions to the first linear congruence are $x = ..., 2, 5, 8, ...$ while all solutions to the second linear congruence are $x = ..., 2, 6, 10, 14, 18, ...$. So clearly $x = 2$ is a solution which satisfies both linear congruences simultaneously. In fact, so should $x = 2 + 12t$ where $t \in \mathbb{Z}$.

However, it should be noted that not all systems of linear congruences are solvable. For example, consider the following system of linear congruences:

(3)

\begin{align} \quad x & \equiv 0 \pmod 2 \\ \quad x & \equiv 1 \pmod 4 \end{align}

The first linear congruence tells us that $x$ must be even. But any even number modulo $4$ is either congruent to $0$ or $2$ modulo $4$ and thus the second linear congruence cannot be satisfied if the first is. Thus this system of linear congruences has no solutions.