Congruence proof $ax \equiv b $ mod $m$

Question

Prove that the congruence $ax \equiv b $ mod $m$ has a solution if and only if $d | b$, where $d = $gcd$(a,m)$

I thought about proving using the contrapositive that $d$ does not divide $b$, but i'm not sure that would really help and am stumped as to where to start.

Some help would be great!

Answer 1

The congruence means $$m\mid ax-b$$ which means that integers $x$ and $y$ exist such that $my=ax-b$ , hence $b=ax-my$. This diophantine equation has integer solutions if and only if $\gcd(a,m)$ divides $b$

Answer 2

If a solution $x_0$ exists, $\exists y\in\Bbb Z:ax_0-my=b$. Since $(a,m)$ divides both $a,m$, it must divide $b$.

Conversely, we know that $\exists p,q\in\Bbb Z:(a,m)=ap+mq$. if $b=k(a,m)=akp+mkq$, we have $m|ax-b=ax-akp-mkq$ for $x=kp$, which suggests the existence of a solution.