Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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$.

share|improve this answer
    
you mean that "$-9$ is the multiplicative inverse of $-3$". –  Lubin Sep 10 '12 at 6:51
    
@Lubin: I do indeed; thanks for catching the typo. –  Brian M. Scott Sep 10 '12 at 6:52

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.

share|improve this answer

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.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.