1. Not finding help here? Sign up for a free 30min 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!

System of equations using modulo

  1. Sep 23, 2010 #1
    1. The problem statement, all variables and given/known data
    5) Determine the inverse of the matrix [tex]\begin{bmatrix}
    6 & 17\\
    13 & 21
    \end{bmatrix}[/tex] mod 26


    2. Relevant equations

    Solve for linear system of equations:
    6a + 17c = 1 mod 26 6b + 17d = 0 mod 26
    13a + 21c = 0 mod 26 13b + 21d = 1 mod 26

    3. The attempt at a solution

    6 * (13a + 21c) = 6 * (0 mod 26)
    - 13 * (6a + 17c) = 13 * (1 mod 26)
    --------------------------------------------
    78a + 126c = 0 mod 26
    - (78a + 221c = 13 mod 26)
    --------------------------------------------
    95c = 13 mod 26



    This is where I'm stuck. How do you divide 13 mod 26 by 95?
     
  2. jcsd
  3. Sep 24, 2010 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, first you reduce 95 mod 26: 26 divides into 95 3 times with remainder 17 so 95= 17 (mod 26). Now you want to solve 17c= 13 (mod 26). You want to multiply both sides by the multiplicative inverse of 17 (mod 26). That, of course, would be an integer n such that 17n= 1 (mod 26). And that says that 17n must be one more than a multiple of 26: 17n= 26m+ 1 for some integer m.

    Write that as the Diophantine equation 17n- 26m= 1. 17 divides into 26 once with remainder 9: 26- 17= 9. 9 divides into 17 once with remainder 8: 17- 9= 8. And 8 divides into 9 once with remainder 1: 9- 8= 1. Replace the "8" in that last equation with 17- 9: 9- (17- 9)= 2(9)- 17= 1. Replace the "9" in that with 26- 17: 2(26- 17)- 17= 2(26)- 3(17)= 1.

    That is, n= -3 and m= -2 will work: 17(-3)- 26(-2)= 2(26)- 3(17)= 1. And, of course, n= -3= 26- 3= 23 (mod 26).

    As a check, 23(17)= 442= 391= 390+ 1= 15(26)+ 1= 1 (mod 26).

    1/17= 23 (mod 26) so x= 13/17= 13(23)= 299= 11(26)+ 13= 13 (mod 26).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: System of equations using modulo
  1. System of Equations (Replies: 1)

  2. System of Equations (Replies: 6)

  3. System of equations (Replies: 3)

Loading...