How to find multiplicative inverse of $17$ in $\mathbb{Z}_{26}$? Say I want to find the multiplicative inverse of $17$ in $\mathbb{Z}_{26}$?
How to do it?
First thing to check is $\gcd(17,26)=1$ so yes they are relatively prime.
I don't really understand Euclid's algorithm to give a solution... Can anyone give an example of how to use his algorithm to find solution? Can be different numbers than what I listed above- just need to see example in action.
Many thanks.
 A: So, the algorithm goes as follows.
$$\begin{align*}26 &= 1 \cdot 17 + \color{red}9 \\ 17 &= 1 \cdot 9 + \color{red}8 \\ 9 &= 1\cdot 8 + \color{red}1. \end{align*}$$
So going back up and isolating the remainders we have $$ \color{red}1 = 9 - \color{red}8 = 9 - (17 - 9) = 2\cdot \color{red}9 - 17 = 2\cdot(26 - 17) - 17 = 2\cdot 26 - 3\cdot 17.$$
And so we find that $1 \equiv (-3)\cdot 17 \mod 26$, i.e., the inverse of $17$ is $-3 \equiv 23 \mod 26$.
A: Let's find $X$:
$17X \equiv 1 \pmod{26}$
$-9X \equiv 1 \pmod{26}$
$9X \equiv -1 \pmod{26}$
$27X \equiv -3 \pmod{26}$
$X \equiv -3 \pmod{26}$
A: Note $51=17\times 3$. Then $17*3=51\equiv(-1)\pmod{26}$. Thus $17*(-3)\equiv 1\pmod{26}$ and $-3\equiv23\pmod{26}$. Therefore $17*23\equiv 1\pmod{26}$
A: We can also do this using Euler's theorem and exponentiation by squaring, complexity is logarithmic over the modulus.
First calculate for powers of two, we use this later: $17^2\equiv 3, 17^4 \equiv9, 17^8\equiv 3$
Now use Euler's theorem to see :
$17^{-1}\equiv17^{\varphi(26)-1}=17^{11}=17\times17^2\times17^7\equiv17\times 3\times 3\equiv 23$.
