Mathematik

Euklidischer Algorithmus Mathematik

Euklidischer Algorithmus , Verfahren zum Auffinden dergrößter gemeinsamer Teiler (GCD) zweier Zahlen, beschrieben vom griechischen MathematikerEuklid in seinen Elementen ( ca. 300 v . Chr. ). Die Methode ist rechnerisch effizient und wird mit geringfügigen Änderungen weiterhin von Computern verwendet.

Auf einer Seite aus einer Arbeitsmappe der ersten Klasse, die typisch für „neue Mathematik“ ist, heißt es möglicherweise: „Zeichnen Sie Verbindungslinien von Dreiecken im ersten Satz zu Dreiecken im zweiten Satz.  Sind die beiden Sätze gleich groß? “
Lesen Sie mehr zu diesem Thema
Arithmetik: Grundlegende Theorie
… Ein Prozess, der als euklidischer Algorithmus bekannt ist und funktioniert, weil die GCD von a und b gleich ist ...

Der Algorithmus beinhaltet das sukzessive Teilen und Berechnen von Resten; Dies lässt sich am besten anhand eines Beispiels veranschaulichen. Um beispielsweise die GCD von 56 und 12 zu ermitteln, teilen Sie zuerst 56 durch 12 und beachten Sie, dass der Quotient 4 und der Rest 8 ist. Dies kann ausgedrückt werden als 56 = 4 × 12 + 8. Nehmen Sie nun den Divisor (12). Teilen Sie es durch den Rest (8) und schreiben Sie das Ergebnis als 12 = 1 × 8 + 4. Nehmen Sie auf diese Weise den vorherigen Teiler (8), teilen Sie ihn durch den vorherigen Rest (4) und schreiben Sie das Ergebnis als 8 = 2 × 4 + 0. Da der Rest jetzt 0 ist, ist der Prozess beendet und der letzte Rest ungleich Null, in diesem Fall 4, ist die GCD.

Der euklidische Algorithmus ist nützlich, um a zu reduzierengemeinsamer Bruch zu niedrigsten Begriffen. Zum Beispiel zeigt der Algorithmus, dass die GCD von 765 und 714 51 ist und daher 765/714 = 15/14. Es hat auch eine Reihe von Anwendungen in der fortgeschritteneren Mathematik . Zum Beispiel ist es das grundlegende Werkzeug, um ganzzahlige Lösungen für lineare Gleichungen a x + b y = c zu finden , wobei a , b und c ganze Zahlen sind. Der Algorithmus liefert als aufeinanderfolgende Quotienten, die aus dem Divisionsprozess erhalten werden, auch die ganzen Zahlen a , b , ..., f, die für die Expansion eines Bruchteils p / benötigt werdenq als fortgesetzte Fraktion: a + 1 / ( b + 1 / ( c + 1 / ( d … + 1 / f )).