* 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.

Copyright 2019 by Bruce Ikenaga