Finding solutions to congruence equations
In my notes it has a theorem, stating: $ax\equiv b\mod m$ has solutions if and only if $\gcd(a,m)|b$. The proof going from right to left is:
If $d=\gcd(a,m)$, $d|b \Rightarrow b=td$. We write $d=ra+sm$ for $r,s\in\mathbb{Z}$ so $b=t(ra+sm)=tra+tsm\equiv (tr)a\mod m$, so $x=tr$ is a solution.
Why is $x=tr$ a solution?
Solution 1:
You want to find $x$ such that $ax+km=b$ for some $k$.
$d=ra+sm$ is a divisor of $b=td$,
Since $tsm\equiv 0$ mod $m$, we see that $ra+sm\equiv ra$ mod $m$.
Therefore, as wanted, $ax=a(tr)\equiv b$ mod $m$.