Inverse Restklasse modulo bestimmen

Question

Aufgabe:

Bestimmen Sie die zu [22] inverse Restklasse modulo 59.

Meine Rechenschritte:

1)ggT bestimmen mit euklidischem Algorithmus.

2)Erweiterten euklidischen Algorithmus.

3)Einsetzen

Nach meiner Rechnung ist der ggT(59,22) = 1.

Somit ist 1=59x + 22y  -> 1=59*3 + 22*(-8)

Antwort: Das Inverse zu 22 ist -8.

Sind meine Rechenschritte und das Ergebnis richtig?

Answer 1

Kannst du ja leicht prüfen:
wenn -8 ( oder besser -8+59=51) die inverse Restklasse zu 22 ist,
dann muss ja -8*22   bzw   51*22  kongruent 1 mod 59 sein.
und das ist der Fall
-8*22=-176 = 1 - 3*59
aber wie gesagt besser wohl
51*22=1122=1+1121=1+19*59