Proposition5.1.1
\begin{equation*}ax\equiv b\text{ (mod }n\text{) has a solution precisely when }\gcd(a,n)\mid b\; .\end{equation*}
Section5.1Solving Linear Congruences¶ permalink
Our first goal to completely solve all linear congruences \(ax\equiv b\) (mod \(n\)). The most important fact for solving them is as follows.
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\))
Subsection5.1.1The nitty-gritty of solving
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.
Proposition5.1.2
If we can construct one solution to the linear congruence \(ax\equiv b\) (mod \(n\)), we can construct all of them.
Example5.1.3
Let's solve \begin{equation*}12x\equiv 9\text{ (mod }15)\; .\end{equation*} Here, \(\gcd(a,n)=3\) so we will have 3 solutions, all separated by \(\frac{n}{d}=\frac{15}{3}=5\).
We need one solution first. Trying by guess and check small values gives us
\(12(1)=12\not\equiv 9\),
but \(12(2)=24\equiv 9\) (mod \(15\)).
So we may take \(x=2\) as our \(x_0\). Then we add \(5\) to each of these, and we see that \(x=[2],[7],[-3]\) all work.
Alternately, \begin{equation*}2+5t,\, t\in\mathbb{Z}\end{equation*} is the general solution.