Berechnen Sie das multiplikativ Inverse [x]^(-1) von [x] in Zp mit dem erweiterten Euklidischen Algorithmus.

Question

Aufgabe: Sei p =12619 (das ist eine Primzahl) und [x]= [810]p. Berechnen Sie das multiplikativ Inverse [x]^(-1) von [x] in Zp mit dem erweiterten Euklidischen Algorithmus.

Geben Sie Ihr Ergebnis in der Form [y] mit 0 kleiner-gleich y kleiner-gleich p-1 an. Überprüfen Sie Ihre Lösung.

Das ist die Aufgabe, die wir lösen sollen. Ich habe den erweiterten Euklidischen Algorithmus gegoogelt und soweit auch verstanden allerdings verstehe ich trtz nicht die Aufgabe und was ich machen soll...und was ist das Inverse und wie berechnet man es? Über Hilfe oder eine Lösung zum Nachvollziehen würde ich mich freuen, danke

Answer 1

...und was ist das Inverse und wie berechnet man es?

Das ist eine Klasse [y] die mit [x] multipliziert [1] ergibt.

Du brauchst also eine Zahl y mit

x*y ≡ 1 mod p

also x*y = n*p + 1

oder x*y - n*p = 1

Wegen ggT(x,p)=1 gibt es solche

y und n und du kannst sie mit der

erweiterten euklid. Alg. berechnen.

Answer 2

Satz. Sind $n,m \in \mathbb{Z}$, dann gibt es $\alpha,\beta\in \mathbb{Z}$, so dass

        $\operatorname{ggT}(n,m) = \alpha n + \beta m$

ist.

Die Koeffizienten $\alpha$ und $\beta$ können mit dem erweiterten euklidischen Algorithmus bestimmt werden.

Sei p =12619 (das ist eine Primzahl) und [x]= [810]p

Laut obigem Satz gibt es $\alpha,\beta\in \mathbb{Z}$, so dass

        $\operatorname{ggT}(12619,810) = \alpha\cdot 12619 + \beta\cdot 810$

ist.

Weil $12619$ eine Primzahl ist, ist $\operatorname{ggT}(12619,810) = 1$. Also gibt es $\alpha,\beta\in \mathbb{Z}$, so dass

      $1 = \alpha\cdot 12619 + \beta\cdot 810$

ist. Für diese $\alpha,\beta$ ist wegen

        $\alpha\cdot 12619 \equiv 0 \mod 12619$

auch

        $\beta\cdot 810\equiv 1 \mod 12619$

und somit

        $[810]_{12619}^{-1} = [\beta]_{12619}$.

Comments

Also muss ich ß berechnen? Wie mache ich das?

---

Ich zitere mal aus meiner Antwort.

Die Koeffizienten $\alpha$ und $\beta$ können mit dem erweiterten euklidischen Algorithmus bestimmt werden.

Was hast du an diesem Satz nicht verstanden?

---

Ach so, ja kenne den Algorithmus nicht, googel ich mal, Dankeschön.

---

Ich habe den erweiterten Euklidischen Algorithmus gegoogelt und soweit auch verstanden

Ich bin jetzt verwirrt.