# Find the inverse of modulus 26

1. Jul 12, 2014

### DODGEVIPER13

1. The problem statement, all variables and given/known data
$$\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 = ?

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:

• ###### EPSON002.jpg
File size:
11 KB
Views:
168
2. Jul 12, 2014

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

#### Attached Files:

• ###### EPSON003.jpg
File size:
16.4 KB
Views:
227
3. Jul 12, 2014

### Staff: Mentor

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

4. Jul 12, 2014

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

5. Jul 12, 2014

### DODGEVIPER13

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

6. Jul 12, 2014

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

7. Jul 12, 2014

### AlephZero

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

8. Jul 12, 2014

### DODGEVIPER13

It is divisible at k=1 which is 3

9. Jul 12, 2014

### DODGEVIPER13

But what does this mean?

10. Jul 13, 2014

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

11. Jul 13, 2014

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

12. Jul 13, 2014

### DODGEVIPER13

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

13. Jul 13, 2014

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

14. Jul 13, 2014

### .Scott

I haven't read your text book, 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.

15. Jul 13, 2014

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

16. Jul 13, 2014

### .Scott

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
17. Jul 13, 2014

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

18. Jul 13, 2014

### .Scott

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

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
19. Jul 13, 2014

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

20. Jul 13, 2014

### .Scott

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)