Extended Euclidean Algorithm for Modular Inverse I'm currently learning how to find the inverse of a modulo with the Extended Euclid Algorithm and I stumbled upon a problem when finding an inverse when
the $m>p$ as for $m \equiv 1 \pmod{p}$
For example, in
$$
240x \equiv 1 \pmod{17}
$$
what is the inverse? What are the steps to find it?
 A: 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.
A: 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}$. 
A: In this case, m > p. So find the remainder of m/p. m mod p = 240 mod 17 = 2.
so the inverse of 240 and the inverse of 2 (mod 17) are the same. The above answer stating the inverse is 9 is correct (2 * 9 = 18 and 18 mod 17 = 1)
