Use the Euclid's Algorithm to find the value of $[23]^{-1}$ and $[42]^{-1}$ in ($\mathbb{Z}/73\mathbb{Z}) \setminus \{0\}, *$)

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

$73 = 3*23+ 4$ so $\color{blue}{4} = 73 - 3*23$

$23 = 5*\color{blue}{4} + 3$ so $\color{green}{3} = 23 - 5*\color{blue}{4}$

$\color{blue}{4} = \color{green}{3}+1$

SO....

$1= \color{blue}{4} - \color{green}{3}$

$=(73 - 3*23)-(23 - 5*\color{blue}{4})$

$=(73 - 3*23)-(23 - 5*(73 - 3*23))$

$=73*6-23*19$

Which means that $23*(-19) = 1 - 7*6$ which means $23*(-19)\equiv 1 \mod 73$

Which meand $23^{-1} \equiv -19 \equiv 54 \mod 73$.

There are easier ways to do notation and keep track of progress but that is the idea. If we kept track as we went along.

$73 = 42 + 31$ so $\color{blue}{31} = 73 - 42$.

$42 = \color{blue}{31} + 11$

so $\color{green}{11} = 42 - \color{blue}{31}$

$= 42 - (73 - 42)$

$= 2*42 - 73$

And $\color{blue}{31} = 2*\color{green}{11} + 9$

So $\color{orange}9 = \color{blue}{31}- 2*\color{green}{11}$

$=(73 - 42) - 2(2*42 - 73)$

$=3*73-5*42$

And $\color{green}{11} = \color{orange}9 + 2$ so

$\color{purple}2 = \color{green}{11}-\color{orange}9$

$= (2*42 - 73) - (3*73-5*42)$

$= 7*42 - 4*73$

And $\color{orange}9 = 4*\color{purple}2+1$

so finally

$1 = \color{orange}9 - 4*\color{purple}2$

$=(3*73-5*42) - 4*(7*42 - 4*73)$

$=19*73 - 33*42$.

So $1 = 19*73 - 33*42$ so

$42(-33) = 1 - 19*73$

So $42(-33) \equiv 1 \mod 73$

So $42^{-1} \equiv -33\equiv 40 \mod 73$.

Answer 4

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.