Hi, I'm looking for any help towards showing the following:
given a and m are coprime, prove that ax 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:
(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
(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
(mod m)
Hi ShootTheBullet.
Let’s put together Gamma’s solution and TheEmptySet’s solution.
So you know that there are integers such that Substituting in the congruence equation gives so is a solution.
Suppose is another solution, so Thus divides divides since Hence the solution to is unique up to congruence modulo