Thread: Congruences

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)

Originally Posted by ShootTheBullet

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.

Since a,m are coprime there exists integers r,s such that



and we know (by definition) that

for some

Multiply this by s to get

Now sub in the above result to get





Since the integers are closed under ops we get



so it has a solution

Originally Posted by ShootTheBullet

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.

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