multiplakatives inverses restklassen

Question

wenn ich von der restklasse 120¯ das multiplikative Inverse in Z_1777 berechnen möchte, dann muss ich doch einfach den ggt(1777,120) mit Hilfe des Euklidischen Divisionsalgortihmus berechnen und dann den erweiterten Euklidischen Divisionsalgorithmus anwenden oder?

Answer 1

Ja genau. Aber wenn ggt(120,1777) sich nicht als 1 rausstellt, gibt es kein inverses Element. Dann endet die Sache dort. Wenn ggt=1, dann gibt der erweiterte Eukl. Alg. das inverse Element.