Skip to main content

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\))

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,y\) to \(ax-b=ny\)

  • 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.

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, 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.