Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problems with inverses in arithmetic in ring z

  1. Oct 15, 2010 #1
    1. The problem statement, all variables and given/known data
    Calculate 7*11 + 9*11^-1 in the group Z20


    2. Relevant equations



    3. The attempt at a solution
    77+ (9*1/11) in group Z20
    77 + 9/11
    17 +11x= 20mod+9
    My solution was 12, this makes 149 on both sides when you multiply the mod times 7.
    I am doing independent study and the computer program I am using says the answer is 16.
    What am I doing wrong? Btw, what is the difference between ring congruence arithmetic and regular congruence arithmetic? They seem pretty similar.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Oct 15, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'm not really sure what you are doing. What is 20mod+9 supposed to mean? At some point you need to figure out what 11^(-1) mod 20 is. Why not do it first?
     
  4. Oct 17, 2010 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You can 'bump' a post if no one has given any response. I don't think that's the case here.
     
  5. Oct 17, 2010 #4
    The first thing you absolutely need to do is to figure out what 11^-1 mod 20 is.
     
  6. Oct 17, 2010 #5
    original problem: calculate 7*11+9*11^-1 with mod 20

    So in order to figure out the inverse of 11^-1 mod 20, I would do the typical
    11x=mod 20+1, and from here would I go 17+99x=mod 20+1(I get 16 on this one, the supposedly correct solution), or some other route?
     
  7. Oct 18, 2010 #6

    HallsofIvy

    User Avatar
    Science Advisor

    To find the multiplicative inverse of 11 mod 20, you want a number, m, such that 11m= 1 (mod 20) or 11m= 1+ 20n for some integer n.

    That is the same as solving the diophantine equation 11m- 20n= 1.

    11 divides into 20 once with remainder 9: 20- 11= 9.

    9 divides into 11 once with remainder 2: 11- 9= 2.

    2 divides into 9 four times with remainder 1: 9- 4(2)= 1.

    Replace the "2" in that equation with 11- 9: 9- 4(11- 9)= 5(9)- 4(11)= 1.

    Replace the "9" in that equation with 20- 11: 5(20- 11)- 4(11)= 5(20)- 9(11)= 1.
    (Of course: 100- 99= 1.)

    A solution to 11m- 20n= 1 is m= -9, n= -5. Thus, the multiplicative inverse of 11, mod 20, is -9= 20- 9= 11 (mod 20). That is, the multiplicative inverse of 11, mod 20, is 11 itself.

    Check: 11(11)= 121= 6(20)+ 1= 1 (mod 20).
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook