Example

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

$$72x \equiv 47 \pmod{200}$$

First, we translate things back into equation form.

$72x \equiv 47 \pmod{200}$ implies $47 - 72x = 200n$ for some integer $n$. This in turn, suggests that we can write 46 as a linear combination of 72 and 200: $$72x + 200n = 47$$ However, we have a problem!

The gcd of 72 and 200 is 2, which would imply that $72x+200n$ must be a multiple of 2. More precisely, we have $72x+200n = 2(36x+100n)$. But this is impossible, as that would imply that 2 is also a divisor of 47, which clearly is not the case.

Consequently, there is no solution to this linear congruence.