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.

Printable View

- May 7th 2009, 07:13 AMShootTheBulletCongruences
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. - May 7th 2009, 07:25 AMGamma
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) - May 7th 2009, 07:33 AMTheEmptySet
- May 7th 2009, 03:26 PMTheAbstractionist
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