If $m$ and $a$ are co-prime positive integers then show that $ax \equiv b \pmod m$ has a solution, and any two solutions differ by a multiple of m.

Question

If $m$ and $a$ are co-prime positive integers then show that $ax \equiv b \pmod m$ has a solution, and any two solutions differ by a multiple of m.

I begun by using the definition of co-prime integers, s.t $au + mv = 1$. But I have no idea what to do next.

Answer 1

Hint: Reducing $au+mv=1$ modulo $m$ gives us $$au \equiv 1 \mod m$$ Thus, $u$ is a solution to $ax \equiv 1 \mod m$. How can you modify this to give you a solution to $ax\equiv b \mod m$?

Answer 2

Since $\gcd(a,m)=1$, we have that $a^{-1}\bmod m$ exists (i.e. the modular multiplicative inverse of $a$ mod $m$), so $ax\equiv b\pmod{m}\iff x\equiv ba^{-1}\pmod{m}$ is the unique solution mod $m$.

Answer 3

Another perhaps more primitive attempt:

Consider the product $ax_n$ for $x_n=0,1…m-1$. If b is between and including 0 and m-1 then there must be one $x_k$ so that $ax_k=b$ (mod m). Otherwise there must be (at least) one other number c different from b, with two different number $x_k$ and $x_l$ such that $ax_k=ax_l = c $ (mod m), that is $ax_k-ax_l=a(x_k-x_l)=0=m $ (mod m) but a and m are coprime which a contradiction, so the unique solution must exist that is $x_k=x_l$ (mod m) and $x_k=x_l +nm$.