NTIC Solving Linear Congruences

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 there are.

🔗

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 $t$ 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, 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],[-4]$ all work.

Alternately,

$\begin{equation*} 3+7k,\, k\in\mathbb{Z} \end{equation*}$

is the general solution.