Existence of Solutions to Linear Congruences

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)
\begin{align} \quad ax \equiv b \pmod m \end{align}

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:
(2)
\begin{align} \quad m \mid (ax_0 - b) \end{align}
  • 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:
(3)
\begin{align} \quad ax_0 = b + km \end{align}
  • 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:
(4)
\begin{align} \quad ar + ms = 1 \end{align}
  • Multiplying this equation by $b$ gives us:
(5)
\begin{align} \quad arb + msb = b \end{align}
  • Rewriting this equation and we have that:
(6)
\begin{align} \quad a(rb) + m(sb) = b \\ \quad a(rb) - b = m(sb) \end{align}
  • 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:
(7)
\begin{align} \quad ax_0 \equiv b \pmod m \quad \mathrm{and} \quad ax_1 \equiv b \pmod m \end{align}
  • 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$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License