# Solving Linear Congruences

• A linear congruence has solutions if and only if .
• You can solve linear congruences by finding modular inverses, by using the Euclidean algorithm, and by turning the congruence into a linear Diophantine equation.

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 there are infinitely many integer solutions

where 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:

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,

are all the solutions mod m.

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