Find the multiplicative inverse of 23 in Z26

Question

I have no number theory training, but I did many google reading prior coming here. There are so many ways to solve this problem but I am lost.

How would you find the answer to the question

Find the multiplicative inverse of 23 in $Z_{26}$?

Can someone please explain to me (step by step) the quickest and most general way that can be understood by someone who has no rigorous training doing Euclidean algorithm, etc? I think this will benefit the rest of the community out there who are yelled at by their instructors assuming their students would know these things by doing Google search.

I don't mean to make such request, but I am pretty confused. Thank you!

---

I've seen people coming up with solutions like a war machine. There must be quicker way for small m other than doing Euclidean or solving as diophantine equation.

Answer 1

Here is one way to find the inverse. First of all, $23$ has an inverse in $\mathbb{Z} / 26 \mathbb{Z}$ because $gcd(26,23) = 1$. So use the Euclidean algorithm to show that gcd is indeed 1. Going backward on the Euclidean algorithm, you will able to write $1 = 26s + 23 t$ for some $s$ and $t$. Thus $23 t \equiv 1 \text{ mod } 26$. So $t$ is an inverse of $23$ in $\mathbb{Z} / 26 \mathbb{Z}$.

Now you just have to find this $t$. For the details, move cursor over the box

26 = (1)(23) + 3
23 = (7)(3) + 2
3 = (1)(2) + 1
2 = (2)(1) + 0
Hence the gcd is $1$. Now going backward on the Euclidean algorithm, you get
1 = 3 - (1)(2)
Using the second line, you get
1 = 3 - (1)(23 - (7)(3))
1 = 3 - 23 + (7)(3)
1 = (-1)(23) + 8(3)
using the first line
1 = (-1)(23) + 8(26 - (1)(23))
1 = -1(23) + 8(26) + (-8)(23)
1 = -9(23) + 8(26)
Hence the inverse of 23 is -9. Moreover $-9 \equiv 17 \text{ mod } 26$. So $-9$ or equivalently $17$ is the inverse of $23$.

---

A nice exercise to test your understanding of this is to use this idea to prove that if $p$ is prime, then $\mathbb{Z} / p \mathbb{Z}$ is a field.

Answer 2

In this case the numbers are small enough that the easiest approach is trial and error: find a multiple of $23$ that leaves a remainder of $1$ when divided by $26$. But we can be a bit cleverer than that: notice that $23$ is $-3$ in $\Bbb Z_{26}$. Now $(-3)(9)=-27=-1$ in $\Bbb Z_{26}$, so $(-3)(-9)=1$ in $\Bbb Z_{26}$: $-9$ is the multiplicative inverse of $-3$. Finally, $-9=26-9=17$ in $\Bbb Z_{26}$, and we’ve got our answer: the multiplicative inverse of $23$ in $\Bbb Z_{26}$ is $17$. As a check, $17\cdot23=391=1+15\cdot26$.

Answer 3

Generally one can use the Extended Euclidean Algorithm - see here for a convenient manual method. But in this case it is simpler to proceed directly as follows

$$\rm\ mod\ 26\!:\ \ \frac{1}{23}\,\equiv\, \frac{27}{-3}\,\equiv\,-9 $$

Briefly, here it is by the Extended Euclidean Algorithm (follow the link for much more).

$$\rm\begin{eqnarray} &&\ \ 26\, &=&\ \ \ 1&\cdot& 26\, +\, 0\cdot 23 \\ &&\ \ 23 &=&\ \ \ 0&\cdot& 26\, +\, 1\cdot 23 \\ \rm row_1\,\ -\ row_2\to && \ \ \ 3 &=&\ \ \ 1&\cdot& 26\, -\, 1\cdot 23 \\ \rm row_2 - 8\,row_3\to && \color{#C00}{-1} &=& -8&\cdot& \color{blue}{26}\, +\, \color{#0A0}{9\cdot 23} \end{eqnarray}$$

Therefore, examining the last row we deduce, $\rm\ mod\ \color{blue}{26}\!:\,\ \color{#0A0}{9\cdot 23}\equiv \color{#C00}{-1},\ $ so $\ 1/23\equiv -9.$