Necessity of the condition $\gcd(a,n)$ divides $b$ for solving $ax\equiv b\pmod{n}$?

Question

I was wondering if someone could give me some more intuition on why we need that $\gcd(a,n)$ divides $b$ when we want to solve $ax\equiv b\pmod{n}$?

Answer 1

Hint $ $ If solvable then $\ ax+cn = b\ $ so $\,d\mid a,n\,\Rightarrow\, d\mid b,\,$ i.e. a common divisor $\,d\,$ of $\,a,n\,$ must divide $\,b\,$ if a solution $\,x\,$ exists.

Answer 2

If $d\mid n$ there are well-defined projection maps $x\bmod n\mapsto x\bmod d$. If $ax\equiv b$ mod $n$ and we reduce the equation mod $g:=\gcd(a,d)$, the equation becomes $0\equiv b\bmod g$, i.e. $g\mid b$.

Answer 3

This congruence is solvable if there exists an integer $y$ such that $b=ax+ny$. Now the ideal $(a, n)$, by definition, is generated by $\gcd(a,n)$.