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

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

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

Now, we can write that as:

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

Correct?
• Jun 22nd 2011, 08: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 $\displaystyle x$ (up to congruence modulo $\displaystyle m$) satisfying $\displaystyle ax\equiv 1\,(\mathrm{mod}\,m)$ (where $\displaystyle a,m$ are fixed). I don't think that what you have done gives us the uniqueness.

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

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