# if (a,m)=1, then ax\equiv 1 (mod m) has a unique sol.

• Jun 22nd 2011, 08:47 PM
dwsmith
if (a,m)=1, then ax\equiv 1 (mod m) has a unique sol.
if $(a,m)=1$, then $ax\equiv 1 \ (\text{mod} \ m)$ has a unique sol.

By Bezout, there exist $x,y\in\mathbb{Z}$ such that $1=ax+my$

Now, we can write that as:

$my=1-ax\Rightarrow m(-y)=ax-1\Rightarrow ax\equiv 1 \ (\text{mod} \ m)$

Correct?
• Jun 22nd 2011, 09:05 PM
topspin1617
Re: if (a,m)=1, then ax\equiv 1 (mod m) has a unique sol.
Hmm...

I don't know about that. What we are trying to prove is that there is a unique value for $x$ (up to congruence modulo $m$) satisfying $ax\equiv 1\,(\mathrm{mod}\,m)$ (where $a,m$ are fixed). I don't think that what you have done gives us the uniqueness.

Try this: suppose there exist $x,y$ such that $ax\equiv ay\equiv 1\,(\mathrm{mod}\,m)$. We try to prove that $x\equiv y\,(\mathrm{mod}\,m)$.

It's fairly simple: what happens if you multiply the congruence $ax\equiv 1\,(\mathrm{mod}\,m)$ by $y$?