Euklidischer Algorithmus

Aufrufe: 55     Aktiv: 09.05.2022 um 23:47
0
Hallo,
hier wurde beispielhaft eine Aufgabe vorgerechnet. Ich muss aber \(  {537}^{-1}  \) in Z/40169Z berechnen. Allerdings ist mir bei der Beispiel-Rechnung nicht klar, wie man auf \( 1=1 \cdot 11-2 \cdot 5 \) kommt. Bei so kleinen Zahlen kann man es ja direkt sehen, aber ich sehe nicht die Schlussfolgerung, wie man darauf kommt, weil bei 537 und 40169 kann ich es nicht direkt sehen.
Diese Frage melden
gefragt

Punkte: 39

 
Kommentar schreiben
1 Antwort
0
Das ist eben die Erweiterung des euklidischen Algorithmus. Im Beispiel ist man ja nach einem Schritt fertig. Bei ggT=1 hört der eben mit 1 auf. Und die Darstellung 1=11-2*5 erhält man durch Umstellen der Zeile dadrüber.
Also rechne erstmal 40169 = 537*?+ Rest usw. bis zum Ende, d.h. da wo es mit ggT=1 endet. Dann umstellen und man hat 1=.... Da setzt man dann wieder von der Zeile drüber ein usw. bis man bei den Ausgangszahlen landet und da die Inverse ablesen kann.
Alles klar? Fang mal an zu rechnen. Man rechnet erstmal los. Kein Mensch schreibt eine Mathe-Aufgabe erst dann auf, wenn er sie im Kopf komplett gelöst hat.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 24.03K

 
Hm, weiß nicht ob ich deine Antwort nicht richtig verstanden habe oder ob ich meine Frage nicht richtig gestellt habe. Für mein konkretes Beispiel habe ich diese Rechnungen schon vorgenommen: 40169=537 * 74+431 --> 537= 431 * 1+106 --> 431= 106 * 4 + 7 --> 106=15*7+1 --> 7=7*1+0 ,sodass der ggT =1 ist. Aber die nächste Zeile ist mir nicht ganz bewusst. Quasi 1 = x*40169 - y*537. Wie komme ich auf ganzzahlige x und y?   ─   sreal 09.05.2022 um 23:06
Oh deinen Edit sehe ich erst jetzt, mal schauen, ob ich es jetzt verstehe   ─   sreal 09.05.2022 um 23:11
Ja, sorry, habe mich in der Interpretation Deiner Frage nochmal umentschieden, daher der edit.
So, das war der eukl. Algorithmus, so weit gut. Jetzt kommt die Erweiterung zur Bestimmung der Inversen, da durchläuft man die Gleichungen von unten nach oben.
Start also mit 1=106-15*7, nun aus der vorigen Zeile einsetzen:
1=106-15*7=106-15*(431-106*4)= ausmultiplizieren und in die From 106*...+431*... bringen, dann die 106 austauschen, ausmultiplizieren, sortieren, fertig. Klappt das?   ─   mikn 09.05.2022 um 23:33
Ja, hat geklappt, danke   ─   sreal 09.05.2022 um 23:47

Kommentar schreiben