Skip to main content

Section 4.1 Solving Linear Congruences

As we saw in a previous lecture, finding a solution to the linear Diophantine equation

\begin{equation*} ax + ny = b \end{equation*}

is equivalent to solving the congruence

\begin{equation*} ax \equiv b \pmod{n}. \end{equation*}

In all of the previous examples (from homework and class) we had \(a\) and \(n\) coprime. This is nice, because as previously seen, this is sufficient to give a solution to any linear Diophantine equation of the form \(ax-ny = b,\) since surely \(1\vert b.\) But what if \(\gcd(a,n) = d \gt 1?\) Does the equivalence \(ax\equiv b\pmod{n}\) have a solution? Is it unique? Before we answer these questions we give some definitions to formalise our discussion.

Definition 4.1.1.

An equation of the form \(ax \equiv b \pmod{n}\) is called a linear congruence.

It is also convenient to think of two congruent solutions as "equal", and two that are not congruent as "different". Thus, when we refer to the number of solutions to a linear congruence, we mean the number of incongruent solutions satisfying the congruence.

Since we know that solving \(ax \equiv b \pmod{n}\) is equivalent to solving \(ax-ny = b,\) we have by comparison that \(ax \equiv b \pmod{n}\) has a solution if and only if \(d\vert b,\) where \(d = \gcd(a, n).\) Also we know that if the linear Diophantine is solvable and \(x_0, y_0\) is a solution, then all other solutions are given by

\begin{equation*} x = x_0 +\frac{n}{d}t \hspace{10mm} y=y_0=\frac{a}{d}t \end{equation*}

where \(t\in\mathbb{Z}.\)

Since we are only interested in the solution of the congruence and not the equation, we consider only the solution for \(x.\) We shall show that of all of the solutions \(x = x_0 +\frac{n}{d}t\) for \(t\in\mathbb{Z},\) the only incongruent ones are

\begin{equation*} x_0, x_0+\frac{n}{d}, x_0+\frac{n}{d}2, x_0+\frac{n}{d}3, ...,x_0+\frac{n}{d}(d-1) \end{equation*}

Suppose it happened that two solutions were congruent; that is,

\begin{equation*} x_0=\frac{n}{d}t_1\equiv x_0+\frac{n}{d}t_2 \pmod{n} \end{equation*}

where \(0 \leq t_1 \lt t_2 \leq d-1.\) Then we would have

\begin{equation*} \frac{n}{d}t_1\equiv \frac{n}{d}t_2 \pmod{n}. \end{equation*}

But since \(\gcd(\frac{n}{d}, n) = \frac{n}{d},\) so that

\begin{equation*} t_1 \equiv t_2 \pmod{d} \end{equation*}

which is impossible since \(0 \leq t_1 \lt t_2 \leq d-1\) shows that \(n \nmid t_1-t_2.\) Thus our list of solutions are pairwise incongruent.

To see that any solution is congruent to one on our list, suppose that \(x_0+\frac{n}{d}t\) is some solution. Using the Division Algorithm, we may we may write \(t = qd + r,\) where \(0 \leq r \lt d.\) Now

\begin{align*} x_0 +\frac{n}{d}t \amp =x_0+\frac{n}{d}(qd+r)\\ \amp =x_0+nq+\frac{n}{d}r\\ \amp \equiv x_0+\frac{n}{d}r\pmod{n} \end{align*}

where \(x_0 +\frac{n}{d}r\) is one of the solutions on our list.

Consider the equivalence \(2x = 2 \pmod{4}.\) Since

\begin{equation*} \gcd(2, 4) = 2\vert 2, \end{equation*}

there are \(2\) incongruent solutions modulo \(4.\) We easily see that \(x = 1\) is a solution. All solutions are of the form \(x = 1 + 2t\) for \(t = 0, 1.\) Thus the other solution is \(x = 3.\) So the two incongruent solutions modulo \(4\) are

\begin{equation*} x \equiv 1, 3\pmod{4}. \end{equation*}

To consider a more complicated example we use the following lemma.

Homework problem.

Consider the equivalence \(9x = 21 \pmod{30}.\) Since

\begin{equation*} \gcd(9, 30) = 3\vert 21, \end{equation*}

there are \(3\) incongruent solutions modulo \(30.\) Finding a first solution to this congruence is a little more tricky than the earlier example.

Using the preceding lemma we know that we may solve \(3x \equiv 7 \pmod{10}\) instead. Now multiplying by \(7\) gives this congruence as \(21x \equiv 49\pmod{10}\) so that \(x \equiv 9 \pmod{10}\) is a solution. So the solution to our original congruence are those integers of the form

\begin{equation*} x = 9 + 10t, \end{equation*}

where \(t = 0, 1, 2.\) Thus we have the solutions

\begin{equation*} x \equiv 9, 19, 29\pmod{30}. \end{equation*}