Use the Euclid's Algorithm to find the value of $[23]^{-1}$ and $[42]^{-1}$ in ($\mathbb{Z}/73\mathbb{Z}) \setminus \{0\}, *$) I should use the Euclid's Algorithm to find the value of $[23]^{-1}$ and $[42]^{-1}$ in ($\mathbb{Z/73Z \setminus \{0\}, *}$). But I do not even know what I have to do to find the value.
Thanks in advance!
 A: Using the Euclidean algorithm, we get
$$73=3\cdot 23+4$$
$$23=5\cdot 4+3$$
$$4=1\cdot 3+1$$
$$3=3\cdot 1+0.$$
So, the $\operatorname{gcd}(23,73)=1$ (as expected). Now, we reverse-insert these equations to get
$$\operatorname{gcd}(23,73)=1=23\cdot(-19) + 73\cdot6.$$
So, $\operatorname{mod} 73$ the last equation states that $-19\equiv 54 (\operatorname{mod}73)$ is the inverse of $23$ in $\mathbb{Z}/73\mathbb{Z}.$
The case with $42$ is left to you :)
Edit: So, with $f$ and $g$ being your numbers 73 and 23, the Euclidean Algorithm has the structure
$$f=a_0 g+r_0$$
$$g=a_1r_0 + r_1$$
$$r_0=a_2r_1+r_2$$
$$r_1=a_3r_2+r_3$$
Since $r_3=0$ we have $\operatorname{gcd}(f,g)=1$.
Now,
$$\operatorname{gcd}(f,g)=r_2=1=r_0-r_1a_2=r_0-(g-r_0a_1)a_2=(f-ga_0)-(g_2-(f-a_0g)a_1)a_2=f(1+a_1a_2) + g(-a_0-a_2-a_0a_1a_2)$$ where $a_0=3,a_1=5,a_2=1$ and $a_3=3.$
I hope that makes sense to you now.
A: Since $23$ is coprime with $73$, there exist $a,b\in\mathbb Z$ with 
$$
23a+73b=1.
$$
This tells you that $[23][a]=1$ in $\mathbb Z_{73}$. So now you have to use the Euclidean Algorithm to find $a$. 
The situation for $42$ is exactly the same. 
A: A good, structural way to cover the question is to search for the 
continued fraction for the rational number
$$\frac {73}{23}\ ,$$
associated to / extracted from the linear diophantian equation $23a+73b=1$, $a,b\in \Bbb Z$. For this we compute by successive divisions with rest:
$$
\begin{aligned}
\frac {73}{23}
&=
3+\frac 4{23}
=
3+\frac 1{\frac {23}4}
=
3+\frac 1{5+\frac 34}
=
3+\frac 1{5+\frac 1{\frac 43}}
\\
&=
\boxed 3+\frac 1{\boxed 5+\frac 1{\boxed 1+\frac 1{\boxed 3}}}
\\
&=[3,5,1,3]
\end{aligned}
$$
Now, to the representation above, there is a (finite) sequence of convergents, which are the following rational numbers, that approximate "better and better" $73/23$, with denominators up to the ones computed for the convergents, 
$$
\begin{aligned}{}
[3]&=3\ ,\\
[3,5]&=3+\frac 15=\frac {16}5\ ,\\
[3,5,1]&=3+\frac 1{5+\frac 11}=\frac {19}6\ ,\\
[3,5,1,3]&=\dots=\frac{73}{23}\ .
\end{aligned}
$$
Now let us consider the last two convergents, and their difference:
$$
\frac{73}{23}
-
\frac {19}6
=
\frac {73\cdot 6-19\cdot 23}{23\cdot 6}\ .
$$
The nummerator is "always" $\pm 1$, (the moral is that we get "best approximation" with previous convergent value,) and this leads to a solution to the diophantian problem we started with.

Computer support for the calculations, sage here:
sage: a = 73/23
sage: convergents(a)
[3, 16/5, 19/6, 73/23]
sage: 73*6 - 19*23
1
sage: b = 73/42
sage: convergents(b)
[1, 2, 5/3, 7/4, 33/19, 73/42]
sage: 73*19 - 33*42
1
sage: F = GF(73)
sage: 1 / F(23)
54
sage: 1 / F(42)
40

(Note that from $73\cdot 6 - 19\cdot 23=1$, passing to modulo $73$ we get $(-19)\cdot 23=1$ mod $73$, so $-19\equiv (73-19)=54$ is the inverse of $23$ in the field with $73$ elements.
