Erweiterter euklidischer Algorithmus
Dieser Rechner verwendet den erweiterten euklidischen Algorithmus, der neben den größten gemeinsamen Teiler von den Ganzzahlen a und b auch den Lemma von Bezout Koeffizienten berechnet.
Diese Webseite exisiert dank der Arbeit von den folgenden Menschen:
 | Timur
|
Stefan Roesner
|
Auf dieser Seite haben wir bereits einen Rechner, Die größten gemeinsamen Teiler von Ganzzahlen, der den euklidischen Algorithmus verwendet. Wie es sich (für mich) rausgestellt hat, gibt es einen erweiterten euklidischen Algorithmus. Dieser Algorithmus berechnet neben dem größten gemeinsamen Teiler der Ganzzahlen a und b auch das Lemma von Bezout Koeffizienten, die die Ganzzahlen x und y sind von
Er erlaubt also die Berechnung der Quotienten on a und b mit deren größten gemeinsamen Teiler.
Sie finden den Rechner hier, und wie üblich ist der theoretische Teil darunter
Erweiterter euklidischer Algorithmus
Der erweiterte Algorithmus nutzt die Rekursion und berechnet die Koeffizienten durch deren Backtracking. Die Formeln dieser Berechnung kann man durch die folgenden Überlegungen erhalten:
Nehmen wir mal an, wir kennen die Koeffizienten für das Paar
, wie:
,
und wir berechnen die Koeffizienten für das Paar , wie:
Zuerst ersetzen wir mit:
, wobei
- der Quotient von der ganzzahligen Division von b nach a,
und nutzen diese als Ersatz in der Gleichung:
Nach der Umgruppierung haben wir:
In einem Vergleich mit der Anfangsgleichung kann man x und y so darstellen:
Der Anfang des rekursiven Backtracking ist das Ende des euklidischen Algorithmus, wenn a = 0 und GNT = b sind, dann ist das erste x und y 0 und 1 respektiv. Weitere Koeffizienten werden mit den obigen Formeln berechnet.
Kommentare