How do you find a multiplicative inverse in modulo arithmetic?
In one of my lectures I have been given this example:
When Googling 'multiplicative inverse' most of the tutorials seem to indicate it's as easy as just multiplying a number by the number divided by 1. What's different in this example? How do you work out a multiplicative inverse when it's $\mathbb{Z}_7$ ?
Also, how exactly is the additive inverse calculated?
$\endgroup$ 33 Answers
$\begingroup$You use what is called the extended Euclidean algorithm. Here is an example:
Let's say we want to find the inverse of $5$ mod $7$. We first seek to find integers $a$ and $b$ such that:
$5a + 7b = 1$ (note that this is a Bezout identity).
Having done so, mod $7$, we wind up with:
$5a = 1$ (mod $7$), so $a$ (mod $7$) is the inverse we're after.
So how do we find $a$ (and the $b$ we don't really care about)?
First we divide $7$ by $5$, to get:
$7 = 1\cdot 5 + 2$.
Next, we divide $5$ by $2$, to get:
$5 = 2\cdot 2 + 1$.
Now...we "work backwards":
$1 = 5 - 2(2)$
But $2 = 7 - 5$, so we get:
$1 = 5 - 2(7 - 5) = 5 - 2(7) + 2(5) = 3(5) - 2(7)$.
Thus $a = 3$, and $b = -2$.
So $5^{-1}$ (mod $7$) is $3$ (mod $7$).
$\endgroup$ 2 $\begingroup$To get the additive inverse, subtract the number from the modulus, which in this case is $7$. (except that $0$ is its own inverse) For example, the additive inverse of $5$ is $7-5=2$.
To get the multiplicative inverse is trickier, you need to find a number that multiplied by $n$ is one more than a multiple of $7$. For example, $5^{-1}$ is $3$ because $5\cdot 3=15$, which is one more than a multiple of $7$.
$\endgroup$ 1 $\begingroup$1*1= 1, 2*4= 8= 7+ 1= 1 (mod 7), 3*5= 15= 2(7)+ 1= 1 (mod 7), and then 4*2= 1 (mod 7), 5*3= 1 (mod 7), 6*6= 36= 5(7)+ 1= 1 (mod 7). So the multiplicative inverse of 1 is 1, the multiplicative inverse of 2 IS 4, the multiplicative inverse of 3 is 5, the multiplicative inverse of 4 is 2, the multiplicative inverse of 5 is 3, and the multiplicative of 6 is 6 (all "mod 7").
$\endgroup$
