Results 1 to 4 of 4

Math Help - inverse using modulo congruence

  1. #1
    Member
    Joined
    Nov 2005
    Posts
    111

    inverse using modulo congruence

    Hi ,

    Please can you help me with this problem .
    I need to find the inverse of 2 modulo 11 using gcd(11,2) and modulo congruence.
    I know I can start like this:

    gcd(11,2)
    11 = 2*5 + 1
    2 = 1*2 + 0


    then I used modulo congruence:

    1=11 - 2*5 (mod 11)
    ....
    I know the answer is 6 mod 11. because I used another method.
    I want to know how to find it using modulo congruence.

    Please can you help me ?

    Thank you for your help
    B
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539
    Hello, braddy!

    I don't know if this what you want, but . . .


    I need to find the inverse of 2 (mod 11)

    We want to find x so that: . 2x\:=\:1 \pmod{11}

    Then: . 2x - 1 \:= \:11k . . . for some integer k.

    And we have: . x \:=\:\frac{11k+1}{2}

    The 'first' value of k which produces an integral x is: . k = 1

    . . which gives us: . x = 6


    Therefore, 6 is the multiplicative inverse of 2 \pmod{11}.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,668
    Thanks
    298
    Awards
    1
    Just a quick note.

    The reason the inverse HAD to exist in your case is that 11 is a prime. If you were, for instance using mod 10 (a composite number), a number does not need to have an inverse, or may have more than one. You can prove these statements using Soroban's method.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2005
    Posts
    111
    Quote Originally Posted by topsquark View Post
    Just a quick note.

    The reason the inverse HAD to exist in your case is that 11 is a prime. If you were, for instance using mod 10 (a composite number), a number does not need to have an inverse, or may have more than one. You can prove these statements using Soroban's method.

    -Dan
    Thank you topsquark and Soroban
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Modulo and congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 26th 2010, 05:10 PM
  2. congruence modulo twenty four
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: March 22nd 2010, 03:45 AM
  3. congruence modulo 2^n
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2009, 06:47 PM
  4. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 27th 2007, 07:59 PM
  5. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 22nd 2007, 03:57 PM

Search Tags


/mathhelpforum @mathhelpforum