Euklidische Algorithmus zur Berechnng des Wertes für [23]^{-1} und [42]^{-1} in (Z,73Z\{0},*)

Question

was will mein Professor von mir bei dieser Aufgabe? Ich verstehe sie gar nicht. Ich soll den Euklidischen Algorithmus benutzen um irgendwelche Werte zu berechnen. Aber ich weiß nicht was ich genau berechnen soll.

[23]^{-1} und [42]^{-1} in (Z,73Z\{0},*)

Answer 1

Du sollst die Inversen der Elemente berechnen. \( [23]^{-1} \) ist das Inverse zum Element \( [23] \), dh es gilt

$$ [23]^{-1} \cdot [23] = [1] = [23] \cdot [23]^{-1} $$

Dazu kannst du den >>>erweiterten<<< euklidischen Algorithmus verwenden. Berechne

$$\gcd(23,73) = 1 = 23u + 73v$$

dann gilt

$$\begin{aligned} [1] &= [23][u] +[73][v]\\&= [23][u] + [0][v] \\&= [23][u] \end{aligned}$$

also ist

$$ [23]^{-1} = [u] $$

Comments

Danke. Hab es raus vielen Dank. Es kommt ja die 54 für die 23 und 40 für die 42 raus, oder?

---

Ja, das ist richtig.