Results 1 to 2 of 2

Math Help - Inverse Modulus Proof

  1. #1
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Inverse Modulus Proof

    Show that an inverse of a modulo m does not exist if gcd(a, m) > 1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by aaronrj View Post
    Show that an inverse of a modulo m does not exist if gcd(a, m) > 1.
    b is an inverse of a modulo m if ab \equiv 1 (\bmod m)

    This means we have : ab=1+mk where k is an integer. i.e. ab-mk=1

    By Bézout's identity, we know that :
    \exists u,v \in \mathbb{Z} \text{ such that } au+bv=1 \Leftrightarrow \text{gcd}(a,b)=1
    it appears in the French wikipedia and I've been taught this, but I don't know where to find it in English (not in wikipedia nor in mathworld). If you want a proof, tell me.

    And you're done.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: November 25th 2011, 11:53 AM
  2. Inverse Modulus
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 9th 2011, 06:19 AM
  3. Modulus Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 13th 2010, 01:15 PM
  4. Proof of the modulus and Amplitude
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: April 5th 2009, 09:57 PM
  5. Inverse and Modulus Functions help please! D:
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 24th 2008, 03:53 AM

Search Tags


/mathhelpforum @mathhelpforum