Let \(g=(a,m)\). If \(ax ≡ b \mod m\), then:
$$ ax = b + mk \text{ where } k \in \mathbb{Z} $$$$ ax - mk = b $$
If \(g\) is the greatest common divisor of \(a\) and \(m\), then \(g\) can divide any linear combination of \(a\) and \(m\) (proof). However, if \(g \nmid b\), then \(b\) is not a linear combination of \(a\) and \(m\), so no valid value of \(x\) and \(k\) can exist.