Use of GCD when solving linear equations in a ring of integers

Question

I know that when I'm solving a linear equation of the form ax = b (mod n), the gcd(a,n) tells me how many solutions there are. I don't really understand why this is. More than a proof, I'm interested in an explanation that will help me understand the relation between the gcd and number of solutions. Also, why does the gcd need to divide b for there to exist solutions?

Thanks

Answer 1

The equation $ax \equiv b \bmod m$ has a solution iff $d \mid b$, where $d=\gcd(a,m)$.

Assume $d \mid b$. Divide everything by $d$ and get $a'x \equiv b' \bmod m'$. Now $\gcd(a',m')=1$ and so the new equation has a unique solution. This solution mod $m'$ can be lifted to $d$ solutions mod $m$: $x,x+m',x+2m',\dots, x+(d-1)m'$.