# Existence of Solutions to Linear Congruences

Recall from the Linear Congruences page that if $a, b, m \in \mathbb{Z}$ then a linear congruence is a congruence of the form:

(1)We said that $x \in \mathbb{Z}$ is a solution to this linear congruence if $x$ satisfies the linear congruence above. In particular, we noted that a linear congruence may have infinitely many solutions, though, only finite many "special" solutions (which we often classify as *the* set of solutions) or perhaps no solutions at all.

We will now examine some results in determining whether a linear congruence has solutions or not.

Theorem 1: Let $a, b, m \in \mathbb{Z}$. Then linear congruence $ax \equiv b \pmod m$ has a solution $x_0$ if and only if there exists a $k \in \mathbb{Z}$ with $ax_0 = b + km$. |

**Proof:**$\Rightarrow$ Suppose that $x_0$ is a solution to $ax \equiv b \pmod m$. Then $ax_0 \equiv b \pmod m$ and thus:

- So there exists a $k \in \mathbb{Z}$ with $km = ax_0 - b$, i.e., $ax_0 = b + km$.

- $\Leftarrow$ Suppose that for $x_0 \in \mathbb{Z}$ there exists a $k \in \mathbb{Z}$ such that $ax_0 = b + km$. Then $km = ax_0 - b$, i.e., $m \mid (ax_0 - b)$. So $ax_0 \equiv b \pmod m$, i.e., $x_0$ is a solution to the linear congruence $ax \equiv b \pmod m$. $\blacksquare$

Theorem 2: Let $a, b, m \in \mathbb{Z}$. Then:a) If $(a, m) \not \mid b$ then $ax \equiv b \pmod m$ has no solutions.b) If $(a, m) = 1$ then $ax \equiv b \pmod m$ has one solution.c) If $(a, m) \mid b$ then $ax \equiv b \pmod m$ has exactly $(a, m)$ solutions. |

**Proof of a)**We will prove the contrapositve statement. Suppose $ax \equiv b \pmod m$ has a solution $x_0 \in \mathbb{Z}$. Then $ax_0 \equiv b \pmod m$, and so there exists a $k \in \mathbb{Z}$ with:

- Let $d = (a, m)$. Then $d \mid a$ and $d \mid m$. So from above we see that $d \mid b$, i.e., $(a, m) \mid b$. Since the assumption that $ax \equiv b \pmod m$ has solutions implies that $(a, m) \mid b$ we have that $(a, m) \not \mid b$ implies that $ax \equiv b \pmod m$ has no solutions. $\blacksquare$

**Proof of b)**Let $(a, m) = 1$. Then there exists $r, s \in \mathbb{Z}$ such that:

- Multiplying this equation by $b$ gives us:

- Rewriting this equation and we have that:

- Hence $a(rb) \equiv b \pmod m$. So $x_0 = rb$ is a solution to this linear congruence. Now, suppose that there exists more than one solution, say $x_0, x_1 \in \mathbb{Z}$ are both solutions to $ax \equiv b \pmod m$. Then we have that:

- Hence $ax_0 \equiv ax_1 \pmod m$. But $(a, m) = 1$, so $x_0 \equiv x_1 \pmod m$. Since $x_0, x_1 \in \{ 0, 1, ..., m - 1 \}$ we conclude that $x_0 = x_1$. $\blacksquare$.

**Proof of c)**Let $(a, m) = d$ and use part (b). $\blacksquare$

Let's now look at some examples.

## Example 1

**Determine the number of solutions the linear congruence $3x \equiv 5 \pmod {12}$ has.**

Notice that $(a, m) = (3, 12) = 4$ and that $4 \not \mid 5$. Hence $3x \equiv 5 \pmod {12}$ has no solutions.

## Example 2

**Determine the number of solutions the linear congruence $6x \equiv 10 \pmod {14}$ has.**

Notice that $(a, m) = (6, 14) = 2$ and that $2 \mid 10$. Hence $6x \equiv 10 \pmod {14}$ has two solutions and it is not hard to verify that they are $x = 4$ and $x = 11$.