Modular arithmetic and linear congruences

Assuming a linear congruence:

$ax\equiv b \pmod m$

It's safe to say that one solution would be:

$x\equiv ba^{-1} \pmod m$

Now, the first condition i memorized for a number $a$ to have an inverse $mod(m)$ was:

$\gcd(a,m) = 1$

Which stems from the fact (and correct me here) that a linear congruence has solution if that gcd divides $b$. Since on an inverse calculation we have:

$ax\equiv 1 \pmod m$

The only number that divides one is one itself, so it makes sense.

Now comes the part that annoys me most:

"If the condition that tells us that there is an inverse $mod (m)$ for $a$ says that $\gcd(a,m)=1$, then how come linear congruences where the $\gcd(a,m) \ne 1$ have solution? Why do we say that a linear congruence where $\gcd(a,m) = d > 1$ has d solutions? If you can't invert $a$, then you can't do this:"

$ax\equiv b \pmod m \implies x\equiv ba^{-1} \pmod m$

Please help on this one. It's kinda tormenting me :(

Answer

The long and the short of it is: $ax \equiv b \pmod m$ has solutions iff $\gcd(a,m)$ divides $b$.

As you said, if $\gcd(a,m) = 1$, then we can multiply by the inverse of $a$ to get our (unique!) solution.

But if $\gcd(a,m) = d > 1$, we still have a chance at finding solutions, even though there is no inverse of $a$ mod $m$.

---

Assume $d \mid b$.

Then there are integers $a', m', b'$ such that $a = da'$, $b = db'$, and $m = dm'$.
$$ax \equiv b \pmod m \iff a'x \equiv b' \pmod{m'}$$

But since $d$ was the GCD of $a$ and $m$, we know $\gcd(a', m') = 1$, and we can construct a solution mod $m'$. For notation's sake, let $c$ be an integer such that $ca' \equiv 1 \pmod {m'}$.
$$a'x \equiv b' \pmod{m'} \iff x \equiv b' c \pmod {m'}$$

Now we can "lift" our solution mod $m'$ to many solutions mod $m$.:
$$x \equiv b' c \pmod {m'} \iff \exists k \quad x \equiv b'c + km' \pmod m$$

---

Say there is a solution to the congruence. Then $ax \equiv b \pmod m$ implies that for some $k$, $ax + km = b$. But if $d$ divides $a$ and $m$, it must also divide $b$.

---

So it is a necessary and sufficient condition.