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

$9x+23y=1,$, and after performing the extended Euclidean algorithm we have that $1=2\cdot 23-5\cdot 9$ which is true. The solution for x is $x={\lambda}_{1}b+t\cdot {a}_{2}$ where ${\lambda}_{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+23t$ for any integer t.

I need to look for the typical represent, so $x\in [0,23]$. We can achieve this by plugging $t=0$, and thus $x=2$.

However, $[9{]}_{23}\cdot [2{]}_{23}\ne [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\cdot 9+2\cdot 23$ which gave them a solution that checks out. They got $x=-5+23t$, 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.

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

$9x+23y=1,$, and after performing the extended Euclidean algorithm we have that $1=2\cdot 23-5\cdot 9$ which is true. The solution for x is $x={\lambda}_{1}b+t\cdot {a}_{2}$ where ${\lambda}_{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+23t$ for any integer t.

I need to look for the typical represent, so $x\in [0,23]$. We can achieve this by plugging $t=0$, and thus $x=2$.

However, $[9{]}_{23}\cdot [2{]}_{23}\ne [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\cdot 9+2\cdot 23$ which gave them a solution that checks out. They got $x=-5+23t$, 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

Expert

2022-07-10Added 12 answers

Explanation:

If ${\lambda}_{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 .

If ${\lambda}_{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

Expert

2022-07-11Added 5 answers

Explanation:

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

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

Most Popular Questions