# Linear Congruences

Theorem. Let , and consider the equation

(a) If , there are no solutions.

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

Proof. Observe that

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

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:

Then

Now divides both sides, and , so I can divide this congruence through by to obtain

Going the other way, suppose . This means that and differ by a multiple of d:

So

This implies that

So

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 ranges over all possible solutions mod m. To be very specific, all the solutions mod m are given by

Example. Solve .

Since , there are no solutions.

Example. Solve .

Since , there will be 1 solutions mod 4. I'll find it in three different ways.

Using linear Diophantine equations.

By inspection , is a particular solution. , so the general solution is

The y equation is irrelevant. The x equation says

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

This tells me how to juggle the coefficient of x to get :

(I used the fact that .

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

I see that , so I multiply the equation by 3:

Theorem. Let , and consider the equation

(a) If , there are no solutions.

(b) If , there are exactly distinct solutions mod m.

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

Example. Solve

, so there are 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

Set

Then

, , is a particular solution. The general solution is

Substitute for w:

, , is a particular solution. The general solution is

will produce distinct values of y mod 10. Note, however, that s and produce and , which are congruent mod 10. That is, adding a multiple of 2 to a given value of s makes the term in x repeat itself mod 10. So I can get all possibilities for x mod 10 by letting .

All together, the distinct solutions mod 10 are

Remarks: I saw the particular solution , by inspection. In general, you can get one using the Extended Euclidean algorithm. For example, in this case

Multiply by (to match ) to get

So a particular solution is and .

In general, it can be tricky to determine the parameter ranges which give the correct number of solutions; it may require some trial-and-error, or careful analysis of the general solution.

Contact information