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!

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
    2016 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
    2016 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
    2016 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)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Find the inverse of modulus 26
Loading...