Proposition 5.1.1.
The linear congruence
\begin{equation*}
ax\equiv b\text{ (mod }n)
\end{equation*}
has a solution precisely when \(\gcd(a,n)\mid b\text{.}\)
Section 5.1 Solving Linear Congruences
Our first goal to completely solve all linear congruences \(ax\equiv b\) (mod \(n\)). The most important fact for solving them is as follows.
Example 5.1.2.
Before going on, test yourself by checking which of the following four congruences has a solution and which ones don’t.
- \(7x\equiv 8\) (mod \(15\))
- \(6x\equiv 8\) (mod \(15\))
- \(7x\equiv 8\) (mod \(14\))
- \(6x\equiv 8\) (mod \(14\))
Proof of Proposition 5.1.1.
The proof is pretty straightforward, as long as we recall when linear Diophantine (integer) equations have solutions.
The following are clearly equivalent:
- Solutions \(x\) to \(ax\equiv b\) (mod \(n\))
- Solutions \(x\) to \(n\mid ax-b\)
- Solutions \(x\) to \(ax-b=ny\) (for some \(y\in\mathbb{Z}\))
- Solutions \(x,y\) to \(ax-ny=b\)
And we know from Theorem 3.1.2 that this final equation has solutions precisely when \(\gcd(a,n) \mid b\text{.}\)
Just like in linear algebra or calculus, though, it’s not enough to know when you have solutions; you want to actually be able to construct solutions. If possible, one wants to construct all solutions. In this case, we can do it.
Proposition 5.1.3.
If we can construct one solution to the linear congruence \(ax\equiv b\) (mod \(n\)), we can construct all of them, and we know exactly how many equivalence classes (or remainders) there are of these solutions, which is \(d=\gcd(a,n)\text{.}\)
Proof.
Consider the proof of Proposition 5.1.1 above. We don’t care about \(y\) (other than that it exists, and it does). So if we have one solution to the congruence, that is the same as having a solution \(x_0,y_0\) to the equation \(ax-ny=b\text{.}\)
But we already know what solutions to that look like, from Theorem 3.1.2. Looking just at the \(x\) components, the solutions from e.g. Subsection 3.1.3 (using \(k\) since \(n\) is taken) are
\begin{equation*}
x_0+\frac{n}{d}k\qquad k\in\mathbb{Z}\text{ where }d=\gcd(a,n)\text{.}
\end{equation*}
This argument also gives us the exact number of solutions (modulo \(n\)), because letting \(k\) go from 0 to \(d-1\) will give all different solutions.
Example 5.1.4.
Let’s solve
\begin{equation*}
12x\equiv 15\text{ (mod }21)\text{.}
\end{equation*}
Here, \(\gcd(a,n)=3\) so we will have 3 solutions (up to equivalence modulo \(21\)), all separated by \(\frac{n}{d}=\frac{21}{3}=7\text{.}\)
We need one solution first. Trying by guess and check small values gives us
- \(12(1)=12\not\equiv 15\text{,}\)
- \(12(2)=24\equiv 3\not\equiv 15\text{,}\)
- but \(12(3)=36\equiv 15\) (mod \(21\)).
So we may take \(x=3\) as our \(x_0\text{.}\) Then we add \(7\) a couple times (mod \(21\)) and we see that \(x=[3],[10],[17]\) all work. (Or, if you prefer least absolute residues (recall Definition 4.4.6), then \(x=[3],[10],[-4]\) work.)
Alternately,
\begin{equation*}
3+7k,\, k\in\mathbb{Z}
\end{equation*}
is the general solution.
Remark 5.1.5.
The previous example well illustrates that, while there are infinitely many integers which may solve a congruence, we will usually only consider the finitely many classes of solutions (or finitely many remainders, if you like). However, it is easy to be sloppy and talk about one when you mean the other, so be cautious.
