System of equations using modulo

[Firestrider]

Homework Statement

5) Determine the inverse of the matrix $$\begin{bmatrix}<br /> 6 & 17\\ <br /> 13 & 21<br /> \end{bmatrix}$$ mod 26

Homework 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

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?

 

[HallsofIvy]

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).