gegebn sei 22 x + 57 = 3 über den GF(59). Gesucht wird x.
So gehe ich vor, aber das Ergebnis hatte mich verwundert. Ich hatte einen Zahlendreher drin, der mir beim erstellen der Frage hier aufgefallen ist, kann trotzdem jemand bestätigen das mein Vorgehen korrekt ist?
Vielen Dank
22x = 3 - 57 | -57
22x = -54 mod 59 ==> 59 - 54 = 5
22x = 5
x = 5 * 22^-1 (Also muss ich das multiplikative Inverse von 22 finden)
ggT(59,22) = 1 ist klar, weil sie teilerfremd sind
59 = 22 x 2 + 15
22 = 15 x 1 + 7
15 = 7 x 2 +1
jetzt das ganze rückwärts
1 = 15 - 7 x 2
1 = 15 - (22 - 15) x2 = 3 x 15 - 22 x 2
1 = 3 x (59 - 22 x2 ) - 22 x 2 = 3 x 59 - 8 x 22
==> -8 mod 59 = 59 - 8 = 51
Also ist das multiplikativ Inverse zu 22 = 51
Probe: 22 * 51 = 1122 mod 59 = 1, also das scheint zu stimmen weiter mit der Gleichung
x = 5 * 51 = 255 mod 59 = 19