WikiDer > Euklids Algorithmus

Animation des Algorithmus von Euklid für die Zahlen 252 und 105. Die Querbalken repräsentieren Vielfaches ab 21, die größter gemeinsamer Teiler (ggd). In jedem Schritt wird die kleinere Zahl von der größeren Zahl abgezogen, bis eine Zahl auf Null reduziert ist. Die verbleibende Zahl wird als größter gemeinsamer Teiler bezeichnet.

In dem Zahlentheorie, eine Unterregion der Mathematik, ist der Euklids Algorithmus eine effiziente Methode zur Berechnung der größter gemeinsamer Teiler (ggd) von zwei positive ganze Zahlen.

Der Algorithmus ist nach dem benannt AltgriechischMathematikerEuklid von Alexandria, das sind die Algorithmen in den Büchern VII und X von Elemente beschrieben.^[1] Der Algorithmus basiert auf der Tatsache, dass die gcd zweier Ganzzahlen auch die gcd der kleinsten Zahl und des Rests ist, der übrig bleibt, wenn die größte Zahl durch die kleinste geteilt wird. Dadurch entsteht ein absteigender iterativ Prozess. Da ist auch ein erweiterte Variante dieses Algorithmus.

Hintergrund

Der größte gemeinsame Teiler zweier Zahlen ist die größte Zahl, die beide Zahlen ohne . enthält sich ausruhen Anteile. Der Algorithmus von Euklid basiert auf dem Prinzip, dass sich der größte gemeinsame Teiler zweier Zahlen nicht ändert, wenn die kleinere von der größeren abgezogen wird.

21 ist zum Beispiel der größte gemeinsame Teiler von 252 und 105 (252 = 21 × 12, 105 = 21 × 5) seit der gcd von 147 (252 - 105) und 105 ist ebenfalls gleich 21. Da man im Algorithmus von zwei Zahlen immer die kleinere von der größten subtrahiert, kann man diesen Vorgang wiederholen, bis eine der beiden Zahlen gleich Null ist. Der größte gemeinsame Teiler ist die verbleibende Zahl (die nicht Null ist).

Erweiterung

Durch Umkehrung der Schritte im Euklid-Algorithmus kann die gcd ausgedrückt werden als Summe der beiden ursprünglichen Zahlen, jeweils multipliziert mit einem positiven oder negativen gerade Zahl zum Beispiel 21 = 5 × 105 (-2) × 252. Diese wichtige Eigenschaft ist als . bekannt Identität von Bézout. Auf diese Weise gibt es umfassender Algorithmus eine Lösung für die diophantische Gleichung

${displaystyle ax by={m {{ggd}(a,b),}}}$

Geschichte

Die älteste erhaltene Beschreibung des euklidischen Algorithmus findet sich in der Elemente (Buch VII, Satz 1 und 2) von Euklid (ca. 300 v. Chr.) und ist damit eine der ältesten Zahlen Algorithmen ist das noch gebraucht. Euklid hat es in Betracht gezogen Geometer Problem, ein gemeinsames "Maß" für zwei Entfernungen zu finden. Der Algorithmus wurde wahrscheinlich nicht von Euclid erfunden, war aber mit ziemlicher Sicherheit schon bekannt von Eudoxus von Knidos (ca. 375 v. Chr.). Ebenfalls Aristoteles (ca. 330 v. Chr.) Punkte in seinem Werk Thema (158b, 29-35) über den Algorithmus.

Der ursprüngliche Algorithmus wurde nur für natürliche Zahlen und geometrische Längen verwendet (reale Nummern), aber im 19. Jahrhundert wurde der Algorithmus auf andere Zahlentypen verallgemeinert, wie z ganze Zahlen von Gauß und Polynome in einer Variablen. Dies führte zu modernen abstrakte Algebra Konzepte wie euklidische Domänen. Gabriel Lame lieferte die Leverde 1844 mathematischer Beweis dass der Algorithmus nie mehr Schritte als das Fünffache der Anzahl der Stellen (Basis 10) der kleineren ganzen Zahl erfordert. Dieser Beweis markiert den Beginn von rechnerische Komplexitätstheorie. Im 20. Jahrhundert wurde Euklids Algorithmus weiter auf andere verallgemeinert mathematische Strukturen, wie Knoten und multivariate Polynome. Außerdem wurden Methoden entwickelt, um die Effizienz des Algorithmus zu verbessern.

Anwendungen

Der Algorithmus von Euklid hat viele theoretische und praktische Anwendungen. Es kann verwendet werden, um fast alle wichtigen traditionellen Musikrhythmen zu erzeugen, die in verschiedenen Kulturen auf der ganzen Welt verwendet werden.^[2] Es ist auch ein wichtiger Bestandteil der RSA-Algorithmus, ein Verschlüsselungsmethode mit öffentlichem Schlüssel, die in der . weit verbreitet ist elektronischer Handel wird eingesetzt. Der Algorithmus wird beim Lösen verwendet diophantische Gleichungen, wie das Finden von Zahlen, die mehrere Kongruenzen erfüllen (Chinesischer Restsatz) oder multiplikative Inverse von a endliches Feld erfüllen. Der Algorithmus von Euklid kann auch bei der Konstruktion von verwendet werden Kettenbrüche, in dem Sturmkettenmethode zum Finden reeller Nullstellen eines Polynoms und in verschiedenen modernen ganzzahlige Faktorisierungsalgorithmen. Schließlich ist es ein grundlegendes Werkzeug für den Nachweis Thesen in der Moderne Zahlentheorie, wie Der Vier-Quadrat-Satz von Lagrange und der Hauptsatz der Arithmetik (eindeutige Faktorisierung).

Der Algorithmus

1. Nenne die größere der beiden Zahlen ${Anzeigestil A}$, das andere ${Anzeigestil B}$.
2. ziehen ${Anzeigestil B}$ genauso oft von ${Anzeigestil A}$ bis 0 oder eine Zahl kleiner als übrig bleibt ${Anzeigestil B}$ (${Displaystil A!!!mod B}$).
3. Wenn 0 bleibt, ${Anzeigestil B}$ die gcd.
4. Wenn nicht, wiederholen Sie den Algorithmus mit ${Anzeigestil B}$ und was ist mit ${Anzeigestil A}$ vorbei ist.

Beispiel

Das folgende Beispiel, in dem die gcd von 900 und 1140 bestimmt wird, verdeutlicht den Algorithmus von Euklid.

Die Division von 1140 durch 900 ergibt:

${displaystyle 1140=1 imes 900 240}$

Da der gesuchte GCD auch der GCD von 900 und 240 ist, wird 900 durch 240 geteilt:

${displaystyle 900=3 imes 240 180}$

Es geht so:

${displaystyle 240=1 imes 180 60}$

${displaystyle 180=3 imes 60 0}$

Der Rest ist jetzt 0, womit die Berechnung beendet ist. Der größte gemeinsame Teiler von 900 und 1140 ist 60, denn:

der letzte Schritt, 180 = 3 × 60 0, zeigt, dass 60|180,

der Schritt davor, 240 = 1 × 180 60, zeigt, dass 60|240,

weiter hinten, 900 = 3 × 240 180, zeigt, dass 60|900,

der erste Schritt, 1140 = 1 × 900 240, also 60|1140.

Die Schlussfolgerung ist, dass 60 ein gemeinsamer Teiler von 900 und 1140 ist.

Wenn d ein gemeinsamer Teiler von 900 und 1140 ist, dann sei

die erste Zeile, 1140 = 1 × 900 240, siehe, dass d|240

die zweite Zeile, 900 = 3 × 240 180, dass d|180

und die dritte Zeile, 240 = 1 × 180 60, dass d|60

Daraus folgt, dass jeder gemeinsame Teiler von 900 und 1140 ein Teiler von 60 ist. Dann ist 60 der größte gemeinsame Teiler.

Die Berechnung kann kurz als Sequenz geschrieben werden:

${Anzeigestil 1140 900 240 180 60 0,}$

Für jedes aufeinanderfolgende Trio ... a b c ... in der Folge gilt: a mod b = c

Auf die gleiche Weise wird die Berechnung des gcd von 752 und 372 geschrieben:

${Anzeigestil 752 372 8 4 0}$

Daraus folgt:

${displaystyle mathrm {ggd} (752,372)=4}$

Implementierung

Je nach den Möglichkeiten, die eine Programmiersprache bietet, kann man von rekursive Programmierung und die 'mod'-Operation. In der folgenden Implementierung ist der Schritt

1. Nenne die größere der beiden Zahlen ${Anzeigestil A}$, das andere ${Anzeigestil B}$

übersprungen: eine Zahl wird einfach übersprungen ${Anzeigestil A}$ und der andere ${Anzeigestil B}$ erwähnt. Trotzdem läuft es gut, denn ${Displaystil A!!!mod B}$ gleich ${Anzeigestil A}$ wenn ${Anzeigestil B>A}$ und die Zahlen werden daher bei der ersten Rekursion umgekehrt.

bestimme gcd(A, B): if B = 0 answer = A else answer = gcd(B, (A mod B))

Für Programmiersprachen, die keine rekursive Programmierung unterstützen und/oder die Operation 'mod' nicht kennen, kann auch Folgendes verwendet werden:

bestimme gcd(A, B): solange (A ≠ B) falls A > B reduziere A um B sonst reduziere B um A

Nachdem Sie diesen Code durchlaufen haben, sind die Zahlen ${Anzeigestil A}$ und ${Anzeigestil B}$ gleich und der größte gemeinsame Teiler des anderen (sowie der ursprünglichen Zahlen).