GGT + Primzahlkörper

Wissenschaft Mathematik
#1

hej, ich habe eine frage bezüglich ggt und den primzahlkörpern.

die aufgabe ein inverses zu finden für (ich bin mir nichtmehr sicher aber ich glaube) 13 im primzahlkörper 919.

normalerweiße für primzahlkörper P5 oder so kann man ne einfache multiplikationstabelle bauen mit 5 x 5 einträgen, kein ding aber ich habe keine lust 919x919 einträge zu machen und schauen wo 1 +919*b ist
(also iwas mit modulo 1) es gibt dazu irgendeinen algorythmus wie ich zu solch hohen körpern ein inverses finde für das 13 *x = 1 ist?

ggt hat glaub ich damit iwas zu tun? sicher bin ich nicht

#2

Ja, das geht mit dem euklidischen Algorithmus.
Bestimme für 13 und 919 den ggT. Dieser sollte 1 sein. Dann kannst du durch Rückwärtseinsetzen o.Ä. die 1 so umformen, dass dann da steht:
1 = x * 13 + y * 919
Modulo 919 wird der letzte Summand 0 und es bleibt:
1 = x * 13
Und das kannst du dann nach dem Inversen von 13 umstellen.
Wenn du es noch genauer brauchst, sag einfach Bescheid.

Nico

#3

da ist mein problem: ggt einer primzahl. was soll das sein. mit kgv kann ich umgehen, ggt habe ich das letzte mal in der 5 oder 6ten klasse gemacht.

wie finde ich genau meine inverse mithilfe des ggT?

#4 
919 | 13 |
----+----+------------------
 13 | 9 | 9 = 919 mod 13 = 919 - 70 \* 13
 9 | 4 | 4 = 13 mod 9 = 13 - 9
 4 | 1 | 1 = 9 mod 4 = 9 - 2 \* 4

Rückwärtseinsetzen:

1 = 9 - 2 \* 4 (4 = 13 - 9)
1 = 9 - 2 \* (13 - 9)
 = 3 \* 9 - 2 \* 13
1 = 3 \* (919 - 70 \* 13) - 2 \* 13
 = 3 \* 919 - 212 \* 13

Das ganze modulo 919:

1 = 3 \* 919 - 212 \* 13
 = -212 \* 13
 = 707 \* 13
1/13 = 707

Fertig.