Example

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

$$1537x \equiv 2863 \pmod{6731}$$

First, we translate things back into equation form.

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

$$1537x + 6731n = 2863$$

It is not clear by inspection what the gcd of 1537 and 6731 is, so we appeal to the Euclidean algorithm:

$$\begin{align} 6731&= 4 \cdot 1537+ 583\\ 1537&= 2 \cdot 583+ 371\\ 583&= 1 \cdot 371+ 212\\ 371&= 1 \cdot 212+ 159\\ 212&= 1 \cdot 159+ \fbox{53} \leftarrow \textrm{gcd}\\ 159&= 3 \cdot 53+ 0 \end{align}$$

So the gcd of 1537 and 6731 is 53.

However, we have a problem!

This value for the gcd implies that $1537x + 6731n$ must be a multiple of 53. More precisely, $1537x - 6731n = 53(29x+127n)$. But this is impossible, as that would imply that 53 is also a divisor of 2863, which is not the case (2863/53 leaves a remainder of 1).

Consequently, there is no solution to this linear congruence.