1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Inverses

  1. Oct 19, 2012 #1
    1. The problem statement, all variables and given/known data

    3.) For each of the following a mod n, find a≡1 mod n, i.e. find an integer
    x with ax≡1 mod n, or explain why such an integer does not exist:
    5' mod 11; (21)' mod 28; 2' mod 101; 4' mod 101:

    4.) Let n = 2k+1 be an odd number. What is 2'≡1 mod n? What happens
    when n = 2k is even? Now find the multiplicative inverse of 3 mod n:
    First suppose n = 3k + 2 for some k. What is 3' mod n? (It looks a
    lot like the answer for 2'.) If n = 3k + 1, find 3' mod n as follows.
    First find a number x such that 3x≡-1 mod n, and then note that
    3(-x)≡1 mod n; finally, write -x as a number between 0 and n - 1.
    What if n = 3k?

    2. Relevant equations

    ax+by=c, has a solution if gcd(a,b)|c

    Euclidean Algorithm

    3. The attempt at a solution

    So I'm just not sure I've done these problems the right way, or the most efficient way. My answers are often negative, but I figured since its congruence classes, when my answers are -x, it really means [-x] which should be okay? But is that a cop-out? Should I be trying to find representatives between zero and n? Question 4 seems to imply that, but I didn't exactly do the problem the way my teacher suggested, I did it how it made sense to me. So could someone check my work?

    Also, in Algebra in general I feel like I write my answers in a weird way or in an odd order. If it seems I've done that, please let me know how you would write your answers in a more elegant or simple to understand way.

    3) ax≡1 mod n → ax+kn=1
    gcd(5,11)= 1 = 11-2(5) → 5' mod 11= -k

    gcd(21,28)= 7 = 28-21. 7 does not dive 1, therefore no solution exists.

    gcd(2,101)= 1 = 101-50(2) → 2' mod 101= -50

    gcd(4,101)= 1 = 101-25(4) → 4' mod 101= -25

    4)n=2k +1, n is odd,
    2': gcd(2,2k+1)=1= (2k+1)+ (-k)(2) → 2' mod (2k+1)= -k

    n=2k
    2': gcd(2,2k)= 2. 2 does not divide 1→ solution does not exist.

    n=3k+2
    3': gcd(3,3k+2)= 1= 2(3k+2)+ (-2k-1)(3) → 3' mod (3k+2)= -2k-1

    n=3k+1
    3': gcd(3,3k+1)=1 = (3k+1)+ (-k)(3) → 3' mod (3k+1)= -k

    n=3k
    3': gcd(3,3k)= 3. 3 does not divide 1 → solution does not exist.
     
  2. jcsd
  3. Oct 19, 2012 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I didn't check every part but it looks generally ok to me. Take the first one. You wrote 5' mod 11= -k, I think you meant 5' mod 11= -2, i.e. that the multiplicative inverse of 5 is -2. That works fine. (-2)*5=(-10)=1 mod 11. You could also express that as a nonnegative value if you want. [-2]=[9] mod 11. So 9*5=45=1 mod 11. Both work fine.
     
    Last edited: Oct 19, 2012
  4. Oct 20, 2012 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    A very simple minded way to find the inverse of 5, mod 11:
    There is no integer x such that 5x= 1 so look at 11+ 1= 12.
    There is no integer x such that 5x= 12 so look at 12+ 11= 23.
    There is no integer x such that 5x= 23 so look at 23+ 11= 34.
    There is no integer x such that 5x= 34 so look at 34+ 11= 45.
    5(9)= 45 so x= 9 (mod 11).

    Do you mean "show that [itex]2^{-1}= 1 mod n[/itex]" rather than "What is"?

    [-x] mod n is the same as [n- x].

    Okay so what is k? Did you mean k= 2? Then saying that the inverse is -2 means it is in the same congruence class as 11- 2= 9.

    Yes, that is correct. If 21x= 1 (mod 28) then 21x= 1+ 28n. That is the same as 21x- 28n= 7(3x- 4n) cannot be equal to 1 because 1 is not divisible by 7.

    Yes, this is correct. And -50 is in the same congrunce class as 101- 50= 51. 2(51)= 102= 1 (mod 101).

    Yes, this is correct. And -25 is in the same congruence class as 101- 25= 76. 4(76)= 304= 3(101)+ 1.

    And, of course, -k= (2k- 1)- k= k+ 1 mod 2k+ 1. (k+1)(2)= 2k+ 2= (2k+ 1)+ 1.

    Yes, for any integer, i, 2i+ m(2k)= 2(i+ mk) is even while 2k+ 1 is odd.

     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modular Inverses
  1. Modular arithmetic (Replies: 3)

  2. Modular arithmetic (Replies: 3)

  3. Modular arithmetic (Replies: 6)

  4. Modular Arithmetic (Replies: 23)

  5. Modular arithmetic (Replies: 3)

Loading...