Lassen Sie uns damit beginnen, den größten gemeinsamen Teiler von 527 und 341 zu finden, indem wir zum Aufwärmen den euklidischen Standardalgorithmus verwenden:

Der Standardalgorithmus ist kurz und einfach und wird als nette kleine Anleitung für die Implementierung des erweiterten Algorithmus dienen.

Für den erweiterten euklidischen Algorithmus nehmen wir die dritte Gleichung (in blau), subtrahieren 155(1) von beiden Seiten und ordnen sie ein wenig um, um eine äquivalente Gleichung zu erhalten, in der 31 isoliert ist.

Als Nächstes ersetzen wir 155 durch 341-186(1), was durch Lösen der zweiten Gleichung für 155 gefunden werden kann und uns folgendes ergibt:

Jetzt bereinigen wir das Ganze. Vergewissern Sie sich, dass Sie das negative Vorzeichen durch die Klammern verteilen und 186 + 186 durch 186-2 ersetzen.

Wie Sie vielleicht feststellen, arbeiten wir uns einfach rückwärts durch den Standardalgorithmus. Wir müssen diesen Prozess noch einmal durchlaufen, um eine Gleichung mit 527 und 341 zu erhalten, was schließlich unser Ziel ist.

Ersetzen Sie dazu 186 durch 527 – 341(1), was aus der ersten Gleichung stammt, wenn wir 186 lösen.

Vereinfache die Gleichung weiter, indem du die 2 verteilst und in Gruppen von 527 und 341 kombinierst.

Wir haben jetzt 31 als Linearkombination von 527 und 341 ausgedrückt. Ziemlich cool, was?

Außerdem ist die Zahl auf der gegenüberliegenden Seite der Linearkombination der größte gemeinsame Teiler. In diesem Fall ist 31 also der größte gemeinsame Teiler von 527 und 341.

Der erweiterte euklidische Algorithmus ist praktisch, weil er sowohl die Bezout-Identität liefert als auch den gcd hervorhebt.

Danke fürs Lesen!