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!

Homework Help: Find the inverse of modulus 26

  1. Jul 12, 2014 #1
    1. The problem statement, all variables and given/known data
    [tex]
    \begin{pmatrix}
    5 & 8\\
    17 & 3\\
    \end{pmatrix}
    [/tex]

    The matrix given above is matrix A and I am trying to find A-1 mod 26 = ?


    2. Relevant equations
    ax+by = c


    3. The attempt at a solution
    Well first I found the det of A which is -121 and then took -121 modulus of 26 which gave me 9. Did I do the work that I UPLOADED for this part right? After that I set -121 = 9 mod 26. So now to find the inverse, I need the Euclidean algorithm, an here is where I get lost. First I put the mod number on the let of the equals sign then I multiplied 9 by some number not known yet and added some remainder. By dividing 26 by 9 I get that the number is 2 and the remainder is 8. Now I move 9 to replace 26 on the left and 8 to replace 9 on the left and a new unknown remainder. Now 8 goes into 9 once with a remainder of 1. Finally 8 will now move to the left and 1 will replace 1. Now if I divide 8 by 1 I get 8 so the number will be 8 with a 0 remainder. If this is confusing please use my UPLOADED WORK. All in all the equations will be:
    26 = 9(2) + 8
    9 = 8(1) + 1
    8 = 1(8) + 0
    My question is did I do it correctly or what did I do wrong?
     

    Attached Files:

  2. jcsd
  3. Jul 12, 2014 #2
    In case the upload wasn't clear I made it a bit darker.To be more clear I am confused because when I manipulate the equations I get:

    26 + 9(-2) = 8
    9 + 8(-1) = 1
    8 + 1(-8) = 0

    This doesn't make any sense to me because when I start making substitutions it gets weird thanks to the 0.

    PS Also real quick if any of you read this let me know if I have this in the wrong spot so I can move it.
     

    Attached Files:

  4. Jul 12, 2014 #3

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    To do what?
    26 and 9 are coprime, that's the result of the algorithm.
     
  5. Jul 12, 2014 #4
    Ok so should I just find the adjoin matrix? Then add 26 to the negatives to get the matrix if this is so then why is this not the answer in the book. In the book they solved it and found it to be 3 but they didn't show work.
     
  6. Jul 12, 2014 #5
    They then multiplys the inverse found to be 3 by the adjoint matrix A.
     
  7. Jul 12, 2014 #6
    This is what the book states exactly we can show that 9^-1 mod 26 = 3 because 9 x 3 = 27 mod 26 = 1. Therefore we compute the inverse of A as and then they proceed to find it. Where did they get 3
     
  8. Jul 12, 2014 #7

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    You know that A adj(A) = a diagonal matrix (but not the unit matrix). So c adj(A) is the inverse of A mod 26, for some integer c.

    Test if 26k+1 is divisible by 9, for k = 0, 1, 2, ....
     
  9. Jul 12, 2014 #8
    It is divisible at k=1 which is 3
     
  10. Jul 12, 2014 #9
    But what does this mean?
     
  11. Jul 13, 2014 #10
    So how did you know the 26k+1 deal gave 3? Also how would I do this -121 mod 26 or did I do this correctly above?
     
  12. Jul 13, 2014 #11

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    This means 9-1 = 3, as 9*3=1.

    If the question refers to something else, it would help if you put your work together instead of posting one sentence at a time (you can also edit your posts if you want to add something).
     
  13. Jul 13, 2014 #12
    Ok but why the 3 how would I know to do this on a test?
     
  14. Jul 13, 2014 #13

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    See post 7 from AlephZero.
    You have to multiple adj(A) by some number to get the unit matrix on the right side - and this is the inverse of the entries you have at the right side.
     
  15. Jul 13, 2014 #14
    I haven't read your text book, but I would just do the modulo 26 arithmetic:
    [tex]
    \begin{pmatrix}
    a & b\\
    c & d\\
    \end{pmatrix}
    \begin{pmatrix}
    5 & 8\\
    17 & 3\\
    \end{pmatrix}=
    \begin{pmatrix}
    1 & 0\\
    0 & 1\\
    \end{pmatrix}=
    \begin{pmatrix}
    5a+17b & 8a+3b\\
    5c+17d & 8c+3d\\
    \end{pmatrix}
    [/tex]
    5a+17b = 1
    8a+3b = 0
    5c+17d = 0
    8c+3d = 1

    So, for a & b you have 2 equations and two unknowns.
    And for c & d you have 2 equations and two unknowns.
     
  16. Jul 13, 2014 #15
    So I have a = -3/121 b = 8/121 c = 17/121 d=-5/121. So I set x times the adjoint matrix and set this equal to the unit matrix but I don't know how to determine the unit matrux?
     
  17. Jul 13, 2014 #16
    Thinking only in modulo 26, you say you have:
    a = 23/17 b = 8/17 c = 17/17 d=21/17
    Would that be right?

    And 17a=23, 17b=8, 17c=17, and 17d=21
    Right?

    Now work out your multiples of 17:
    17*0=0, 17*1=17, 17*2=8, 17*3=25, ...
    Are you there yet?
     
    Last edited: Jul 13, 2014
  18. Jul 13, 2014 #17
    Where are you getting this 23 and 17? As far as the math that you have performed as an example to me I can follow all of that, and to answer the question of "am I there yet". My answer would be, that the series preformed is good enough as 25 is one less than 26. So 17 is what we desire then?
     
  19. Jul 13, 2014 #18
    -3 + 26 = 23
    -5+26 = 21
    With modulo 26, I'm keeping everything in the range of 0 to 25. No negative numbers.

    You'll be there when you have the answer. Then we'll check the answer so that you understand it.

    It sounds as though you can follow everything up to "17a=23, 17b=8, 17c=17, and 17d=21". Is that true?

    But you don't know what to do with something like 17a=23. Is that correct?

    ---edit to add:
    If you haven't figured out what that table is, work out all 26 members of it. There's a 50:50 chance you catch on to its purpose before you finish. And if you don't, I'll be asking you about four of those 26 table entries.

    By the way, we are only 2 or 3 simple steps from the solution.
     
    Last edited: Jul 13, 2014
  20. Jul 13, 2014 #19
    Before we move on where did -3 and -5 come from? I guess that explains the 23 but where did 17 come from? I am sorry this is probably basic but I am lost.
     
  21. Jul 13, 2014 #20
    You gave me these:
    a = -3/121 b = 8/121 c = 17/121 d=-5/121

    There's a -3 and a -5 in there.

    All I did was to put everything in the range of 0 to 25 by adding or subtracting multiples of 26.

    ---Edit:
    Oh, the 17 is 121-(4*26)
     
  22. Jul 13, 2014 #21
    Ok well I get the -3 and -5 now and why you used 26 but now im confused on 121-(4*26) where is the 4?
     
  23. Jul 13, 2014 #22
    121-(1*26) = 95 (no good, need 0 to 25)
    121-(2*26) = 69 (still no good)
    121-(3*26) = 43
    121-(4*26) = 17 (yeay!!)

    What you can do is 121/26 = 4 and a fraction.
     
  24. Jul 13, 2014 #23
    I'll be around for another 5 minute - then I'll be back in about 90 minutes.
    All we're doing is implementing modulo 26 when we go
    from: a = -3/121, b = 8/121, c = 17/121, d=-5/121
    to: a = 23/17 b, = 8/17, c = 17/17, d=21/17

    Then we need to get rid of those fractions, so we multiply through by 17:
    17a=23, 17b=8, 17c=17, and 17d=21

    Next we need the 17's row of the multiply table for modulo 26.
    I started it for you with "17*0=0, 17*1=17, 17*2=8, 17*3=25, ..."
    You need to generate the rest of that row. It will be the key to turning something like 17x=P into the form x=Q.
    By the time I get back, I want to see either that full table posted or your solution to a, b, c, and d.
    If you give me a, b, c, and d, I'll know you know what to do with that table. Otherwise, I will walk you through it.

    Once you have a, b, c, and d, the next step will be to demonstrate that you have the answer by doing a matrix multiplication. If you want to demonstrate that you've got yourself tuned in to modulo arithmetic, post that matrix multiplication result before I get back.
     
  25. Jul 13, 2014 #24
    Ok I have started my work on it hopefully I will get I will back soon.
     
  26. Jul 13, 2014 #25
    17*4 = 42, 17*5 =59, 17*6 =76, 17*7 = 93, 17*8 = 110, 17*9 = 127, 17*10 = 144, 17*11 = 161, 17*12 = 178, 17*13=195, 17*14 = 212, 17*15 = 229, 17*16 = 246, 17*17 = 263, 17*18 = 280, 17*19 = 297, 17*20 = 314, 17*21 = 331, 17*22 = 348, 17*23 = 365, 17*24 = 382, 17*25 = 399, 17*26 = 416

    I am however confused by this, because it goes beyond 25.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted