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

**dwsmith** · June 22nd 2011, 07:47 PM

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?

**topspin1617** · June 22nd 2011, 08:05 PM

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$ ?

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

LinkBack

Thread Tools

Display

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

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

Similar Math Help Forum Discussions

[SOLVED] if ra\equiv rb (mod m), then a\equiv b (mod \frac{m}{gcd(r,m)})

[SOLVED] x^2\equiv 1 (mod p) and x^2\equiv 1 (mod q), where p and q are distinct primes

[SOLVED] 2n^3+3n^2+n\equiv 0 (mod 6)

[SOLVED] if ab\equiv 0 (mod p), then a\equiv 0 (mod p) or b\equiv 0 (mod p).

[SOLVED] a \not\equiv b (mod m), then b \not\equiv a (mod m)

Search Tags