5.2 Solving linear congruences

If a congruence involves an unknown $x$, we can try to solve it, just like an equation — but there will never be a unique solution, as multiples of the modulus may always be added without changing anything; the best we can hope for is to express the solution in the form ‘‘$x\equiv c\bmod n$’’ for some $n\in\mathbb{N}$. A congruence $x+a\equiv b\bmod m$ is easy: adding $-a$ to both sides (as we may by Lemma 5.1.7) gives the solution as $x\equiv b-a\bmod m$.

A congruence $ax\equiv b\bmod m$ is more subtle, however: there may be no solutions at all; or if there are any, they may involve a modulus other than $m$.

Example 5.2.1(i) raises the question: when does the congruence $ax\equiv b\bmod m$ have solutions? The answer is as follows.

Proof. Set $d=\mathrm{hcf}(a,m)$.

‘‘$\Rightarrow$’’. Suppose that the congruence has solutions; choose one, say $x\in\mathbb{Z}$, so that $ax\equiv b\bmod m$. We can then write $ax=qm+b$ for some $q\in\mathbb{Z}$, and thus $b=ax-qm$. Since $d|a$ and $d|m$, we conclude that $d|b.$

‘‘$\Leftarrow$’’. Conversely, suppose that $d|b$, say $b=td$ for some $t\in\mathbb{Z}$. By Theorem 4.2.17, we can write $d=ra+sm$ for some $r,s\in\mathbb{Z}$, and therefore

$$b=td=t(ra+sm)=a(tr)+(ts)m\equiv a(tr)\bmod m;$$

so the congruence has solutions, because $x=tr$ is one. $\Box$

In fact the second half of the proof of Theorem 5.2.2 gives us more than we have stated: whenever solutions exist, it tells us how to find one explicitly. We formally record this finding as follows.

We now turn our attention to the problem of finding all solutions to a given congruence (under the assumption that solutions exist, of course). We refer to this as finding the complete solution to the congruence. In this context, a specific number which satisfies the congruence is called a particular solution.

We begin by considering the case where $a$ and $m$ are coprime.

Proof. By assumption, $m$ divides $ab-ac=a(b-c)$. As $a$ and $m$ are coprime, this implies that $m$ divides $b-c$ by Theorem 4.4.8, and the result follows. $\Box$

Proof. Set $c=br\in\mathbb{Z}$. Since $a$ and $m$ are coprime, Corollary 5.2.4 shows that $x=c$ is a solution to the congruence, that is, $ac\equiv b\bmod m$.

We must show that an integer $x$ satisfies $ax\equiv b\bmod m$ if and only if $x\equiv c\bmod m$.

‘‘$\Rightarrow$’’. Suppose that $ax\equiv b\bmod m$. Lemma 5.1.7 shows that $b\equiv ac\bmod m$, so that $ax\equiv ac\bmod m$ by Lemma 5.1.9. Lemma 5.2.5 allows us to cancel $a$ because $a$ and $m$ are coprime, and hence we have $x\equiv c\bmod m$.

‘‘$\Leftarrow$’’. Suppose that $x\equiv c\bmod m$. By Lemma 5.1.7, we have $ax\equiv ac\bmod m$. Since $ac\equiv b\bmod m$, Lemma 5.1.9 implies that $ax\equiv b\bmod m$. $\Box$

We can now solve completely any congruence of the form $ax\equiv b\bmod m$ provided that $a$ and $m$ are coprime. Thus all that remains is to show how to reduce a general congruence which has solutions to one in which $a$ and $m$ are coprime. This is easily achieved using the following result.

Proof. By Proposition 5.1.3(b), $ad\equiv bd\bmod nd$ means that $ad=qnd+bd$ for some $q\in\mathbb{Z}$, while $a\equiv b\bmod n$ means that $a=qn+b$ for some $q\in\mathbb{Z}.$ These two statements are clearly equivalent (divide/multiply by $d\neq 0$). $\Box$

Solution. By prime factorization (or the Euclidean algorithm), we find $\mathrm{hcf}(30,145)=5$. Since $5|70$, solutions exist by Theorem 5.2.2. To find the complete solution, we apply Lemma 5.2.8: an integer $x$ satisfies $30x\equiv 70\bmod 145$ if and only if

$$\frac{30}{5}x\equiv\frac{70}{5}\bmod\frac{145}{5},\qquad\text{that is,}\qquad 6x\equiv 14\bmod 29;$$

we saw above that this congruence has the complete solution $x\equiv 12\bmod 29.$

As a check, we verify that $x=12$ satisfies the original congruence:

$$30\cdot 12-70=290=2\cdot 145.$$

Solution. By the Euclidean algorithm, we find

	$\displaystyle 164$	$\displaystyle=6\cdot 26+8$		and	$\displaystyle 2$	$\displaystyle=26-3\cdot 8$
	$\displaystyle 26$	$\displaystyle=3\cdot 8+2$				$\displaystyle=26-3(164-6\cdot 26)$
	$\displaystyle 8$	$\displaystyle=4\cdot 2+0,$				$\displaystyle=19\cdot 26-3\cdot 164.$
	$\displaystyle\text{so that}\ \mathrm{hcf}(26,164)$	$\displaystyle=2$

Since $2|74$, solutions exist by Theorem 5.2.2. To find the complete solution, we apply Lemma 5.2.8: an integer $x$ satisfies $26x\equiv 74\bmod 164$ if and only if

$$\frac{26}{2}x\equiv\frac{74}{2}\bmod\frac{164}{2},\qquad\text{that is,}\qquad 13x\equiv 37\bmod 82,$$

(5.2.1)

where

$$1=\frac{19\cdot 26-3\cdot 164}{2}=19\cdot 13-3\cdot 82,$$

so in particular $13$ and $82$ are coprime (but we know that already, by Corollary 4.4.6). Hence the complete solution to the right-hand congruence in (5.2.1) is given by

$$x\equiv 37\cdot 19=703\equiv 8\cdot 82+47\equiv 47\bmod 82,$$

As a check, we verify that $x=47$ solves the original congruence:

$$26\cdot 47-74=1148=7\cdot 164.$$