Modular Arithmetic – Extended Euclidean Algorithm for Modular Inverse

inversemodular arithmetic

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?

Best Answer

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.