5.4 Linear congruences
We now return to the question of cancellation of congruence classes, postponed from earlier in this chapter.
We would like to be able to simplify an expression of the form \([a][b]=[a][c]\) in order to conclude that \([b]=[c]\).
This is not always true:
Let \(a=2, b=3, c=0\) and \(n=6\). Then \([a][b]=[6]=[0]=[a][c]\), however \([b]=[3]\ne[0]=[c]\). This is reminiscent of the fact that we cannot always cancel even when dealing with integers, since we cannot cancel 0. In the case of mod \(6\) arithmetic we cannot cancel \([2]\) either.
However we can sometimes cancel, so for example, if \([5][b]=[5][c]\) mod \(6\), then \([b]=[c]\). To prove this notice that if \([5][b]=[5][c]\), then \([5][5][b]=[5][5][c]\), so \([25][b]=[25][c]\). But \([25]=[1]\) mod \(6\), so \([b]=[c]\).
More generally if we can find a congruence class \([a']\) such that \([a'][a]=[1]\) then we can cancel \([a]\) by multiplying by \([a']\).
Another way to think of this
If \(b\) is an integer divisible by an integer \(a\), then \(b=aq\) for some integer \(q\), which we called the quotient of \(b\) by \(a\). To say that a congruence class \([b]\) is divisible by another congruence class \([a]\) is to say that there is a congruence class \([q]\) such that \([b]=[a][q]\).
Finding divisors
In order to decide whether or not \([b]\) is divisible by \([a]\) we need to consider the solutions of the linear congruence \(ax\equiv b\text{ mod }(n)\).
Note that if \(x\) is a solution, and if \(x'\equiv x\), then \(ax'\equiv ax\equiv b\) and so \(x'\) is also a solution; thus the solutions (if they exist) form a union of congruence classes.
Now \(ax\equiv b\text{ mod }(n)\) if and only if \(ax-b\) is a multiple of \(n\), so \(x\) is a solution of this linear congruence if and only if there is integer \(y\) such that \(x\) and \(y\) satisfy the linear diophantine equation \(ax+ny=b\), which we studied (with slightly different notation) in Chapter 3. Translating Theorem 3.31 into the language of congruences we have:
If \(d=\gcd(a,n)\), then the linear congruence \[ax\equiv b\text{ mod }(n)\] has a solution if and only if \(d\) divides \(b\).
If \(d\) does divide \(b\), and if \(x_0\) is any solution, then the general solution is given by \[x=x_0+ct\] where \(n=cd\), and \(t\in{\mathbb Z}\).
In particular, the solutions form exactly \(d\) congruence classes \(\text{mod }(n)\), with representatives \[x=x_0,\; x_0+{c},\; x_0+{2c},\; \ldots,\; x_0+{(d-1)c}\,.\]
Proof. Apart from a slight change of notation, the only part of this which is not a direct translation of Theorem 3.31 is the statement about congruence classes. To prove this, note that \[x_0+{tc}\equiv x_0+{t'c}\text{ mod }(n)\] if and only if \(n\) divides \((t-t')c\), that is, if and only if \(d\) divides \(t-t'\), so the congruence classes of solutions \(\text{mod }(n)\) are obtained by letting \(t\) range over a complete set of residues \(\text{mod }(d)\), such as \(0, 1, \ldots, d-1\).
Solve the congruence \[10x\equiv 3\text{ mod }(12)\,.\]
Here \(a=10\), \(b=3\) and \(n=12\), so \(d=\gcd(10,12)=2\); this does not divide \(3\), so there are no solutions. (This can be seen directly: the elements of the congruence class \([3]\) in \({\mathbb Z}_{12}\) are all odd, whereas any elements of \([10][x]\) must be even.)
Solve the congruence \[10x\equiv 6\text{ mod }(12)\,.\]
As before we have \(d=2\), and now this does divide \(b=6\), so there are two classes of solutions. We can take \(x_0=3\) as a particular solution, so the general solution has the form \[x=3+\frac{12t}{2}=3+6t\,,\] where \(t\in{\mathbb Z}\). These solutions form two congruence classes \([3]\) and \([9]\text{ mod }(12)\), with representatives \(x_0=3\) and \(x_0+(n/d)=9\); equivalently, they form a single congruence class \([3]\text{ mod }(6)\).
Find the general solution of the congruence \(12x\equiv 9 \text{ mod }(15)\).
If \(\gcd(a,n)=1\) then the solutions of the linear congruence \(ax\equiv b\text{ mod }(n)\) form a single congruence class \(\text{mod }(n)\).
Proof. Put \(d=1\) in Theorem 5.28.
If \(a,n\) are coprime then \([a]\) is a unit in \(\mathbb Z_n\).
Proof. From the previous Corollary \(ax\equiv 1\) mod \((n)\) has a congruence class \([x]\) as solution. Hence \([a][x]=[1]\).
Recap
There are three possibilities:
- If \(a\) and \(n\) are coprime then for each \(b\) there is a unique class \([x]\) such that \([a][x]=[b]\) in \({\mathbb Z}_n\).
- If \(d=\gcd(a,n)>1\) and \(d|b\) then there is more than one such class \([x]\)
- If \(d\nmid b\) there is no such class.
Consider the congruence \[7x\equiv 3\text{ mod }(12)\,.\] Here \(a=7\) and \(n=12\), and since these are coprime there is a single congruence class of solutions; this is the class \([x]=[9]\), since \(7\times 9=63\equiv 3\text{ mod }(12)\).
Solving \(ax\equiv b\) for small \(n\)
In Examples 5.29, 5.30 and 5.34, 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.35(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.35(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.35(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.