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