Results 1 to 3 of 3

Math Help - Multiplicative Inverses

  1. #1
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722

    Multiplicative Inverses

    Righto, i had to miss a lecture and the notes are just of skeleton form so they don't explain things well. Could someone tell me whats going on here from a tutorial Q i have.

    6.1 - Find the multiplicative inverses of the non-zero elements in Z_7. (Just experimenting is probably easier than
    using the Euclidean algorithm.)
    hint/solution 6.1 - By experiment, 2.4 = 1, 3.5 = 16.6 = 1 and so 2,4 are
    mutually inverse as are 3,5. The element 6 is its own inverse.

    I assume the algorithm in question is the GCD one, but surely that means 16,6 and 2,4 would be 2..?

    So... Whats going on here?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,860
    Thanks
    742
    Hello, Deadstar!

    Here's an algebraic approach to this problem.


    6.1 - Find the multiplicative inverses of the non-zero elements in Z_7.

    In any system: . 1\cdot1 \equiv 1 \pmod{n}
    . . 1 is its own inverse.


    Inverse of 2

    We want: . 2x \:\equiv\:1 \pmod 7

    . . That is: . 2x \:=\:7n+1 . . . 2x is one more than a multiple of 7.

    . . Then: . x \:=\:\frac{7n+1}{2} \:=\:3n + \frac{n+1}{2}

    Since x is a positive integer, n+1 must be divisible by 2.
    The first time this happens is when n = 1

    Hence: . x \:=\:3(1) + \frac{1+1}{2} \:=\:4

    Therefore, 4 is the inverse of 2 ... and 2 is the inverse of 4.


    Inverse of 3

    We want: . 3x \:\equiv\:1 \pmod 7

    . . That is: . 3x \:=\:7n+1 . . . 3x is one more than a multiple of 7.

    . . Then: . x \:=\:\frac{7n+1}{3} \:=\:2n + \frac{n+1}{3}

    Since x is a positive integer, n+1 must be divisible by 3.
    The first time this happens is when n = 2

    Hence: . x \:=\:2(2) + \frac{2+1}{3} \:=\:5

    Therefore, 5 is the inverse of 3 ... and 3 is the inverse of 5.


    Inverse of 6

    We want: . 6x \:\equiv\:1 \pmod 7

    . . That is: . 6x \:=\:7n+1 . . . 6x is one more than a multiple of 7.

    . . Then: . x \:=\:\frac{7n+1}{6} \:=\:n + \frac{n+1}{6}

    Since x is a positive integer, n+1 must be divisible by 6.
    The first time this happens is when n = 5

    Hence: . x \:=\:5 + \frac{5+1}{6} \:=\:6

    Therefore, 6 is its own inverse.



    . . . . \begin{array}{|c|c|} \hline<br />
\text{Number} & \text{Inverse} \\ \hline<br />
 1 & 1 \\ 2 & 4 \\ 3 & 5 \\ 4 & 2 \\ 5 & 3 \\ 6&6 \\ \hline \end{array}

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,201
    Thanks
    1789
    Quote Originally Posted by Deadstar View Post
    Righto, i had to miss a lecture and the notes are just of skeleton form so they don't explain things well. Could someone tell me whats going on here from a tutorial Q i have.

    6.1 - Find the multiplicative inverses of the non-zero elements in Z_7. (Just experimenting is probably easier than
    using the Euclidean algorithm.)
    hint/solution 6.1 - By experiment, 2.4 = 1, 3.5 = 16.6 = 1 and so 2,4 are
    mutually inverse as are 3,5. The element 6 is its own inverse.

    I assume the algorithm in question is the GCD one, but surely that means 16,6 and 2,4 would be 2..?

    So... Whats going on here?
    They said they are NOT using the Euclidean algorithm, "just experimenting". When they say 2.4= 1, 3.5= 16.6= 1, they are talking about the LCD but really mean the product: 2.4= 8=7+ 1 so is 1 mod 7. 3*5= 15= 2*7+1 so is 1 mod 7. I have no idea what the "16.6" is about! Perhaps they meant 6.6 and the "1" is a misprint: 6*6= 36= 5*7+1 so is 1 mod 7.

    If they DID use the Euclidean Algorithm to find the mulitplicative inverse of, say, 6 mod 7, what they would have done would be
    "iIf n is the multiplicative inverse of 6, mod 7, then 6n= 1 mod 7 which means 6n= 7m+ 1 for some integer m. That is the same as the Diophantine equation 6n- 7m= 1. Clearly that is true for m= n= -1 but it is also true for an m= -1+ 6k, n= -1+ 7k (because the "k" terms will cancel in the equation). Taking k= 1, m= 5 and n= 6: 6(6)- 5(7)= 1 so 6(6)= 5(7)+ 1. Of course, for small numbers it is, as they say, easier just to "experiment": 6(2)= 12= 5 mod 7; no. 6(3)= 18= 4 mod 7; no, 6(4)= 24= 3 mod 7; no, 6(5)= 30= 2 mod 7; no, 6(6)= 36= 1 mod 7. That's the one!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: June 15th 2011, 09:14 PM
  2. Replies: 2
    Last Post: March 8th 2010, 06:25 PM
  3. Prove their own multiplicative inverses
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 3rd 2010, 12:25 AM
  4. Multiplicative inverses in field extensions
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 18th 2010, 09:10 PM
  5. MOre Multiplicative inverses
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 29th 2009, 10:12 PM

Search Tags


/mathhelpforum @mathhelpforum