Finde das Inverse Element der Multiplikation mit 34 im endlichen Körper GF(37).

Question

Aufgabe:

Finde das Inverse Element der Multiplikation mit 34 im endlichen Körper GF(37).

Problem/Ansatz:

Erstmal mit dem euklidischen Algorithmus den GGT(34, 37) berechnet.

37 = 1 * 34 + 3

34 = 11 * 3 + 1

3 = 3 * 1 + 0

Nun soll ich ja 1 = s * 34 + t * 37 durch Umkehrung des euklidischen Algorithmus darstellen. Mir ist aber noch nicht klar, wie das funktioniert, hab mal nen Ansatz gemacht:

1 = 34 - 11 * 3

1 = 34 - 11 * (37-34)

Comments

1 = 34 - 11 * (37-34)

= 12*34 -11*37

Modulo 37 gilt also

12*34 = 1

Answer 1

Den ggT(34,37) hast du mit 1 richtig bestimmt.

Du setzt jetzt einfach rückwärts ein (Stichwort: Lemma von Bézout)

1=34-3*11

1=34-11*(37-34)=34-11*37+11*34=34(1+11)-11*37=12*34+(-11)*37

Das sind doch gerade die Zahlen, die du suchst, d. h. s=12 und t=-11

Comments

Jetzt hab ichs verstanden, war doch nicht so schwer, vielen Dank. Habe bemerkt, dass man immer einfach nach dem Rest umstellen muss.

---

Kein Ding ;)

Answer 2

Beide Zeilen sind richtig

37 = 1·34 + 3 → 3 = 1·37 - 1·34

Du kannst also den Rest 3 darstellen als 1·37 - 1·34.

34 = 11·3 + 1 → 1 = 1·34 - 11·3

Du kannst also den Rest 1 darstellen als 1·34 - 11·3. Aber moment. Wir wissen ja schon das wir 3 auch anders schreiben können

34 = 11·3 + 1 → 1 = 1·34 - 11·(1·37 - 1·34) = 12·34 - 11·37

Das inverse zu 34 ist als 12 wenn wir in der Resteklasse 37 rechnen.