Results 1 to 3 of 3
Like Tree2Thanks
  • 2 Post By emakarov

Math Help - Existence of a multiplicative inverse

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,839
    Thanks
    320
    Awards
    1

    Existence of a multiplicative inverse

    A quick question this time. I have a number n and number a. Both positive integers such that 1 \leq a \leq n.

    How can I prove the existence of a number c such that ac \equiv 1 \text{ (mod n)}

    Obviously I can't use the Euclidean algorithm since I have no specific relation between a and n. How can I prove existence of c? (Or can't I?)

    Thanks!

    -Dan
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Existence of a multiplicative inverse

    ac\equiv 1\pmod{n} iff there exists an integer d such that ac + nd = 1. But it is known that the set of linear combinations of two numbers coincides with the set of multiples of their GCD. (The GCD can be expressed as a linear combination through the Euclidean algorithm, and every linear combination is a multiple of the GCD.) Thus, a has a multiplicative inverse mod n iff GCD(a, n) = 1.
    Thanks from HallsofIvy and topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,839
    Thanks
    320
    Awards
    1

    Re: Existence of a multiplicative inverse

    Quote Originally Posted by emakarov View Post
    ac\equiv 1\pmod{n} iff there exists an integer d such that ac + nd = 1. But it is known that the set of linear combinations of two numbers coincides with the set of multiples of their GCD. (The GCD can be expressed as a linear combination through the Euclidean algorithm, and every linear combination is a multiple of the GCD.) Thus, a has a multiplicative inverse mod n iff GCD(a, n) = 1.
    (sighs) You know, I worked that problem for more than 2 hours. Then I figured it out about 15 minutes later as I was leaving my house. Grrrrrr...

    Thanks for the help!

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Multiplicative Inverse
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 13th 2012, 11:02 PM
  2. Multiplicative Inverse
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2011, 11:48 AM
  3. Existence of a Multiplicative Identity
    Posted in the Calculus Forum
    Replies: 8
    Last Post: April 28th 2010, 07:56 PM
  4. multiplicative inverse
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 23rd 2010, 01:31 PM
  5. Multiplicative inverse 71.7
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 26th 2009, 09:34 AM

Search Tags


/mathhelpforum @mathhelpforum