Example

Solve the following linear congruence

$$21x \equiv 14 \pmod{91}$$

First, we translate things back into equation form.

$21x \equiv 14 \pmod{91}$ implies $14 - 21x = 91n$ for some integer $n$. This in turn, suggests that we can write 14 as a linear combination of 91 and 21:

$$21x + 91n = 14$$

By inspection, we note that the gcd of 91 and 21 is 7, so we verify that 14 is a multiple of 7, which it is. Given that these numbers are as small as they are, we could probably find one solution for $x$ and $n$ by inspection. That said, let us go through the process we would use if the numbers were much larger...

First, we will try to find a single solution to the intermediate equation: $21x_1 + 91n_1 = 7$, using the Euclidean algorithm.

$$\begin{align} 91 &= 4 \cdot 21 + \fbox{7} \leftarrow \textrm{gcd}\\ 21 &= 3 \cdot 7 + 0 \end{align}$$

We can use the above to write the gcd, 7, as a linear combination of 21 and 91 (it falls out in a single step this time):

$$7 = 1 \cdot 91 - 4 \cdot 21$$

So $x_1=-4$, $n_1=1$ is a solution to $21x_1 + 91n_1 = 7$

Now we can use this to find a solution to our original equation: $21x +91n = 14$. Simply multiply both $x_1$ and $n_1$ by 2 (since $14 = 2 \cdot 7$).

Thus $x=-8$, $n=2$ is a solution to $21x +91n = 14$

Adding the appropriate multiples to find all solutions from this one solution, we get

$$x=-8+\dfrac{91}{7}k \textrm{ and }n=2-\dfrac{21}{7}k$$

Simplifying, we find, $x=-8+13k$ and $n=2-3k$ gives all solutions to $21x +91n = 14$

Of course, we don't really care what $n$ is, since it doesn't appear in our original congruence. Further, if we are only considering the possible values of $x \pmod{91}$, there are only 7 that fit the $-8+13k$ form:

$$x \equiv 5, 18, 31, 44, 57, 70, \textrm{ and } 83 \pmod{91}$$

These are our solutions.