mutliplicative inverse

Let a = 216, M = 342865. Show that gcd(a,M) = 1. Hence ﬁnd the mutliplicative inverse, a^-1 mod M.

I don't really know what to seach up for this question, but if anyone can provide me a example of this type of question or give me a starting point it would be appreciated.

thanks

• PowerMod[216, -1, 342865] = 112701 – Mario Carneiro Apr 23 '14 at 1:13
• Generally the simplest way is to use the version of the extended Euclidean algorithm described in this answer. – Bill Dubuque Apr 23 '14 at 1:36

You can do this applying the Euclidean Algorithm.

It's pretty simple so long as you're careful with the long division :)

Once you've done the Extended Euclidean Algorithm to get the integers $x$ and $y$ such that $1 = ax + My$, then when you mod out by $M$, you get $ax \equiv 1 \pmod {M}$. Hence, whatever $x$ you get will be the multiplicative inverse of $a$.

• Cheers, solved the question now :) great link – Andrew Apr 23 '14 at 1:30
• Glad I could help! – Kaj Hansen Apr 23 '14 at 1:31

Using the Extended Euclidean Algorithm

$$\begin{array}{rrr} 342865 & 1 & 0\\ 216 & 0 & 1\\ 73 & 1 & -1587\\ -3 & -3& 4762\\ 1 & \color{#c00}{-71} & \color{#0a0}{112701}\\ \end{array}$$

where each above line $\,\ a\ \ b\ \ c\ \,$ means that $\ a = 342865\, b + 216\, c.\$ Therefore

$$1 \,=\, 342865(\color{#c00}{-71})+ 216(\color{#0a0}{112701})\quad$$

from which we deduce that $\ {\rm mod}\ 342865\!:\,\ 1\equiv 216(112701),\,$ so $\,216^{-1}\equiv 112701.$

The linked post described the algorithm in great detail, in a way that is easy to remember.

Here is another example computing $\rm\ gcd(141,19),\,$ with the equations written explicitly

$$\rm\begin{eqnarray}(1)\quad \color{#C00}{141}\!\ &=&\,\ \ \ 1&\cdot& 141\, +\ 0&\cdot& 19 \\ (2)\quad\ \color{#C00}{19}\ &=&\,\ \ \ 0&\cdot& 141\, +\ 1&\cdot& 19 \\ \color{#940}{(1)-7\,(2)}\, \rightarrow\, (3)\quad\ \ \ \color{#C00}{ 8}\ &=&\,\ \ \ 1&\cdot& 141\, -\ 7&\cdot& 19 \\ \color{#940}{(2)-2\,(3)}\,\rightarrow\,(4)\quad\ \ \ \color{#C00}{3}\ &=&\, {-}2&\cdot& 141\, + 15&\cdot& 19 \\ \color{#940}{(3)-3\,(4)}\,\rightarrow\,(5)\quad \color{#C00}{{-}1}\ &=&\,\ \ \ 7&\cdot& 141\, -\color{#0A0}{ 52}&\cdot& \color{#0A0}{19} \end{eqnarray}\qquad$$

Negating the prior line we immediately deduce that, $\ {\rm mod}\,\ 141\!:\:\ \color{#0a0}{52\,\cdot\, 19}\,\equiv\, \color{#c00}1,\,$ so $\, 19^{-1}\equiv 52$

You can use Euclid's algorithms and store up the coefficients.