Linear Congruences

In elementary algebra we learn how to solve simple linear equations such as $2x + 3 = 5$. We will now look at solving analogous linear congruences which we define below.

Definition: Let $a, b, m \in \mathbb{Z}$. A Linear Congruence is a congruence of the form $ax \equiv b \pmod m$, and $x \in \mathbb{Z}$ is said to be a Solution if it satisfies this linear congruence.

For example, consider the following linear congruence with $a = 1$, $b = 2$, and $m = 3$:

(1)

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

This linear congruence has infinitely many solutions, namely, $x = ..., -1, 2, 5, 8, ...$. In fact, if a linear congruence has solutions then it will always have infinitely many solutions since if $x_0$ is a solution to $ax \equiv b \pmod m$ then so if $x_0 + km$ for all $k \in \mathbb{Z}$.

Of course, there is one particular solution that is of interest. $x = 2$ is "special" in a sense because $2 \in \{ 0, 1, 2, \}$. Hence, we will often times distinguish "solutions" of a linear congruence to mean solutions contained in $\{ 0, 1, ..., m - 1 \}$

Of course, it is possible that a linear congruence has no solutions. For example, consider the following linear congruence with $a = 2$, $b = 1$, and $m = 4$:

(2)

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

We claim that this linear congruence has no solutions. To show this, note that for all $x \in \mathbb{Z}$ that $2x$ is an even integer. So $2x \equiv 0 \pmod 4$ for $x = ..., -2, 0, 2, ...$ and $2x \equiv 2 \pmod 4$ for $x = ..., -1, 1, 3, ...$. Thus $2x \equiv 1 \pmod 4$ has no solutions by exhausting all possible integer solutions $x$.