Schlagwort: Blankinship-Algorithmus

Der größte gemeinsame Teiler und der Euklidische Algorithmus

Ausgehend von der Frage, welcher Zusammenhang zwischen Multiplikationstabellen und Linearkombinationen in den ganzen Zahlen bestehen, werden der Euklidische Algorithmus und seine Erweiterung besprochen. Der Euklidische Algorithmus berechnet den größten gemeinsamen Teiler zweier Zahlen, der erweiterte Euklidische Algorithmus erlaubt es zusätzlich, den größten gemeinsamen Teiler von a und b als Linearkombination von a und b darzustellen. Die Analyse dieser Algorithmen liefert zahlreiche Einsichten in die Zusammenhänge zwischen Kongruenzen, Linearkombination in Z und den Eigenschaften des größten gemeinsamen Teilers zweier Zahlen. In den R-Skripten werden Implementierungen vorgestellt sowie Verbesserungen (Blankinship, Stein) des Euklidischen Algorithmus diskutiert.