How Do You Find the Inverse of a Matrix Modulo 26?

[DODGEVIPER13]

Homework Statement

$$\begin{pmatrix} 5 & 8\\ 17 & 3\\ \end{pmatrix}$$

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

Homework Equations

ax+by = c

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?

 

[DODGEVIPER13]

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.

 

[mfb]

So now to find the inverse, I need the Euclidean algorithm

To do what?
26 and 9 are coprime, that's the result of the algorithm.

 

[DODGEVIPER13]

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.

 

[DODGEVIPER13]

They then multiplys the inverse found to be 3 by the adjoint matrix A.

 

[DODGEVIPER13]

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

 

[AlephZero]

Ok so should I just find the adjoin matrix?

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.

Where did they get 3

Test if 26k+1 is divisible by 9, for k = 0, 1, 2, ...

 

[DODGEVIPER13]

It is divisible at k=1 which is 3

 

[DODGEVIPER13]

But what does this mean?

 

[DODGEVIPER13]

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?

 

[mfb]

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

 

[DODGEVIPER13]

Ok but why the 3 how would I know to do this on a test?

 

[mfb]

See post 7 from AlephZero.

A adj(A) = a diagonal matrix (but not the unit matrix)

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.

 

[.Scott]

I haven't read your textbook, but I would just do the modulo 26 arithmetic:
$$\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}$$
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.

 

[DODGEVIPER13]

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?

 

[.Scott]

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 matrix?

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?

 

[DODGEVIPER13]

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?

 

[.Scott]

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?

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

 

[DODGEVIPER13]

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.

 

[.Scott]

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.

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)

 

[DODGEVIPER13]

Ok well I get the -3 and -5 now and why you used 26 but now I am confused on 121-(4*26) where is the 4?

 

[.Scott]

Ok well I get the -3 and -5 now and why you used 26 but now I am confused on 121-(4*26) where is the 4?

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.

 

[.Scott]

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 into modulo arithmetic, post that matrix multiplication result before I get back.

 

[DODGEVIPER13]

Ok I have started my work on it hopefully I will get I will back soon.

 

[DODGEVIPER13]

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.

 

[.Scott]

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.

You're supposed to be working in modulo 26. So none of those products should be anything other than 0 to 25.
For example, 17*4 = 68, modulo 26 is 16, so 17*4=16.

So: 17*0=0, 17*1=17, 17*2=8, 17*3=25, 17*4=16, ...

Give me the remaining 21, 17*5 to 17*25. Stop before 17*26 because that's zero.

 

[.Scott]

One quick way to generate this table is to add 17 to the preceding entry and then, if the result is 26 or more, subtract 26.

So 17*0 = 0
17*1 = 0+17 = 17
17*2 = 17+17 = 34 - 26 = 8
17*3 = 8+17 = 25
17*4 = 25+17 = 42 - 26 = 16
17*5 = 16+17 = ...

 

[DODGEVIPER13]

17*5=7,
17*6=24,
17*7=15,
17*8 = 6,
17*9= 23,
17*10=14,
17*11=5,
17*12=22,
17*13=13,
17*14=4,
17*15=21,
17*16=12,
17*17=3
17*18=20
17*19=11,
17*20=2,
17*21=19,
17*22=10,
17*23=1,
17*24=18,
17*25=9

 

[.Scott]

Excellent.
So, tell me, what are a, b, c, and d, given: 17a=23, 17b=8, 17c=17, and 17d=21 ?

 

[.Scott]

Here's a clue. Two of the answers are from the 5 table entries I calculated. The other two are from your part of the table.

When you report your results, report them in this form:
$$Inverse = \begin{pmatrix} a & b\\ c & d\\ \end{pmatrix} = \begin{pmatrix} 25 & 25\\ 25 & 25\\ \end{pmatrix}$$
With the "25"s replaced with your results.

As you can see, you're on the final step to the solution.
... and so far, your calculations are correct.

 

[DODGEVIPER13]

A=9 b=2 c=1 d =15

 

[DODGEVIPER13]

$$\begin{pmatrix} 9 & 2\\ 1 & 15\\ \end{pmatrix}$$

 

[DODGEVIPER13]

Sweet man you are the best, so if I see this on the test I should follow the instructions you gave?

 

[.Scott]

Excellent!
Now demonstrate that the answer is correct:
$$\begin{pmatrix} 9 & 2\\ 1 & 15\\ \end{pmatrix} \begin{pmatrix} 5 & 8\\ 17 & 3\\ \end{pmatrix} = ?$$
Remember this: When you do the adds and multiplies you can start by ignoring the modulo 26 arithmetic. But before you finish, bring everything back to 0 to 25.

For example, if you work it out and get this:
$$\begin{pmatrix} 1303 & 2604\\ 3905 & 5206\\ \end{pmatrix}$$
Take the next step to bring it to modulo 26:
$$\begin{pmatrix} 1303 & 2604\\ 3905 & 5206\\ \end{pmatrix} = \begin{pmatrix} 3 & 4\\ 5 & 6\\ \end{pmatrix}$$

 

[.Scott]

Sweet man you are the best, so if I see this on the test I should follow the instructions you gave?

Once you demonstrate that your answer is correct (which it is), you will have achieved minimum rank at modulo 26 wizardry!