0
$\begingroup$

Let a = 216, M = 342865. Show that gcd(a,M) = 1. Hence find 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

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

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$.

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

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.