Wie Erweiterter Euklidischer Algorithmus Gleichung Lösen?
Wir haben in Mathe die Aufgabe die Gleichung 83x + 36y = 1 und müssen diese mit dem Erweiterten Euklidischen Algorithmus lösen. Wir haben diese nicht erklärt bekommen und wir wissen auch nicht ganz wie es funktioniert. Wir haben den EEA nur im Zusammenhang im RSA verfahren benutzt um die Inverse b zu bestimmen
2 Antworten
Das geht genauso wie bei RSA und der Inversenbestimmung. Du führst den euklidischen Algorithmus mit 83 und 36 aus und kommst in der letzten Zeile auf 1, dies ist dann der ggT. Nun löst du diese Gleichung nach 1 auf und setzt rückwärts alle Zwischenergebnisse ein, bis du nur noch Terme mit 83 und 36 hast (das müsstest du ja können, ist ja bei der Inversenbestimmung genauso), das führt dann auf
1 = 30 * 36 - 13 * 83.
Dies ist dann die Lösung der Gleichung.
p.s. Es gilt jetzt natürlich logischerweise 30 = 36^(-1) mod 83 und genauso -13 = 83^(-1) mod 36, damit hast du ja auch die beiden Inversen.
ja, ich kanns auch nicht, ich kann dir nur eine lösung anbieten, wo x und y abhängig sind
toll, oder?