5.5 Solving congruences
Solving \(ax\equiv b\) for small \(n\)
In Examples 5.29, 5.30 and 5.33, we had \(n=12\). When \(n\) is small as in these cases, We can simply calculate \(ax\) for each of the \(n\) elements \(x\) of a complete set of residues \(\text{mod }(n)\), and see which of these products are congruent to \(b\).
Solving \(ax\equiv b\) for larger \(n\)
In general however, a more efficient method is needed for solving linear congruences. We shall give an algorithm for this, based on Theorem 5.28, but first we need some preliminary results.
- Let \(m\) divide \(a, b\) and \(n\), and let \(a=a'm,\; b=b'm\) and \(n=n'm\). Then \[ax\equiv b\text{ mod }(n)\quad\text{if and only if}\quad a'x\equiv b'\text{ mod }(n')\,.\]
- Let \(a\) and \(n\) be coprime, let \(m\) divide \(a\) and \(b\), and let \(a=a'm\) and \(b=b'm\). Then \[ax\equiv b\text{ mod }(n)\quad\text{if and only if}\quad a'x\equiv b'\text{ mod }(n)\,.\]
Proof.
We have \(ax\equiv b\) \(\text{mod }(n)\) if and only if \(ax-b=qn\) for some integer \(q\) and so dividing by \(m\), we see that this is equivalent to \(a'x-b'=qn'\), that is, to \(a'x\equiv b'\text{ mod }(n')\).
If \(ax\equiv b\text{ mod }(n)\), then as in (1) we have \(ax-b=qn\) and hence \((a'x-b')m=qn\). It follows that \(m\) divides \(qn\) and since \(m\) is also coprime to \(n\) (\(m\) divides \(a\) and \(a\) is coprime to \(n\)) then \(m\) must divide \(q\) by Corollary 3.27(b). Thus, letting \(q = q'm\) we have that \(a'x-b'=q'n\) is a multiple of \(n\), so \(a'x\equiv b'\text{ mod }(n)\).
Conversely, if \(a'x\equiv b'\text{ mod }(n)\) then \(a'x-b'=q'n\) for some integer \(q'\). Hence, multiplying by \(m\) we see that \(ax-b=mq'n\) and hence \(ax\equiv b\text{ mod }(n)\).
Note that in (1), where \(m\) divides \(a, b\) and \(n\), we divide all three of these integers by \(m\), whereas in (2), where \(m\) divides \(a\) and \(b\), we divide just these two integers by \(m\), leaving \(n\) unchanged. Also note that in part (2) \[ a'x\equiv b'\text{ mod }n\Rightarrow ax\equiv b\mod n \] is always true but \[ ax\equiv b\text{ mod }n\Rightarrow a'x\equiv b'\mod n \] is ONLY true when \(\gcd(a,n)=1\).
Show, by means of a counterexample, that Lemma 5.34(2) can fail if \(a\) and \(n\) are not coprime.
An algorithm to solve \(ax\equiv b\text{ mod }(n)\)
To help you understand each step, it may be useful to try this algorithm out on the congruence \(10x\equiv 6\text{ mod }(14)\) - take a look in Appendix E to see if you are correct.
Step 1
We calculate \(d=\gcd(a,n)\), using the Euclidean algorithm if necessary, and see whether \(d\) divides \(b\). If it does not, there are no solutions, so we stop. If it does, we go on to step 2.
Assuming that there is a solution, Theorem 5.28 will give us the general solution. All we need is to find a particular solution \(x_0\), so the rest of the algorithm focusses on finding \(x_0\). The general strategy is to reduce \(|a|\) until \(|a|=1\), since in this case the solution \(x_0=\pm b\) is obvious.
Step 2
Since \(d\) divides \(a, b\) and \(n\), Lemma 5.34(1) implies that we can replace the original congruence with \[a'x\equiv b'\text{ mod }(n')\,,\] where \(a=a'd,\; b=b'd\) and \(n=n'd\). Note also that by Corollary 3.26, \(a'\) and \(n'\) are coprime. If \(d=1\) then this is nothing practical to do in this step.
Step 3
We now use Lemma 5.34(ii) to “divide” this new congruence by \(m=\gcd(a',b')\), resulting in a congruence \[a''x\equiv b''\text{ mod }(n')\] where \(a'=a''m\), \(b'=b''m\) and \(a''\) is coprime to both \(b''\) and \(n'\). If \(a''=\pm1\) then \(x_0=\pm b''\) is the required solution. Otherwise, we go on to step 4. If \(m=1\) then this is nothing practical to do in this step.
Step 4
There are two ways to proceed at this stage.
- Noting that \[b''\equiv b''\pm n'\equiv b''\pm 2n'\equiv\ldots\text{ mod }(n')\,,\] we may be able to replace \(b''\) with some number \(b'''\equiv b''\text{ mod }n'\) such that \(\gcd(a'',b''')>1\).
- Alternatively, we may be able to multiply the congruence by some suitably chosen constant \(c\), giving \(ca''x\equiv cb''\text{ mod }(n')\), in such a way that the least absolute residue \(a'''\) of \(ca''\) satisfies \(|a'''|<|a''|\). Then we have reduced \(|a''|\) to give a linear congruence \(a'''x\equiv b'''\text{ mod }(n')\) with \(b'''=cb''\).
In both cases, we can then apply step 3 to the new congruence \(a'''x\equiv b'''\text{ mod }(n')\) and again reduce \(|a'''|\). A combination of the methods in step 4 will eventually reduce \(a\) to \(\pm 1\), in which case the solution \(x_0\) can be read off. Theorem 5.28 then gives the general solution.
Consider the congruence \[10x\equiv 6\text{ mod }(14)\,.\]
Solution. Step 1 gives \(\gcd(10,14)=2\), which divides \(6\), so there is a solution. If \(x_0\) is any solution, then the general solution is \(x=x_0+(14/2)t=x_0+7t\), where \(t\in{\mathbb Z}\). To find \(x_0\) go onto step 2 - we divide the original congruence through by \(\gcd(10,14)=2\) to give \[5x\equiv 3\text{ mod }(7)\,.\]
Step 3 has no effect since \(\gcd(5,3)=1\) and so we move on to step 4. We see that \(3\equiv 10\text{ mod }(7)\), with \(10\) divisible by \(5\), we replace the congruence with \[5x\equiv 10\text{ mod }(7)\] and then divide by \(5\) (which is coprime to \(7\)) to give \[x\equiv 2\text{ mod }(7)\,.\] Thus \(x_0=2\) is a solution, so the general solution has the form \[x=2+7t\quad(t\in{\mathbb Z})\,.\]
Consider the congruence \[4x\equiv 13\text{ mod }(47)\,.\]
Solution. Step 1 gives \(\gcd(4,47)=1\), which divides \(13\), so the congruence has solutions. If \(x_0\) is any solution, then the general solution is \(x=x_0+47t\) where \(t\in{\mathbb Z}\), forming a single congruence class \([x_0]\) in \({\mathbb Z}_{47}\). Since \(\gcd(4,47)=1\), step 2 has no effect, so we move on to step 3, which also has no effect since \(\gcd(4,13)=1\). Noting that \(4\times 12=48\equiv 1\text{ mod }(47)\), we multiply by \(12\) to give \[48x\equiv 12\times 13\text{ mod }(47)\,,\] that is, \[x\equiv 3\times 4\times 13\equiv 3\times 52\equiv 3\times 5\equiv 15\text{ mod }(47)\,.\] Thus we can take \(x_0=15\), so the general solution is \(x=15+47t\).
For more practice in solving linear congruences, visit Appendix E in the online version of these notes.