Solving Linear Congruences

Let

(⇒)

Suppose

Then

so

for some integer k. Since d | a and d | n,

(⇐)

Suppose

Write

Then

is equivalent to

where

Thus, it is enough to consider the case

Consider

Suppose two of them have the same remainder modulo n. Then, for some 1 ≤ i < j ≤ n,

Hence

Since

we have

But

which is impossible.

Therefore, a, 2a, ..., na have n distinct remainders modulo n. Hence, they cover all possible remainders

In particular, one of them has remainder b. Therefore, for some x,

Thus,

Let

If

then by the solvability theorem for linear congruences,

has no solution.

Now suppose

Write

Then

is equivalent to

where

Therefore, modulo n', there is exactly one solution. Let this solution be

Thus all integer solutions are

for integers k.

Since

consider

These are all solutions modulo n.

They are pairwise incongruent modulo n. Indeed, if

then

Since n = dn',

But for

we have

which is impossible.

Hence these d solutions are distinct modulo n.

Therefore,

So altogether,

First compute

Since

solutions exist.

Divide by 6:

Divide by -4:

A solution exists if and only if

Since

we need

Therefore,

Multiply by 2:

Multiply by 14: