# Congruences

• May 7th 2009, 06:13 AM
ShootTheBullet
Congruences
Hi, I'm looking for any help towards showing the following:

given a and m are coprime, prove that ax $\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 AM
Gamma
Lemma:
If gcd(a,m)=1, then there is a unique inverse to a mod m. That is there is a unique solution to:
$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
$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
$ax \equiv b$ (mod m)
• May 7th 2009, 06:33 AM
TheEmptySet
Quote:

Originally Posted by ShootTheBullet
Hi, I'm looking for any help towards showing the following:

given a and m are coprime, prove that ax $\equiv$ 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

$sa+rm=1 \iff sa=1-rm$

and we know (by definition) that

$ax-b=mq_1$ for some $q_1 \in \mathbb{Z}$

Multiply this by s to get

$sax-sb=msq_1$ Now sub in the above result to get

$(1-rm)x-sb=msq_1 \iff x-srm-sb=msq_1$

$x-sb=srm+msq_1 \iff x-sb=m(sr+sq_1)$

Since the integers are closed under ops we get

$x-sb =mq_2 \iff x=sb \mod(m)$

so it has a solution (Clapping)
• May 7th 2009, 02:26 PM
TheAbstractionist
Quote:

Originally Posted by ShootTheBullet
Hi, I'm looking for any help towards showing the following:

given a and m are coprime, prove that ax $\equiv$ 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 $r,s$ such that $rm+sa=1.$ Substituting $x=sb$ in the congruence equation gives $asb=b-brm\equiv b\pmod m$ so $x=sb$ is a solution.

Suppose $x'$ is another solution, so $ax'\equiv b\pmod m.$ Thus $a(x-x')\equiv0\pmod m\ \implies\ m$ divides $a(x-x')\ \implies\ m$ divides $x-x'$ since $\gcd(m,a)=1\ \implies\ x'\equiv x\pmod m.$ Hence the solution to $ax\equiv b\pmod m$ is unique up to congruence modulo $m.$