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.

Printable View

- May 7th 2009, 06:13 AMShootTheBulletCongruences
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. - May 7th 2009, 06: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:

$\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) - May 7th 2009, 06:33 AMTheEmptySet
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 (Clapping) - May 7th 2009, 02:26 PMTheAbstractionist
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.$