No solution to congruence if no inverse exists? If $ax \equiv b \pmod{c}$, then if $\gcd(a, c) \ne 1$, there is no $a^{-1} \pmod{c}$. Can we conclude no solution exists for $x$?
 A: No. Consider $2x\equiv 4\pmod 6$.
A: Just to make things clear, the following are equivalent


*

*$a x \equiv b \pmod{c}$ has a solution $x$, and

*$\gcd(a, c) \mid b$.


If $x$ is a solution of (1), then there is $t$ such that $a x = b + t c$, so $b = a x - t c$ and $\gcd(a, c) \mid b$.
Conversely, if $\gcd(a, c) \mid b$, then use Bézout to get $u, v$ such that
$$
a u + c v = \gcd(a, c),
$$
and then multiply by the integer
$$
\frac{b}{\gcd(a, c)}
$$
to get
$$
a u \frac{b}{\gcd(a, c)} + c v \frac{b}{\gcd(a, c)} = \gcd(a, c) \frac{b}{\gcd(a, c)} = b,
$$
to get that
$$
x = u \frac{b}{\gcd(a, c)}
$$
is a solution to (1).
So for instance $\gcd(4, 6) = 2 \ne 1$, still the equation
$$
4 x = 2 \pmod{6}
$$
has a solution $x = 2$.
A: $\begin{align} {\rm Generally}\ \ &\exists x\!:\ ax\equiv b\!\!\pmod c\iff (a,c)\mid b\\
\\
{\rm e.g.} \quad  &\exists x\!:\ ax\equiv 1\!\!\pmod c\iff (a,c)\mid 1 \ \ \ {\rm is\  said\ special\ case\ on\ invertibility} \end{align}\ $
Said in words:  $\,\ a\,$ is invertible mod $\,c\,\ $ iff $\,\ a,c\,$ are coprime.
The key to the proof is Bezout's identity for the gcd, which may be expressed as follows
$$ a\Bbb Z + c\Bbb Z \, =\, (a,c)\,\Bbb Z\ $$
Thus $\ \exists x\!:\ ax\equiv b\!\!\pmod c\iff b\in a\Bbb Z + c\Bbb Z \, =\, (a,c)\,\Bbb Z\iff (a,c)\mid b$
A: Only if $\gcd (a,c) \not \mid b $.
If $ax \equiv b\mod c $ then it's pretty easy to see that $\gcd (a,c)|b $ (because $ax\equiv b\mod c\implies ax-b=kc\implies \gcd (a,c)|b $)  and it's very easy to set up such with equations such as $8x = 12 \mod 20$ where it does.
But any where it doesn't , say $8x \mod 14 \mod 20$, there is no solution. ($8x - 14 =20k\implies 4x-7=10\implies  2|7$.)
