Multiplicative inverse of [ 9 ] 23 I'm new to modular arithmetic and this has...

Ellen Chang

Ellen Chang

Answered

2022-07-09

Multiplicative inverse of [ 9 ] 23
I'm new to modular arithmetic and this has been very confusing for me. I know that in order for an element [ a ] m to be invertible, the GCD of (a,m) has to be 1.
I have the element [ 9 ] 23 .
Now, the GCD of those two numbers is 1. We form the Diophantine equation
9 x + 23 y = 1 ,, and after performing the extended Euclidean algorithm we have that 1 = 2 23 5 9 which is true. The solution for x is x = λ 1 b + t a 2 where λ 1 is the first coefficient in the euclidean algorithm and equal to 2, b is the right side of the equation 1, and a 2 is the second coefficient in the equation, which is 23.
This gives me x = 2 + 23 t for any integer t.
I need to look for the typical represent, so x [ 0 , 23 ]. We can achieve this by plugging t = 0, and thus x = 2.
However, [ 9 ] 23 [ 2 ] 23 [ 1 ] 23 .
Where did I go wrong? The only thing my workbook did different was they switched the places in the euclidean algorithm 1 = 5 9 + 2 23 which gave them a solution that checks out. They got x = 5 + 23 t, and for t = 1 they got x = 18, which is the multiplicative inverse.
This made me curious where I went wrong. In my mind, the only thing I did differently was switch the places of the two operands in the euclidean algorithm.

Answer & Explanation

diamondogsaz

diamondogsaz

Expert

2022-07-10Added 12 answers

Explanation:
If λ 1 is the first coefficient regardless of order, then to get the correct answer, you need the correct order. You switched the order when switching sides of the equation. That gave you the wrong inputs to use the formula on .
rjawbreakerca

rjawbreakerca

Expert

2022-07-11Added 5 answers

Explanation:
Stop at your 1 = 2 23 5 9, everything after that is unnecessary. Reduce both sides modulo 23. You get [ 1 ] = [ 5 ] [ 9 ]. There you have the answer. You could say [18] instead of [-5] if you want, but that's not necessary in my opinion.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?