Additive and multiplicative Inverse

Quote:

Originally Posted by extatic

Hi All,

Having a real hard time in particular getting a grasp on multiplicative inverse. In a standard tut question is see is :

Compute the additive and multiplicative inverses of 7 and 8 MOD13

Would love any input, thank you

If you're given $x\pmod{n}$ , and $x+y \equiv 0\pmod{n}$ , then $y\pmod{n}$ is the additive inverse of $x\pmod{n}$ . Similarly, if $xz\equiv 1\pmod{n}$ , then $z$ is the multiplicative inverse of $x\pmod{n}$ .

Calculating the additive inverses is relatively easy; all you need to do is find an $x$ such that $7+x\equiv 13\equiv 0\pmod{13}$ with $x$ being an element of the residue system $\{0,1,\ldots,11\}$ (Its very similar for the other one).

In calculating the multiplicative inverse of $7\pmod{13}$ there is usually no quick of way of doing it (if you have a knowledge of Euler's theorem, then it could be used to get to the answer as well). However, since you're looking at mod 13, you can find the inverse by the method of exhaustion; i.e. find out what 7*1, 7*2, 7*3, ... ,7*13 are and see which results in the value of 1. So in your case, $7\cdot 2\equiv 14\equiv 1\pmod{13}$ so 2 is the multiplicative inverse of 7. The other one is done in a similar fashion.

Does this make sense? Can you proceed?