Example

Determine the incongruent solutions, if they exist, to the following:

$$4183x \equiv 5781 \pmod{15087}$$

First, we translate things back into equation form.

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

$$4183x + 15087n = 5781$$

It is not clear by inspection, what the gcd of 4183 and 15087 is, so we proceed with the Euclidean algorithm to find out.

$$\begin{align} 15087 &= 3 \cdot 4183 + 2538\\ 4183 &= 1 \cdot 2538 + 1645\\ 2538 &= 1 \cdot 1645 + 893\\ 1645 &= 1 \cdot 893 + 752\\ 893 &= 1 \cdot 752 + 141\\ 752 &= 5 \cdot 141 + \fbox{47} \leftarrow \textrm{gcd}\\ 141 &= 3 \cdot 47 + 0 \end{align}$$

This tells us that the gcd of 4183 and 15087 is 47, so we verify that 5781 is a multiple of 47, which it is ($5781 = 123 \cdot 47$). We are thus guaranteed some solution, so we continue. We will first try to find a single solution to the intermediate equation: $4183x_1 + 15087n_1 = 47$, using the results of the Euclidean algorithm above.

$$\begin{align} 47 &= 752 - 5 \cdot 141\\ &= 752 - 5 \cdot (893 - 752)\\ &= 6 \cdot 752 - 5 \cdot 893\\ &= 6 \cdot (1645 - 893) - 5 \cdot 893\\ &= 6 \cdot 1645 - 11 \cdot 893\\ &= 6 \cdot 1645 - 11 \cdot (2538 - 1645)\\ &= 17 \cdot 1645 - 11 \cdot 2538\\ &= 17 \cdot (4183 - 2538) - 11 \cdot 2538\\ &= 17 \cdot 4183 - 28 \cdot 2538\\ &= 17 \cdot 4183 - 28 \cdot (15087 - 3 \cdot 4183)\\ &= 101 \cdot 4183 - 28 \cdot 15087 \end{align}$$

So $x_1=101$, $n_1=-28$ is a solution to $4183x_1 + 15087n_1 = 47$

Now we can use this to find a solution to our original equation: $4183x +15087n = 5781$. Simply multiply both $x_1$ and $n_1$ by 123 (since $5781 = 123 \cdot 47$).

Thus $x=12423$, $n=-3444$ is a solution to $4183x +15087n = 5781$

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

$$x=12423+\dfrac{15087}{47}k \textrm{ and }n=-3444-\dfrac{4183}{47}k$$

Simplifying, we find, $x=12423+321k$ and $n=-3444-89k$ gives all solutions to $4183x +15087n = 5781$

Of course, we don't really care what $n$ is, since it doesn't appear in our original congruence. Further, we are only considering the possible values of $x \pmod{15087}$, of which there are 47 that fit the $12423+321k$ form. Given the large number of solutions, we don't list them all. Instead, we can simply write our solution as:

$$x \equiv 12423 + 321k \pmod{15087} \textrm{, where $k$ is any integer}$$

If we want an even tighter form, we might subtract off as many 321's from 12423 as we can without going negative, so that smaller numbers are used:

$$x \equiv 225 + 321k \pmod{15087} \textrm{, where $k$ is any integer}$$