Example

Solve the following linear congruence

$$66x \equiv 100 \pmod{121}$$

First, we translate things back into equation form.

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

The gcd of 66 and 121 is 11, which would imply that $66x-121n$ must be a multiple of 11. More precisely, $66x-121n = 11(6x-11n)$. But this is impossible, as that would imply that 11 is also a divisor of 100, which clearly is not the case.

Consequently, there is no solution to this linear congruence.