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$.