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

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

Inverse of 2

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

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

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

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

Hence: . $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: . $3x \:\equiv\:1 \pmod 7$

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

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

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

Hence: . $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: . $6x \:\equiv\:1 \pmod 7$

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

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

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

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

Therefore, 6 is its own inverse.

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

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