Results 1 to 2 of 2

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

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    10

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2010
    Posts
    193

    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$?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] if ra\equiv rb (mod m), then a\equiv b (mod \frac{m}{gcd(r,m)})
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jun 15th 2011, 08:04 AM
  2. Replies: 2
    Last Post: Jul 10th 2010, 05:14 PM
  3. [SOLVED] 2n^3+3n^2+n\equiv 0 (mod 6)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jul 8th 2010, 11:44 PM
  4. [SOLVED] if ab\equiv 0 (mod p), then a\equiv 0 (mod p) or b\equiv 0 (mod p).
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jul 7th 2010, 04:21 PM
  5. [SOLVED] a \not\equiv b (mod m), then b \not\equiv a (mod m)
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Jul 5th 2010, 02:44 AM

Search Tags


/mathhelpforum @mathhelpforum