Frage zur Lösung (erweiterter Euklidischer Algorithmus)

Question

Aufgabe: 15*x = 10 (mod 17) x Element von Z_17 nun rechnen wir x aus, mit dem erweiterten euklidischen Algorithmus :

17 = 1 * 15 +2; 15 = 7 *2 + 1 => 1 = 15 -7 * 2; 1 = 15 - 7(17 -15) => 15^-1 = 8

15^-1 = 8 wie kommt man darauf der Rest ist mir klar, aber dieser Sprung? Kann leider keinen Zusammenhang herstellen.

Answer 1

Hi,

wenn du die Klammer auflöst du folgendes erhältst

1 = 15 -7*17+7*15 = 8*15 +7*17

Das bedeutet aber auch 8*15 = 1 mod 17

also ist 8 die Inverse zu 15 in Z_17.

Gruß