Hi, I'm looking for any help towards showing the following:
given a and m are coprime, prove that ax $\displaystyle \equiv$ b (mod m) has a unique solution mod m.
Any help would be much appreciated, and thank you for your time.
Lemma:
If gcd(a,m)=1, then there is a unique inverse to a mod m. That is there is a unique solution to:
$\displaystyle ax\equiv 1$ (mod m)
Proof
By the Euclidean Algorithm, you know there exist integers x and y such that
ax + my=1
Reduce mod m and we see
$\displaystyle ax\equiv 1$ (mod m)
as desired.
Uniqueness of this solution mod m comes from solving this diophantine equation. There are an infinite number of solutions to this equation ax +my = 1 if (a,m)=1 but they should all be congruent mod m. Alternatively if you know what a group is this is just the multiplicative group of units for the integers modulo m and as we all know inverses in a group are uniqe.
To solve your question, simply take the unique inverse that I found above and multiply it by b, multiplication is well defined, so this is the unique answer to the equation
$\displaystyle ax \equiv b $ (mod m)
Since a,m are coprime there exists integers r,s such that
$\displaystyle sa+rm=1 \iff sa=1-rm$
and we know (by definition) that
$\displaystyle ax-b=mq_1$ for some $\displaystyle q_1 \in \mathbb{Z}$
Multiply this by s to get
$\displaystyle sax-sb=msq_1$ Now sub in the above result to get
$\displaystyle (1-rm)x-sb=msq_1 \iff x-srm-sb=msq_1$
$\displaystyle x-sb=srm+msq_1 \iff x-sb=m(sr+sq_1)$
Since the integers are closed under ops we get
$\displaystyle x-sb =mq_2 \iff x=sb \mod(m)$
so it has a solution
Hi ShootTheBullet.
Let’s put together Gamma’s solution and TheEmptySet’s solution.
So you know that there are integers $\displaystyle r,s$ such that $\displaystyle rm+sa=1.$ Substituting $\displaystyle x=sb$ in the congruence equation gives $\displaystyle asb=b-brm\equiv b\pmod m$ so $\displaystyle x=sb$ is a solution.
Suppose $\displaystyle x'$ is another solution, so $\displaystyle ax'\equiv b\pmod m.$ Thus $\displaystyle a(x-x')\equiv0\pmod m\ \implies\ m$ divides $\displaystyle a(x-x')\ \implies\ m$ divides $\displaystyle x-x'$ since $\displaystyle \gcd(m,a)=1\ \implies\ x'\equiv x\pmod m.$ Hence the solution to $\displaystyle ax\equiv b\pmod m$ is unique up to congruence modulo $\displaystyle m.$