Example

Solve the following linear congruence:

$$8x \equiv 6 \pmod{14}$$

First, we translate things back into an equation form.

$8x \equiv 6 \pmod{14}$ implies $8x - 6 = 14n$ for some integer $n$. This in turn, suggests that we can write 6 as a linear combination of 8 and 14: $$8x - 14n = 6$$ By inspection, we note that the gcd of 8 and 14 is 2, so we verify that 6 is a multiple of 2, 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: $8x_1 - 14n_1 = 2$, using the Euclidean algorithm.

$$\begin{align} 14 &= 1 \cdot 8 + 6\\ 8 &= 1 \cdot 6 + \fbox{2} \leftarrow \textrm{gcd}\\ 6 &= 3 \cdot 2 + 0 \end{align}$$

Now writing the gcd, 2, as different linear combinations, we find:

$$\begin{align} 2 &= 8 - 6\\ &= 8 - (14-8)\\ &= 2 \cdot 8 - 1 \cdot 14\\ \end{align}$$

So $x_1=2$, $n_1=1$ is a solution to $8x_1 - 14n_1 = 2$

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

Thus $x=6$, $n=3$ is a solution to $8x - 14n = 6$

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

$$x=6+\dfrac{14}{2}k \quad \textrm{ and } \quad n=3+\dfrac{8}{2}k$$

Simplifying, we find, $x=6+7k$ and $n=3+4k$ gives all solutions to $8x - 14n = 6$

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{14}$, there are only two that fit the $6+7k$ form: $x \equiv 6 \textrm{ or } 13 \pmod{14}$. These are our solutions.