Solving Linear Congruences


Theorem. Let $d = (a,m)$ , and consider the equation

$$ax = b \mod{m}.$$

(a) If $d \notdiv b$ , there are no solutions.

(b) If $d \mid b$ , there are exactly d distinct solutions mod m.

Proof. Observe that

$$ax = b \mod{m} \quad \Leftrightarrow \quad ax + my = b \quad\hbox{for some}\quad y.$$

Hence, (a) follows immediately from the corresponding result on linear Diophantine equations. The result on linear Diophantine equations which corresponds to (b) says that there are infinitely many integer solutions

$$x = x_0 + \dfrac{m}{d}t,$$

where $x_0$ is a particular solution. I need to show that of these infinitely many solutions, there are exactly d distinct solutions mod m.

Suppose two solutions of this form are congruent mod m:

$$x_0 + \dfrac{m}{d}t_1 = x_0 + \dfrac{m}{d}t_2 \mod{m}.$$

Then

$$\dfrac{m}{d}t_1 = \dfrac{m}{d}t_2 \mod{m}.$$

Now $\dfrac{m}{d}$ divides both sides, and $\left(\dfrac{m}{d},m\right) =
   \dfrac{m}{d}$ , so I can divide this congruence through by $\dfrac{m}{d}$ to obtain

$$t_1 = t_2 \mod{d}.$$

Going the other way, suppose $t_1 = t_2 \mod{d}$ . This means that $t_1$ and $t_2$ differ by a multiple of d:

$$t_1 - t_2 = kd.$$

So

$$\dfrac{m}{d}t_1 - \dfrac{m}{d}t_2 = \dfrac{m}{d}\cdot kd = km.$$

This implies that

$$\dfrac{m}{d}t_1 = \dfrac{m}{d}t_2 \mod{m}$$

so

$$x_0 + \dfrac{m}{d}t_1 = x_0 + \dfrac{m}{d}t_2 \mod{m}.$$

Let me summarize what I've just shown. I've proven that two solutions of the above form are equal mod m if and only if their parameter values are equal mod d. That is, if I let t range over a complete system of residues mod d, then $x_0 + \dfrac{m}{d}t$ ranges over all possible solutions mod m. To be very specific,

$$x_0 + \dfrac{m}{d}t \mod{m} \hbox{ for } t = 0, 1, 2, \ldots, d - 1$$

are all the solutions mod m.


Example. Solve $6x = 7 \mod{8}$ .

Since $(6,8) = 2 \notdiv 7$ , there are no solutions.


Example. Solve $3x = 7 \mod{4}$ .

Since $(3,4) = 1 \mid 7$ , there will be 1 solutions mod 4. I'll find it in three different ways.

Using linear Diophantine equations.

$$3x = 7 \mod{4} \quad\hbox{implies}\quad 3x + 4y = 7 \quad\hbox{for some}\quad y.$$

By inspection $x_0 = 1$ , $y_0 = 1$ is a particular solution. $(3,4) = 1$ , so the general solution is

$$x = 1 + 4t, \quad y = 1 - 3t.$$

The y equation is irrelevant. The x equation says

$$x = 1 \mod{4}.$$

Using the Euclidean algorithm. Since $(3,4) = 1$ , some linear combination of 3 and 4 is equal to 1. In fact,

$$(-1)\cdot 3 + 1\cdot 4 = 1.$$

This tells me how to juggle the coefficient of x to get $1\cdot x$ :

$$\matrix{& 4x & = & 0 & \mod{4} \cr - & 3x & = & 7 & \mod{4} \cr \noalign{\hrule} & x & = & 1 & \mod{4} \cr}$$

(I used the fact that $7 =
   -1 \mod{4}$ .

Using inverses mod 4. Here is a multiplication table mod 4:

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & * & & 0 & & 1 & & 2 & & 3 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 0 & & 0 & & 0 & & 0 & & 0 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 1 & & 0 & & 1 & & 2 & & 3 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 2 & & 0 & & 2 & & 0 & & 2 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 3 & & 0 & & 3 & & 2 & & 1 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

I see that $3\cdot 3 = 1
   \mod{4}$ , so I multiply the equation by 3:

$$3x = 7 \mod{4}, \quad x = 21 = 1 \mod{4}.\quad\halmos$$


Theorem. Let $d = (a,b,m)$ , and consider the equation

$$ax + by = c \mod{m}.$$

(a) If $d \notdiv c$ , there are no solutions.

(b) If $d \mid c$ , there are exactly $md$ distinct solutions mod m.

I won't give the proof; it follows from the corresponding result on linear Diophantine equations.


Example. Solve

$$2x + 6y = 4 \mod{10}.$$

$(2,6,10) = 2 \mid 4$ , so there are $2\cdot 10 = 20$ solutions mod 10. I'll solve the equation using a reduction trick similar to the one I used to solve two variable linear Diophantine equations.

The given equation is equivalent to

$$2x + 6y + 10z = 4 \hbox{ for some } z.$$

Set

$$w = \dfrac{2}{(2,6)}x + \dfrac{6}{(2,6)}y.$$

Then

$$(2,6)w + 10z = 4, \quad 2w + 10z = 4, \quad w + 5z = 2.$$

$w_0 = -3$ , $z_0 = 1$ , is a particular solution. The general solution is

$$w = -3 + 5s, \quad z = 1 - s.$$

Substitute for w:

$$\dfrac{2}{(2,6)}x + \dfrac{6}{(2,6)}y = -3 + 5s, \quad x + 3y = -3 + 5s.$$

$x_0 = 5s$ , $y_0 = -1$ , is a particular solution. The general solution is

$$x = 5s + 3t, \quad y = -1 - t.$$

$t = 0, 1, \ldots, 9$ will produce distinct values of y mod 10. Note, however, that s and $s + 2r$ produce $5s$ and $5s +
   10r$ , which are congruent mod 10. That is, adding a multiple of 2 to a given value of s makes the $5s$ term in x repeat itself mod 10. So I can get all possibilities for x mod 10 by letting $s = 0, 1$ .

All together, the distinct solutions mod 10 are

$$x = 5s + 3t, \quad y = -1 - t, \quad \hbox{where} \quad s = 0,1 \quad\hbox{and}\quad t = 0, 1, \ldots, 9.\quad\halmos$$


Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga