0 Daumen
1,4k Aufrufe


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

Avatar von

Zur Kontrolle kannst du doch jetzt einfach 

22*19 + 57  ausrechnen. (modulo 59 müsste 3 rauskommen, wenn 19 richtig ist.) 

2 Antworten

+1 Daumen
 
Beste Antwort

Zur Kontrolle kannst du doch jetzt einfach 

22*19 + 57  ausrechnen. (modulo 59 müsste 3 rauskommen, wenn 19 richtig ist.) 


Kontrolle mit 

https://www.wolframalpha.com/input/?i=%2822*19+%2B+57-3%29%2F59

besagt, dass x=19 stimmt.

Die Frage wäre höchstens noch, ob man 19 nicht einfacher rausbekommen kann.

Avatar von 162 k 🚀
+1 Daumen
Passt doch alles:

Probe zeigt 22*19 + 57=475 = 8*59 + 3 also kongruent 3 MOD 59.

Und weil es über einem Körper ist, gibt es auch nur diese eine Lösung.

Avatar von 289 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community