Q:

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

A:

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

