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.

Question

Multiplicative inverse of   [  9      ]          23      I&#039;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.

diamondogsaz · Accepted Answer

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 · Accepted Answer

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&#039;s not necessary in my opinion.