Solution to linear congruences

Question

This document states the following theorem:

Let $m>1$, $a$ and $b$ be integers. Then $ax \equiv b \pmod m$ has a solution if and only if $gcd(a, m)$ divides $b$.

I thought $ax \equiv b \pmod m$ has a solution if and only if $gcd(a, m)=1$. Isn't $ax \equiv b \pmod m$ solved by $x \equiv a^{-1}\cdot b \pmod m$? If $gcd(a, m) \neq 1$, then the inverse doesn't exist.

Answer 1

See the entry in Wikipedia: "Linear congruence theorem."

What you might be recalling is the fact that $a$ is not the inverse of $x$ unless $\gcd (a, b) = 1$.

But here, we have that the following applies:

IF $d = \gcd (a,m) > 1$, then $d\mid b$ and $${\small \dfrac ad }x\equiv {\small \dfrac bd} \left(\mod \small\frac md\right)$$

Answer 2

Suppose that $gcd(a,m)=d$ and $d\mid b$. Then, you have $\frac{a}{d}x\equiv \frac{b}{d} \mod \frac{m}{d}$. Here $gcd(\frac{a}{d},\frac{m}{d})=1$ and therefore the last congruence has a solution $y$ and therefore $dy$ is the solution of ${a}x\equiv {b} \mod {m}$.