# Thread: Multiplicative Inverses

1. ## Multiplicative Inverses

Righto, i had to miss a lecture and the notes are just of skeleton form so they don't explain things well. Could someone tell me whats going on here from a tutorial Q i have.

6.1 - Find the multiplicative inverses of the non-zero elements in $\displaystyle Z_7$. (Just experimenting is probably easier than
using the Euclidean algorithm.)
hint/solution 6.1 - By experiment, 2.4 = 1, 3.5 = 16.6 = 1 and so 2,4 are
mutually inverse as are 3,5. The element 6 is its own inverse.

I assume the algorithm in question is the GCD one, but surely that means 16,6 and 2,4 would be 2..?

So... Whats going on here?

Here's an algebraic approach to this problem.

6.1 - Find the multiplicative inverses of the non-zero elements in $\displaystyle Z_7$.

In any system: .$\displaystyle 1\cdot1 \equiv 1 \pmod{n}$
. . 1 is its own inverse.

Inverse of 2

We want: .$\displaystyle 2x \:\equiv\:1 \pmod 7$

. . That is: .$\displaystyle 2x \:=\:7n+1$ . . . $\displaystyle 2x$ is one more than a multiple of 7.

. . Then: .$\displaystyle x \:=\:\frac{7n+1}{2} \:=\:3n + \frac{n+1}{2}$

Since $\displaystyle x$ is a positive integer, $\displaystyle n+1$ must be divisible by 2.
The first time this happens is when $\displaystyle n = 1$

Hence: .$\displaystyle x \:=\:3(1) + \frac{1+1}{2} \:=\:4$

Therefore, 4 is the inverse of 2 ... and 2 is the inverse of 4.

Inverse of 3

We want: .$\displaystyle 3x \:\equiv\:1 \pmod 7$

. . That is: .$\displaystyle 3x \:=\:7n+1$ . . . $\displaystyle 3x$ is one more than a multiple of 7.

. . Then: .$\displaystyle x \:=\:\frac{7n+1}{3} \:=\:2n + \frac{n+1}{3}$

Since $\displaystyle x$ is a positive integer, $\displaystyle n+1$ must be divisible by 3.
The first time this happens is when $\displaystyle n = 2$

Hence: .$\displaystyle x \:=\:2(2) + \frac{2+1}{3} \:=\:5$

Therefore, 5 is the inverse of 3 ... and 3 is the inverse of 5.

Inverse of 6

We want: .$\displaystyle 6x \:\equiv\:1 \pmod 7$

. . That is: .$\displaystyle 6x \:=\:7n+1$ . . . $\displaystyle 6x$ is one more than a multiple of 7.

. . Then: .$\displaystyle x \:=\:\frac{7n+1}{6} \:=\:n + \frac{n+1}{6}$

Since $\displaystyle x$ is a positive integer, $\displaystyle n+1$ must be divisible by 6.
The first time this happens is when $\displaystyle n = 5$

Hence: .$\displaystyle x \:=\:5 + \frac{5+1}{6} \:=\:6$

Therefore, 6 is its own inverse.

. . . . $\displaystyle \begin{array}{|c|c|} \hline \text{Number} & \text{Inverse} \\ \hline 1 & 1 \\ 2 & 4 \\ 3 & 5 \\ 4 & 2 \\ 5 & 3 \\ 6&6 \\ \hline \end{array}$

3. Originally Posted by Deadstar
Righto, i had to miss a lecture and the notes are just of skeleton form so they don't explain things well. Could someone tell me whats going on here from a tutorial Q i have.

6.1 - Find the multiplicative inverses of the non-zero elements in $\displaystyle Z_7$. (Just experimenting is probably easier than
using the Euclidean algorithm.)
hint/solution 6.1 - By experiment, 2.4 = 1, 3.5 = 16.6 = 1 and so 2,4 are
mutually inverse as are 3,5. The element 6 is its own inverse.

I assume the algorithm in question is the GCD one, but surely that means 16,6 and 2,4 would be 2..?

So... Whats going on here?
They said they are NOT using the Euclidean algorithm, "just experimenting". When they say 2.4= 1, 3.5= 16.6= 1, they are talking about the LCD but really mean the product: 2.4= 8=7+ 1 so is 1 mod 7. 3*5= 15= 2*7+1 so is 1 mod 7. I have no idea what the "16.6" is about! Perhaps they meant 6.6 and the "1" is a misprint: 6*6= 36= 5*7+1 so is 1 mod 7.

If they DID use the Euclidean Algorithm to find the mulitplicative inverse of, say, 6 mod 7, what they would have done would be
"iIf n is the multiplicative inverse of 6, mod 7, then 6n= 1 mod 7 which means 6n= 7m+ 1 for some integer m. That is the same as the Diophantine equation 6n- 7m= 1. Clearly that is true for m= n= -1 but it is also true for an m= -1+ 6k, n= -1+ 7k (because the "k" terms will cancel in the equation). Taking k= 1, m= 5 and n= 6: 6(6)- 5(7)= 1 so 6(6)= 5(7)+ 1. Of course, for small numbers it is, as they say, easier just to "experiment": 6(2)= 12= 5 mod 7; no. 6(3)= 18= 4 mod 7; no, 6(4)= 24= 3 mod 7; no, 6(5)= 30= 2 mod 7; no, 6(6)= 36= 1 mod 7. That's the one!