Extended Euclidean Algorithm for Modular Inverse

Solution 1:

You have to write $$ 1 = 240x+17y $$ so $$ 240x\equiv 1\pmod{17} $$

The Euclidean algorithm applied to $240$ and $17$ gives \begin{align} \color{red}{240} &= \color{red}{17}\cdot 14 + \color{red}{2} \\ \color{red}{17} &= \color{red}{2}\cdot 8 + \color{red}{1} \end{align} The successive remainders are colored red. Now start from the top: $$ \color{red}{2}=\color{red}{240}-\color{red}{17}\cdot 14 $$ Go one line down: $$ \color{red}{1}=\color{red}{17}-\color{red}{2}\cdot 8 $$ Substitute the value you have for $\color{red}{2}$: $$ \color{red}{1}=\color{red}{17}-(\color{red}{240}-\color{red}{17}\cdot 14)\cdot 8 =\color{red}{17}\cdot(1+132)-\color{red}{240}\cdot 8 =\color{red}{240}\cdot(-8)+\color{red}{17}\cdot 133 $$ Thus you can take $x=-8$, or else $x=9$ since $-8\equiv 9\pmod{17}$. Indeed $$ 240\cdot9=2160=17\cdot127+1 $$ or $$ 240\cdot 9\equiv 1\pmod{17}. $$

Just remember operating on the “red numbers” as if they were letters. Express each remainder in terms of the previous ones and substitute in the equations below the first. Only terms with $\color{red}{240}$ and $\color{red}{17}$ multiplied by integers will remain.

Solution 2:

There is no fast, efficient way of finding an inverse. A general tip is to reduce as much as possible first to get everything between $0$ and $p-1$ when taking $\pmod p$. So, $240x \equiv 2x \pmod {17}$ and the inverse of $2$ is just $9$ so $x \equiv 9 \pmod {17}$.