Skip to main content
🔗

Section 5.1 Solving Linear Congruences

🔗
Our first goal to completely solve all linear congruences ax≡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≡8 (mod 15)

  • 6x≡8 (mod 15)

  • 7x≡8 (mod 14)

  • 6x≡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\) 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.

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

12x≡15 (mod 21).

Here, gcd(a,n)=3 so we will have 3 solutions (up to equivalence modulo 21), all separated by nd=213=7.

We need one solution first. Trying by guess and check small values gives us

  • 12(1)=12≢15,

  • 12(2)=24≡3≢15,

  • but 12(3)=36≡15 (mod 21).

So we may take x=3 as our x0. 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,

3+7k,k∈Z

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.