In der Mathematik ist der Euklidische Algorithmus (hat auch den Algorithmus von Euklid genannt), eine effiziente Methode, für den größten allgemeinen Teiler (GCD) von zwei ganzen Zahlen, auch bekannt als den größten gemeinsamen Faktor (GCF) oder höchsten gemeinsamen Faktor (HCF) zu schätzen. Es wird nach dem griechischen Mathematiker Euklid genannt, der es in Büchern VII und X seiner Elemente beschrieben hat.

Die frühste überlebende Beschreibung des Euklidischen Algorithmus ist in den Elementen von Euklid (c. 300 v. Chr.), es einen der ältesten numerischen Algorithmen noch in der üblichen Anwendung machend. Der ursprüngliche Algorithmus wurde nur für natürliche Zahlen und geometrische Längen (reelle Zahlen) beschrieben, aber der Algorithmus wurde im 19. Jahrhundert zu anderen Typen von Zahlen, wie ganze Zahlen von Gaussian und Polynome in einer Variable verallgemeinert. Das hat zu modernen abstrakten algebraischen Begriffen wie Euklidische Gebiete geführt. Der Euklidische Algorithmus ist weiter zu anderen mathematischen Strukturen, wie Knoten und multivariate Polynome verallgemeinert worden.

Der Algorithmus hat viele theoretische und praktische Anwendungen. Es kann verwendet werden, um fast alle wichtigsten traditionellen Musikrhythmen zu erzeugen, die in verschiedenen Kulturen weltweit verwendet sind. Es ist ein Schlüsselelement des RSA Algorithmus, eine im elektronischen Handel weit verwendete Verschlüsselungsmethode des öffentlichen Schlüssels. Es wird verwendet, um Gleichungen von Diophantine, wie Entdeckung von Zahlen zu lösen, die vielfache Kongruenzen (chinesischer Rest-Lehrsatz) oder multiplicative Gegenteile eines begrenzten Feldes befriedigen. Es kann auch verwendet werden, um fortgesetzte Bruchteile in der Kettenmethode von Sturm zu bauen, um echte Wurzeln eines Polynoms, und in mehrerer moderner ganzer Zahl factorization Algorithmen zu finden. Schließlich ist es ein grundlegendes Werkzeug, um Lehrsätze in der modernen Zahlentheorie, wie der quadratische Lehrsatz von Lagrange und der Hauptsatz der Arithmetik (einzigartiger factorization) zu beweisen.

Wenn durchgeführt, mit Resten der langen Abteilung aber nicht Subtraktionen schätzt der Algorithmus von Euklid den GCD der großen Anzahl effizient: Man verlangt nie mehr Abteilungsschritte als fünfmal die Zahl von Ziffern (stützen Sie 10) der kleineren ganzen Zahl. Das wurde von Gabriel Lamé 1844 bewiesen, und kennzeichnet den Anfang der rechenbetonten Kompliziertheitstheorie. Methoden, für die Leistungsfähigkeit des Algorithmus zu verbessern, wurden im 20. Jahrhundert entwickelt.

Der GCD von zwei Zahlen ist die größte Zahl, die sie beide teilt, ohne einen Rest zu verlassen. Der Euklidische Algorithmus basiert auf dem Grundsatz, dass sich der größte allgemeine Teiler von zwei Zahlen nicht ändert, wenn die kleinere Zahl von der größeren Zahl abgezogen wird. Zum Beispiel, 21 ist der GCD 252 und 105 (252 = 21 × 12; 105 = 21 × 5); seit 252  105 = 147 ist der GCD 147 und 105 auch 21.

Da die größere von den zwei Anzahlen vermindert wird, wiederholend, dass dieser Prozess nacheinander kleinere Zahlen gibt, bis einer von ihnen Null ist. Wenn das vorkommt, ist der GCD die restliche Nichtnullzahl. Durch das Umkehren der Schritte im Euklidischen Algorithmus kann der GCD als eine Summe der zwei ursprünglichen Zahlen jeder ausgedrückt werden, der mit einer positiven oder negativen ganzen Zahl, z.B, 21 = [5 × 105] + [(2) × 252] multipliziert ist. Dieses wichtige Eigentum ist als die Identität von Bézout bekannt.

Konkretes Beispiel

Nehmen Sie an, dass es gewünscht wird, um gcd (1989, 867), d. h. der größte allgemeine Teiler von 1989 und 867 zu finden.

Wenn wir die größere Anzahl vermindern, indem wir die kleinere davon abziehen, ändert sich der gcd nicht:

:

So machen Sie wieder Abstriche:

:

Jetzt 867 ist nicht mehr die kleinere Zahl. Ebenso weitermachend, vermindern wir die größere Anzahl, jetzt 867, indem wir die kleinere davon abziehen, das gcd unveränderte verlassend:

:

Die erste Zahl, 255, ist noch die kleinere, so wieder verwenden wir es, um das größere zu reduzieren:

: \begin {richten }\aus

\gcd (255,612) & = \gcd (255,612-255) = \gcd (255,357) \\

\text {und again:} & = \gcd (255,357-255) = \gcd (255,102).

\end {richten }\aus</Mathematik>

Jetzt 255 ist die größere Zahl, und wir reduzieren sie, indem wir 102 davon Abstriche machen:

: \begin {richten }\aus

\gcd (255,102) & = \gcd (255-102.102) = \gcd (153,102) \\

\text {und again:} & = \gcd (153-102.102) = \gcd (51,102).

\end {richten }\aus</Mathematik>

Jetzt 102 ist der größere, und wir reduzieren ihn, indem wir 51 davon Abstriche machen:

:

Jetzt werden wir getan: Wir beschließen dass gcd (1989,867) = 51. So müssen wir haben

: \begin {richten }\aus

1989 & = 51 \times\text {etwas}, \\

867 & = 51 \times\text {etwas}.

\end {richten }\aus</Mathematik>

Durch die Abteilung bekommen wir

: \begin {richten }\aus

1989 & = 51 \times 39, \\

867 & = 51 \times 17.

\end {richten }\aus</Mathematik>

Wenn man wiederholt die größere Anzahl vermindert, indem man die kleinere davon so abzieht:

:

dann ist die kleinste Zahl am Ende, 255, der Rest, der sich aus sich teilendem 1989 durch 867 ergibt. So wird der Algorithmus häufig wie folgt beschrieben:

• In Anbetracht des Problems, gcd (1989,867) zu finden, ersetzt man die größere Zahl, 1989 durch den Rest, der sich aus dem Teilen davon durch die kleinere Zahl, 867 ergibt, kommend

::

• Folgender ersetzt die größere Zahl, 867, durch den Rest, der sich aus dem Teilen davon durch die jetzt kleinere Zahl, 255 ergibt, kommend

::

• Folgender ersetzt die größere Zahl, 255, durch den Rest, der sich aus dem Teilen davon durch die jetzt kleinere Zahl, 102 ergibt, kommend

::

• Folgender ersetzt die größere Zahl, 102, durch den Rest, der sich aus dem Teilen davon durch die jetzt kleinere Zahl, 51 ergibt, kommend

::

• Wenn 0 erscheint, werden wir getan; der gcd ist 51.

Hintergrund

Größter allgemeiner Teiler

Der Euklidische Algorithmus berechnet den größten allgemeinen Teiler (GCD) von zwei natürlichen Zahlen a und b. Der größte allgemeine Teiler g ist die größte natürliche Zahl, die sowohl a als auch b teilt, ohne einen Rest zu verlassen. Synonyme für den GCD schließen den größten gemeinsamen Faktor (GCF), den höchsten gemeinsamen Faktor (HCF) und das größte allgemeine Maß (GCM) ein. Der größte allgemeine Teiler wird häufig als GCD (a, b) oder, einfacher, als geschrieben (a, b), obwohl die letzte Notation auch für andere mathematische Konzepte wie zweidimensionale Vektoren verwendet wird.

Wenn GCD (a, b) = 1, dann, wie man sagt, sind a und b coprime (oder relativ erst). Dieses Eigentum deutet nicht an, dass a oder b selbst Primzahlen sind. Zum Beispiel, weder 6 noch 35 ist eine Primzahl, da sie beide zwei Hauptfaktoren haben: 6 = 2 × 3 und 35 = 5 × 7. Dennoch, 6 und 35 sind coprime. Keine natürliche Zahl außer 1 teilt sich sowohl 6 als auch 35, da sie keine Hauptfaktoren gemeinsam haben.

Lassen Sie g = GCD (a, b). Da a und b beide Vielfachen von g sind, können sie = Mg und b = ng geschrieben werden, und es gibt keine größere Zahl G> g, für den das wahr ist. Die natürlichen Zahlen M und n müssen coprime seit jedem gemeinsamen Faktor sein, können der M und n ausgeklammert werden, um g größer zu machen. So muss jede andere Nummer c, die sowohl a als auch b teilt, auch g teilen. Der größte allgemeine Teiler g a und b ist der einzigartige (positive) allgemeine Teiler von a und b, der durch jeden anderen allgemeinen Teiler c teilbar ist.

Der GCD kann wie folgt vergegenwärtigt werden. Denken Sie ein rechteckiges Gebiet durch b und jeden allgemeinen Teiler c, der sowohl a als auch b genau teilt. Die Seiten des Rechtecks können in Segmente der Länge c geteilt werden, der das Rechteck in einen Bratrost von Quadraten der Seitenlänge c teilt. Der größte allgemeine Teiler g ist der größte Wert von c, für den das möglich ist. Für die Illustration kann ein 24 durch 60 rechteckiges Gebiet in einen Bratrost geteilt werden: 1 durch 1 Quadrate, 2 durch 2 Quadrate, 3 durch 3 Quadrate, 4 durch 4 Quadrate, 6 durch 6 Quadrate oder 12 durch 12 Quadrate. Deshalb, 12 ist der größte allgemeine Teiler 24 und 60. Ein 24 durch 60 rechteckiges Gebiet kann in einen Bratrost von 12 durch 12 Quadraten, mit zwei Quadraten entlang einem Rand (24/12 = 2) und fünf Quadraten entlang dem anderen (60/12 = 5) geteilt werden.

Der GCD von zwei Zahlen a und b ist das Produkt der durch die zwei Zahlen geteilten Hauptfaktoren, wo derselbe Hauptfaktor mehrmals verwendet werden kann, aber nur so lange das Produkt dieser Faktoren sowohl a als auch b teilt. Zum Beispiel, seit 1386 kann factored in 2 × 3 × 3 × sein 7 × 11, und 3213 können factored in 3 × 3 × 3 × 7 × 17 sein, der größte allgemeine Teiler von 1386 und 3213 ist 63 = 3 × 3 × 7, das Produkt ihrer geteilten Hauptfaktoren gleich. Wenn zwei Zahlen keine Hauptfaktoren gemeinsam haben, ist ihr größter allgemeiner Teiler 1 (erhalten hier als ein Beispiel des leeren Produktes), mit anderen Worten sind sie coprime. Ein Schlüsselvorteil des Euklidischen Algorithmus besteht darin, dass es den GCD effizient finden kann, ohne die Hauptfaktoren schätzen zu müssen. Wie man glaubt, ist Factorization von großen ganzen Zahlen ein rechenbetont sehr schwieriges Problem, und die Sicherheit von vielen modernen Geheimschrift-Systemen basiert auf seinen infeasibility.

Eine andere Definition des GCD ist in der fortgeschrittenen Mathematik nützlich, rufen Sie besonders Theorie an. Der größte allgemeine Teiler g zwei Nichtnullzahlen a und b ist auch ihre kleinste positive integrierte geradlinige Kombination, d. h. die kleinste positive Zahl der Form ua + vb, wo u und v ganze Zahlen sind. Der Satz aller integrierten geradlinigen Kombinationen von a und b ist wirklich dasselbe als der Satz aller Vielfachen von g (Mg, wo M eine ganze Zahl ist). Auf der modernen mathematischen Sprache ist das Ideal, das durch a und b erzeugt ist, das Ideal, das durch den g erzeugt ist, allein (ein durch ein einzelnes Element erzeugtes Ideal wird ein Hauptideal genannt, und alle Ideale der ganzen Zahlen sind Hauptideale). Einige Eigenschaften des GCD sind tatsächlich leichter, mit dieser Beschreibung, zum Beispiel die Tatsache zu sehen, dass jeder allgemeine Teiler von a und b auch den GCD teilt (teilt es beide Begriffe von ua + vb). Die Gleichwertigkeit dieser GCD Definition mit den anderen Definitionen wird unten beschrieben.

Der GCD von drei oder mehr Zahlen kommt dem Produkt der für alle Zahlen üblichen Hauptfaktoren gleich, aber es kann auch durch die wiederholte Einnahme des GCDs von Paaren von Zahlen berechnet werden. Zum Beispiel,

: GCD (a, b, c) = GCD (a, GCD (b, c)) = GCD (GCD (a, b), c) = GCD (GCD (a, c), b).

So genügt der Algorithmus von Euklid, der den GCD von zwei ganzen Zahlen schätzt, um den GCD von willkürlich vielen ganzen Zahlen zu berechnen.

Induktion, recursion und unendlicher Abstieg

Drei zusammenhängende mathematische Methoden werden in den Argumenten unten verwendet: Induktion, recursion und unendlicher Abstieg.

Induktion wird häufig verwendet, um einen Lehrsatz für alle natürlichen Zahlen n zu beweisen. Diese Annäherung beginnt durch die Vertretung, dass, wenn der Lehrsatz für n hält, es auch für n + 1 hält. Deshalb, wenn der Lehrsatz für einen Fall hält (normalerweise, n = 1), hält es für alle höheren Fälle (n = 2, 3, usw.).

Ein recursion ist eine Gleichung, die Zahlen verbindet, die eine Reihe a, a, a usw. bilden. Der n-te Begriff in der Reihe, a, wird häufig in Bezug auf frühere Begriffe der Reihe wie a ausgedrückt. Zum Beispiel werden die Fibonacci-Zahlen rekursiv definiert; jeder Begriff ist die Summe der zwei vorhergehenden Begriffe: F = F + F. Mehrere mit dem Euklidischen Algorithmus vereinigte Gleichungen sind rekursiv.

Schließlich, im unendlichen Abstieg, wird eine gegebene Lösung in natürlichen Zahlen verwendet, um eine Lösung mit kleineren natürlichen Zahlen zu bauen. Jedoch können die Lösungen nicht unbestimmt zurückweichen, da es nur eine begrenzte Zahl von natürlichen Zahlen unter den anfänglichen natürlichen Zahlen gibt. Deshalb war entweder die ursprüngliche Lösung unmöglich, oder der Aufbau von kleineren Lösungen muss enden. Das letzte Argument wird verwendet, um zu zeigen, dass der Euklidische Algorithmus für natürliche Zahlen in einer begrenzten Zahl von Schritten enden muss.

Beschreibung

Verfahren

Der Euklidische Algorithmus ist wiederholend, bedeutend, dass die Antwort in einer Reihe von Schritten gefunden wird; die Produktion jedes Schritts wird als ein Eingang für den nächsten Schritt verwendet. Lassen Sie k eine ganze Zahl sein, die die Schritte des Algorithmus aufzählt, mit der Null anfangend. So entspricht der anfängliche Schritt k = 0, der nächste Schritt entspricht k = 1, und so weiter.

Jeder Schritt beginnt mit zwei nichtnegativen Resten r und r. Da der Algorithmus sicherstellt, dass die Reste fest mit jedem Schritt abnehmen, ist r weniger als sein Vorgänger r. Die Absicht des Kth-Schritts ist, einen Quotienten q und Rest r solch zu finden, dass die Gleichung zufrieden ist

: r = q r + r

wo r. Mit anderen Worten werden Vielfachen der kleineren Nummer r von der größeren Nummer r abgezogen, bis der Rest kleiner ist als der r.

Im anfänglichen Schritt (k = 0), die Reste r und der r gleiche a und b, die Zahlen, für die der GCD gesucht wird. Im nächsten Schritt (k = 1), die Reste gleicher b und der Rest r des anfänglichen Schritts, und so weiter. So kann der Algorithmus als eine Folge von Gleichungen geschrieben werden

: = q b + r

: b = q r + r

: r = q r + r: r = q r + r

: …

Wenn kleiner zu sein, als b der erste Schritt des Algorithmus die Zahlen tauscht. Zum Beispiel, wenn Null gleichkommt, und der Rest r a ist. So ist r kleiner als sein Vorgänger r für den ganzen k  0.

Seit der Rest-Abnahme mit jedem Schritt, aber kann nie negativ sein, ein Rest r muss schließlich Null gleichkommen, an dem Punkt der Algorithmus anhält. Der Endnichtnullrest r ist der größte allgemeine Teiler von a und b. Die Nummer N kann nicht unendlich sein, weil es nur eine begrenzte Zahl von natürlichen Zahlen zwischen dem anfänglichen Rest r und der Null gibt.

Beweis der Gültigkeit

Die Gültigkeit des Euklidischen Algorithmus kann durch ein Zweipunktargument bewiesen werden. Im ersten Schritt, wie man zeigt, teilt der Endnichtnullrest r sowohl a als auch b. Da es ein allgemeiner Teiler ist, muss es weniger sein als oder gleich dem größten allgemeinen Teiler g. Im zweiten Schritt wird es gezeigt, dass jeder allgemeine Teiler von a und b, einschließlich g, r teilen muss; deshalb muss g weniger sein als oder gleich r. Diese zwei Beschlüsse sind wenn r = g inkonsequent.

Um zu demonstrieren, dass r sowohl a als auch b (der erste Schritt) teilt, teilt r seinen Vorgänger r

: r = q r

seit dem Endrest ist r Null. r teilt auch seinen folgenden Vorgänger r

: r = q r + r

weil es beide Begriffe auf der rechten Seite der Gleichung teilt. Dasselbe Argument wiederholend, teilt r alle vorhergehenden Reste, einschließlich a und b. Keiner der vorhergehenden Reste r, r, teilt usw. a und b, da sie einen Rest verlassen. Da r ein allgemeiner Teiler von a und b, r  g ist.

Im zweiten Schritt teilt jede natürliche Zahl c, der sowohl a als auch b teilt (mit anderen Worten, jeder allgemeine Teiler von a und b) die Reste r. Definitionsgemäß kann a und b als Vielfachen von c geschrieben werden: = mc und b = nc, wo M und n natürliche Zahlen sind. Deshalb teilt c den anfänglichen Rest r, seitdem r = ein  qb = mc  qnc = (M  qn) c. Ein analoges Argument zeigt, dass c auch die nachfolgenden Reste r, r usw. teilt. Deshalb muss der größte allgemeine Teiler g r teilen, der das g  r einbezieht. Seitdem der erste Teil des Arguments die Rückseite (r  g), hieraus folgt dass g = r gezeigt hat. So ist g der größte allgemeine Teiler aller folgenden Paare:

:g = GCD (a, b) = GCD (b, r) = GCD (r, r) = … = GCD (r, r) = r.

Bearbeitetes Beispiel

Für die Illustration kann der Euklidische Algorithmus verwendet werden, um den größten allgemeinen Teiler = 1071 und b = 462 zu finden. Um zu beginnen, werden Vielfachen 462 von 1071 abgezogen, bis der Rest weniger als 462 ist. Zwei solche Vielfachen können (q = 2) abgezogen werden, einen Rest von 147 verlassend

: 1071 = 2 × 462 + 147.

Dann werden Vielfachen 147 von 462 abgezogen, bis der Rest weniger als 147 ist. Drei Vielfachen können (q = 3) abgezogen werden, einen Rest von 21 verlassend

: 462 = 3 × 147 + 21.

Dann werden Vielfachen 21 von 147 abgezogen, bis der Rest weniger als 21 ist. Sieben Vielfachen können (q = 7) abgezogen werden, keinen Rest verlassend

: 147 = 7 × 21 + 0.

Da der letzte Rest Null, die Algorithmus-Enden mit 21 als der größte allgemeine Teiler 1071 und 462 ist. Das stimmt mit dem GCD (1071, 462) gefunden durch ersten factorization oben überein. In der tabellarischen Form sind die Schritte

Vergegenwärtigung

Der Euklidische Algorithmus kann in Bezug auf die mit Ziegeln deckende Analogie vergegenwärtigt werden, die oben für den größten allgemeinen Teiler gegeben ist. Nehmen Sie an, dass wir ein a-by-b Rechteck mit Quadratziegeln genau, wo bedecken möchten der größeren von den zwei Zahlen zu sein. Wir versuchen zuerst, das Rechteck mit b-by-b Quadratziegel mit Ziegeln zu decken; jedoch verlässt das ein r-by-b restliches Rechteck mit Ziegeln ungedeckt, wo r-by-r Quadratziegel. Das verlässt ein zweites restliches Rechteck r-by-r, den wir zum Ziegel mit r-by-r Quadratziegel und so weiter versuchen. Die Folge endet, wenn es kein restliches Rechteck gibt, d. h., wenn die Quadratziegel das vorherige restliche Rechteck genau bedecken. Die Länge der Seiten des kleinsten Quadratziegels ist der GCD der Dimensionen des ursprünglichen Rechtecks. Zum Beispiel ist der kleinste Quadratziegel in der angrenzenden Zahl 21 durch 21 (gezeigt im Rot), und 21 ist der GCD 1071 und 462, die Dimensionen des ursprünglichen Rechtecks (gezeigt im Grün).

Das Rechnen der Quotienten und Reste

An jedem Schritt k schätzt der Euklidische Algorithmus einen Quotienten q und Rest r von zwei Nummern r und r

: r = q r + r

wo der Umfang von r ausschließlich weniger ist als dieser von r. Der Abteilungsalgorithmus stellt sicher, dass solch ein Quotient und Rest immer bestehen. Der Abteilungsalgorithmus für natürliche Zahlen stellt auch fest, dass q und r einzigartig sind, aber das ist für den Euklidischen Algorithmus nicht erforderlich.

In der ursprünglichen Version von Euklid des Algorithmus werden der Quotient und Rest durch die wiederholte Subtraktion gefunden; d. h. r wird von r wiederholt abgezogen, bis der Rest r kleiner ist als r. Eine effizientere Annäherung verwendet Abteilung der ganzen Zahl und die modulo Operation, um den Quotienten und Rest beziehungsweise zu berechnen. Die modulo Operation gibt den Rest nach dem Teilen von zwei Zahlen; so,

:r &equiv; r mod r

Der Rest ist zur Kongruenz-Klasse in der Modularithmetik gleichwertig.

Durchführungen

Durchführungen des Algorithmus können im Pseudocode ausgedrückt werden. Zum Beispiel kann die Abteilungsbasierte Version als programmiert werden

fungieren Sie gcd (a, b)

während b  0

t: = b

b: = ein mod b

a: = t

geben Sie einen zurück

Am Anfang der kth Wiederholung hält die Variable b den letzten Rest r, wohingegen die Variable ein Halten seines Vorgängers, r. Der Schritt b: = ist ein mod b zum obengenannten recursion Formel r  r mod r gleichwertig. Die Platzhaltervariable t hält den Wert von r, während der folgende Rest r berechnet wird. Am Ende der Schleife-Wiederholung hält die Variable b den Rest r, wohingegen die Variable ein Halten seines Vorgängers, r.

In der Subtraktionsbasierten von Euklid definierten Version wird die Rest-Berechnung (b = ein mod b) durch die wiederholte Subtraktion ersetzt.

fungieren Sie gcd (a, b)

wenn = 0

geben Sie b zurück

während b  0

wenn a> b

a: = ein  b

sonst

b: = b  ein

geben Sie einen zurück

Die Variablen a und B-Stellvertreter das Halten der vorherigen Reste r und r. Nehmen Sie dass an größer zu sein, als b am Anfang einer Wiederholung; dann ein Gleichkommen r, seitdem r> r. Während der Schleife-Wiederholung, reduziert durch Vielfachen des vorherigen Rests b zu sein, bis er kleiner gewesen ist als b. Dann des folgenden Rests r zu sein. Dann wird b durch Vielfachen reduziert, bis es wieder kleiner ist als a, den folgenden Rest r und so weiter gebend.

Die rekursive Version basiert auf der Gleichheit des GCDs von aufeinander folgenden Resten und der anhaltenden Bedingung GCD (r, 0) = r.

fungieren Sie gcd (a, b)

wenn b = 0

geben Sie einen zurück

sonst

geben Sie gcd (b, ein mod b) zurück

Für die Illustration wird der GCD (1071, 462) vom gleichwertigen GCD (462, 1071 mod 462) = GCD (462, 147) berechnet. Der letzte GCD wird vom GCD (147, 462 mod 147) = GCD berechnet (147, 21), der der Reihe nach vom GCD (21, 147 mod 21) = GCD (21, 0) = 21 berechnet wird.

Methode von am wenigsten absoluten Resten

In einer anderen Version des Algorithmus von Euklid wird der Quotient an jedem Schritt durch denjenigen vergrößert, wenn der resultierende negative Rest im Umfang kleiner ist als der typische positive Rest. Vorher, die Gleichung

: r = q r + r

angenommen dass |r> r> 0. Jedoch kann ein alternativer negativer Rest e geschätzt werden:

: r = (q + 1) r + e

wenn r> 0 oder

: r = (q - 1) r + e

wenn r, dann wird r durch e ersetzt. Als |r = r - e befriedigt dieser neue r

: |r / 2.

Leopold Kronecker hat gezeigt, dass diese Version wenigste Zahl von Schritten jeder Version des Algorithmus von Euklid verlangt.

Historische Entwicklung

Der Euklidische Algorithmus ist einer der ältesten Algorithmen noch in der üblichen Anwendung. Es erscheint in den Elementen von Euklid (c. 300 v. Chr.), spezifisch im Buch 7 (Vorschläge 1-2) und Buch 10 (Vorschläge 2-3). Im Buch 7 wird der Algorithmus für ganze Zahlen formuliert, wohingegen im Buch 10 es für Längen von Liniensegmenten formuliert wird. (Im modernen Gebrauch würde man sagen, dass er dort für reelle Zahlen formuliert wurde. Aber Längen, Gebiete, und Volumina, vertreten als reelle Zahlen im modernen Gebrauch, werden in denselben Einheiten nicht gemessen, und es gibt keine natürliche Einheit der Länge, des Gebiets oder des Volumens, und das Konzept von reellen Zahlen war damals unbekannt.) Der letzte Algorithmus ist geometrisch. Der GCD von zwei Längen a und b entspricht der größten Länge g, der a und b gleichmäßig misst; mit anderen Worten sind die Längen a und b beide Vielfachen der ganzen Zahl der Länge g.

Der Algorithmus wurde wahrscheinlich von Euklid nicht entdeckt, der Ergebnisse von früheren Mathematikern in seinen Elementen kompiliert hat. Der Mathematiker und Historiker B. L. van der Waerden schlagen vor, dass Buch VII auf ein Lehrbuch auf der Zahlentheorie zurückzuführen ist, die von Mathematikern in der Schule von Pythagoras geschrieben ist. Der Algorithmus war wahrscheinlich von Eudoxus von Cnidus (ungefähr 375 v. Chr.) bekannt. Der Algorithmus kann sogar Eudoxus zurückdatieren, nach dem Gebrauch des Fachbegriffs  (anthyphairesis, gegenseitige Subtraktion) in Arbeiten von Euklid und Aristoteles urteilend.

Einige Jahrhunderte später wurde der Algorithmus von Euklid unabhängig sowohl in Indien als auch in China entdeckt, um in erster Linie Gleichungen von Diophantine zu lösen, die in der Astronomie und dem Bilden genauer Kalender entstehen. Gegen Ende des fünften Jahrhunderts haben der Indianermathematiker und Astronom Aryabhata den Algorithmus als der "pulverizer", vielleicht wegen seiner Wirksamkeit im Lösen von Gleichungen von Diophantine beschrieben. Obwohl ein spezieller Fall des chinesischen Rest-Lehrsatzes bereits vom chinesischen Mathematiker und Astronomen Sun Tzu beschrieben worden war, wurde die allgemeine Lösung von Qin Jiushao veröffentlicht seinen 1247 schreiben Shushu Jiuzhang ( Mathematische Abhandlung in Neun Abteilungen) ein. Der Euklidische Algorithmus wurde zuerst in Europa in der zweiten Ausgabe von Problèmes plaisants von Bachet und délectables (Angenehme und angenehme Probleme, 1624) beschrieben. In Europa wurde es ebenfalls verwendet, um Gleichungen von Diophantine und im Entwickeln fortlaufender Bruchteile zu lösen. Der verlängerte Euklidische Algorithmus wurde vom englischen Mathematiker Nicholas Saunderson veröffentlicht, der ihn Roger Cotes zugeschrieben hat, als eine Methode, um zu rechnen, Bruchteile effizient fortgesetzt hat.

Im 19. Jahrhundert hat der Euklidische Algorithmus zur Entwicklung von neuen Zahl-Systemen, wie ganze Zahlen von Gaussian und ganze Zahlen von Eisenstein geführt. 1815 hat Carl Gauss den Euklidischen Algorithmus verwendet, um einzigartigen factorization von ganzen Zahlen von Gaussian zu demonstrieren, obwohl seine Arbeit zuerst 1832 veröffentlicht wurde. Gauss hat den Algorithmus in seinem Disquisitiones Arithmeticae (veröffentlichter 1801), aber nur als eine Methode für fortlaufende Bruchteile erwähnt. Peter Dirichlet scheint, erst gewesen zu sein, um den Euklidischen Algorithmus als die Basis für viel Zahlentheorie zu beschreiben. Dirichlet hat bemerkt, dass viele Ergebnisse der Zahlentheorie, wie einzigartiger factorization, für jedes andere System von Zahlen für wahr halten würden, auf die der Euklidische Algorithmus angewandt werden konnte. Die Vorträge von Dirichlet auf der Zahlentheorie wurden editiert und von Richard Dedekind erweitert, der den Algorithmus von Euklid verwendet hat, um algebraische ganze Zahlen, einen neuen allgemeinen Typ der Zahl zu studieren. Zum Beispiel war Dedekind erst, um den Zwei-Quadrate-Lehrsatz von Fermat mit dem einzigartigen factorization von ganzen Zahlen von Gaussian zu beweisen. Dedekind hat auch das Konzept eines Euklidischen Gebiets, eines Zahl-Systems definiert, in dem eine verallgemeinerte Version des Euklidischen Algorithmus (wie beschrieben, unten) definiert werden kann. In den Schlussjahrzehnten des 19. Jahrhunderts, jedoch, ist der Euklidische Algorithmus allmählich verfinstert durch die allgemeinere Theorie von Dedekind von Idealen geworden.

Andere Anwendungen des Algorithmus von Euklid wurden im 19. Jahrhundert entwickelt. 1829 hat Charles Sturm gezeigt, dass der Algorithmus in der Kettenmethode von Sturm nützlich war, für die echten Wurzeln von Polynomen in jedem gegebenen Zwischenraum aufzuzählen.

Der Euklidische Algorithmus war der erste Beziehungsalgorithmus der ganzen Zahl, der eine Methode ist, um Beziehungen der ganzen Zahl zwischen entsprechenden reellen Zahlen zu finden. Mehrere neuartige Beziehungsalgorithmen der ganzen Zahl sind in den letzten Jahren, wie der Algorithmus von Ferguson-Forcade (1979) von Helaman Ferguson und R.W. Forcade, und seinen Verwandten, dem LLL Algorithmus, dem HJLS Algorithmus und dem PSLQ Algorithmus entwickelt worden.

1969 haben Cole und Davie ein Zwei-Spieler-Spiel entwickelt, das auf dem Euklidischen Algorithmus gestützt ist, genannt Das Spiel von Euklid, der eine optimale Strategie hat. Die Spieler beginnen mit zwei Stapeln von a und b Steinen. Die Spieler wechseln sich ab, M Vielfachen des kleineren Stapels vom größeren entfernend. So, wenn die zwei Stapel aus x und y Steinen bestehen, wo x größer ist als y, kann der folgende Spieler den größeren Stapel von x Steinen bis x  meine Steine reduzieren, so lange der Letztere eine natürliche Zahl ist. Der Sieger ist der erste Spieler, um einen Stapel auf Nullsteine zu reduzieren.

Mathematische Anwendungen

Die Identität von Bézout

Die Identität von Bézout stellt fest, dass der größte allgemeine Teiler g zwei ganzer Zahlen a und b als eine geradlinige Summe der ursprünglichen zwei Zahlen a und b vertreten werden kann. Mit anderen Worten ist es immer möglich, ganze Zahlen s und t solch dass g = sa + tb zu finden.

Die ganzen Zahlen s und t können von den Quotienten q, q, usw. durch das Umkehren der Ordnung von Gleichungen im Algorithmus von Euklid berechnet werden. Mit der zweitletzten Gleichung beginnend, kann g in Bezug auf den Quotienten q und die zwei vorhergehenden Reste, r und r ausgedrückt werden.

: g = r = r  q r

Jene zwei Reste können in Bezug auf ihre Quotienten und vorhergehende Reste, ebenfalls ausgedrückt werden

: r = r  q r

: r = r  q r.

Das Auswechseln gegen diese Formeln für r und r in die erste Gleichung gibt g als eine geradlinige Summe der Reste r und r nach. Der Prozess, Reste durch Formeln einzusetzen, die ihre Vorgänger einbeziehen, kann fortgesetzt werden, bis die ursprünglichen Zahlen a und b erreicht werden

: r = r  q r

: r = b  q r

: r = ein  q b.

Nachdem alle Reste r, r, usw. eingesetzt worden sind, drückt die Endgleichung g als eine geradlinige Summe von a und b aus: g = sa + tb. Die Identität von Bézout, und deshalb der vorherige Algorithmus, können beide zum Zusammenhang von Euklidischen Gebieten verallgemeinert werden.

Hauptideale und verwandte Probleme

Die Identität von Bézout stellt noch eine andere Definition des größten allgemeinen Teilers g von zwei Zahlen a und b zur Verfügung. Denken Sie den Satz aller Zahlen ua + vb, wo u und v irgendwelche zwei ganzen Zahlen sind. Da a und b beide durch g teilbar sind, ist jede Zahl im Satz durch g teilbar. Mit anderen Worten ist jede Zahl des Satzes eine von g vielfache ganze Zahl. Das ist für jeden allgemeinen Teiler von a und b wahr. Jedoch, verschieden von anderen allgemeinen Teilern, ist der größte allgemeine Teiler ein Mitglied des Satzes; durch die Identität von Bézout, u = s und v = wählend, gibt t g. Ein kleinerer allgemeiner Teiler kann kein Mitglied des Satzes sein, da jedes Mitglied des Satzes durch g teilbar sein muss. Umgekehrt kann jede vielfache M von g durch die Auswahl u = Millisekunde und v = mt erhalten werden, wo s und t die ganzen Zahlen der Identität von Bézout sind. Das kann durch das Multiplizieren der Identität von Bézout durch die M, gesehen werden

: Mg = msa + mtb.

Deshalb ist der Satz aller Zahlen ua + vb zum Satz von Vielfachen M von g gleichwertig. Mit anderen Worten ist der Satz aller möglichen Summen von Vielfachen der ganzen Zahl von zwei Zahlen (a und b) zum Satz von Vielfachen von GCD (a, b) gleichwertig. Wie man sagt, ist der GCD der Generator des Ideales von a und b. Diese GCD Definition hat zu den modernen abstrakten algebraischen Konzepten eines Hauptideales (ein Ideal geführt, das durch ein einzelnes Element erzeugt ist) und ein ideales Hauptgebiet (ein Gebiet, in dem jedes Ideal ein Hauptideal ist).

Bestimmte Probleme können mit diesem Ergebnis behoben werden. Denken Sie zum Beispiel zwei Messtassen des Volumens a und b. Dadurch u Vielfachen der ersten Tasse und v Vielfachen der zweiten Tasse hinzufügen/abziehen, jedes Volumen ua + vb kann ausgemessen werden. Diese Volumina sind alle Vielfachen von g = GCD (a, b).

Verlängerter Euklidischer Algorithmus

Die ganzen Zahlen s und t der Identität von Bézout können effizient mit dem verlängerten Euklidischen Algorithmus geschätzt werden. Diese Erweiterung fügt zwei rekursive Gleichungen zum Algorithmus von Euklid hinzu

: s = s  qs

: t = t  qt

mit den Startwerten

: s = 1, t = 0

: s = 0, t = 1.

Mit diesem recursion werden die ganzen Zahlen von Bézout s und t durch s = s und t = t gegeben, wo N der Schritt ist, auf dem der Algorithmus mit r = 0 endet.

Die Gültigkeit dieser Annäherung kann durch die Induktion gezeigt werden. Nehmen Sie an, dass die recursion Formel bis zum Schritt k1 des Algorithmus richtig ist; nehmen Sie mit anderen Worten das an

: r = s + t b

für den ganzen j weniger als k. Der kth Schritt des Algorithmus gibt die Gleichung

: r = r  qr.

Seitdem, wie man angenommen hat, die recursion Formel für r und r richtig gewesen ist, können sie in Bezug auf den entsprechenden s und die t Variablen ausgedrückt werden

: r = (s + t b)  q (s + t b).

Umordnen dieser Gleichung gibt die recursion Formel für den Schritt k, wie erforderlich, nach

: r = s + t b = (s  qs) + (t  qt) b.

Matrixmethode

Die ganzen Zahlen s und t können auch mit einer gleichwertigen Matrixmethode gefunden werden. Die Folge von Gleichungen des Algorithmus von Euklid

: = q b + r: b = q r + r: …

: r = q r + 0

kann als ein Produkt 2 durch 2 des Quotienten matrices das Multiplizieren eines zweidimensionalen Rest-Vektoren geschrieben werden

:

\begin {pmatrix} \\b \end {pmatrix} =

\begin {pmatrix} q_0 & 1 \\1 & 0 \end {pmatrix} \begin {pmatrix} b \\r_ {0} \end {pmatrix} =

\begin {pmatrix} q_0 & 1 \\1 & 0 \end {pmatrix} \begin {pmatrix} q_1 & 1 \\1 & 0 \end {pmatrix} \begin {pmatrix} r_0 \\r_1 \end {pmatrix} =

\cdots =

\prod_ {i=0} ^N \begin {pmatrix} q_i & 1 \\1 & 0 \end {pmatrix} \begin {pmatrix} r_ {n-1} \\0 \end {pmatrix }\

</Mathematik>

Lassen Sie M das Produkt des ganzen Quotienten matrices vertreten

:

\mathbf {M} = \begin {pmatrix} m_ {11} & m_ {12} \\m_ {21} & m_ {22} \end {pmatrix} =

\prod_ {i=0} ^N \begin {pmatrix} q_i & 1 \\1 & 0 \end {pmatrix} =

\begin {pmatrix} q_0 & 1 \\1 & 0 \end {pmatrix} \begin {pmatrix} q_1 & 1 \\1 & 0 \end {pmatrix} \cdots \begin {pmatrix} q_ {N} & 1 \\1 & 0 \end {pmatrix }\

</Mathematik>

Das vereinfacht den Euklidischen Algorithmus zur Form

:\begin {pmatrix} \\b \end {pmatrix} =

\mathbf {M} \begin {pmatrix} r_ {n-1} \\0 \end {pmatrix} =

\mathbf {M} \begin {pmatrix} g \\0 \end {pmatrix }\

</Mathematik>

Um g als eine geradlinige Summe von a und b auszudrücken, können beide Seiten dieser Gleichung mit dem Gegenteil der MatrixM multipliziert werden. Die Determinante der M ist (1) gleich, da es dem Produkt der Determinanten des Quotienten matrices gleichkommt, von denen jeder negativer ist. Da die Determinante der M nie Null ist, kann der Vektor der Endreste mit dem Gegenteil der M gelöst werden

:

\begin {pmatrix} g \\0 \end {pmatrix} =

\mathbf {M} ^ {-1} \begin {pmatrix} \\b \end {pmatrix} =

(-1) ^ {N+1} \begin {pmatrix} m_ {22} &-m_ {12} \\-m_ {21} & m_ {11} \end {pmatrix} \begin {pmatrix} \\b \end {pmatrix }\

</Mathematik>

Da die Spitzengleichung gibt

:g = (1) (M eine  M b)

die zwei ganzen Zahlen der Identität von Bézout sind s = (1) M und t = (1) M. Die Matrixmethode ist so effizient wie der gleichwertige recursion, mit zwei Multiplikationen und zwei Hinzufügungen pro Schritt des Euklidischen Algorithmus.

Das Lemma von Euklid und einzigartiger factorization

Die Identität von Bézout ist für viele Anwendungen des Algorithmus von Euklid, wie das Demonstrieren des einzigartigen factorization von Zahlen in Hauptfaktoren notwendig. Um das zu illustrieren, nehmen Sie an, dass eine Nummer L als ein Produkt von zwei Faktoren u und v, d. h. L = uv geschrieben werden kann. Wenn eine andere Nummer w auch L teilt, aber coprime mit u ist, dann muss w v durch das folgende Argument teilen: Wenn der größte allgemeine Teiler von u und w 1 ist, dann können ganze Zahlen s und t solch dass gefunden werden

: 1 = su + tw

durch die Identität von Bézout. Das Multiplizieren beider Seiten durch v gibt die Beziehung

: v = suv + twv = sL + twv

Da w beide Begriffe auf der rechten Seite teilt, muss er auch die linke Seite, v teilen. Dieses Ergebnis ist als das Lemma von Euklid bekannt. Spezifisch, wenn eine Primzahl L teilt, dann muss es mindestens einen Faktor von L teilen. Umgekehrt, wenn eine Nummer w coprime zu jeder einer Reihe von Zahlen a, a, …, a ist, dann ist w auch coprime zu ihrem Produkt, ein × ein × … × a.

Das Lemma von Euklid genügt, um zu beweisen, dass jede Zahl einen einzigartigen factorization in Primzahlen hat. Um das zu sehen, nehmen Sie das Gegenteil an, dass es zwei unabhängige factorizations von L in die M und n Hauptfaktoren, beziehungsweise gibt

: L = Seiten … p = qq … q

Da jeder erste p L durch die Annahme teilt, muss es auch einen der q Faktoren teilen; da jeder q ebenso erst ist, muss es das p = q sein. Wiederholend zeigt das Teilen durch die p Faktoren, dass jeder p ein gleiches Seitenstück q hat; die zwei ersten factorizations sind abgesehen von ihrer Ordnung identisch. Der einzigartige factorization von Zahlen in die Blüte hat viele Anwendungen in mathematischen Beweisen, wie gezeigt, unten.

Geradlinige Diophantine Gleichungen

Gleichungen von Diophantine sind Gleichungen, in denen die Lösungen auf ganze Zahlen eingeschränkt werden; sie werden nach dem dritten Jahrhundert Mathematiker von Alexandrian Diophantus genannt. Eine typische geradlinige Gleichung von Diophantine sucht ganze Zahlen x und solchen y dass

: Axt + durch = c

wo a, b und c ganze Zahlen gegeben werden. Das kann als eine Gleichung für x in der Modularithmetik geschrieben werden

: Axt &equiv; c mod b.

Lassen Sie g der größte allgemeine Teiler von a und b sein. Beide Begriffe in der Axt + dadurch sind durch g teilbar; deshalb muss c auch durch g teilbar sein, oder die Gleichung hat keine Lösungen. Durch das Teilen beider Seiten durch c/g kann die Gleichung auf die Identität von Bezout reduziert werden

: sa + tb = g

wo s und t durch den verlängerten Euklidischen Algorithmus gefunden werden können. Das stellt eine Lösung der Gleichung von Diophantine, x = s (c/g) und y = t (c/g) zur Verfügung.

Im Allgemeinen hat eine geradlinige Gleichung von Diophantine keine Lösungen oder eine unendliche Zahl von Lösungen. Um die Letzteren zu finden, denken Sie zwei Lösungen, (x, y) und (x, y)

: Axt + durch = c = Axt + durch

oder gleichwertig

: (x  x) = b (y  y).

Deshalb ist der kleinste Unterschied zwischen zwei x Lösungen b/g, wohingegen der kleinste Unterschied zwischen zwei y Lösungen a/g ist. So können die Lösungen als ausgedrückt werden

:x = x  bt/g

:y = y + at/g.

Indem

sie t erlaubt, sich über alle möglichen ganzen Zahlen zu ändern, kann eine unendliche Familie von Lösungen von einer einzelnen Lösung (x, y) erzeugt werden. Wenn die Lösungen erforderlich sind, positive ganze Zahlen zu sein (x> 0, y> 0), kann nur eine begrenzte Zahl von Lösungen möglich sein. Diese Beschränkung der annehmbaren Lösungen erlaubt Systemen von Gleichungen von Diophantine, mit mehr unknowns gelöst zu werden, als Gleichungen; das ist für ein System von geradlinigen Gleichungen unmöglich, wenn die Lösungen jede reelle Zahl sein können.

Gegenteile von Multiplicative und der RSA Algorithmus

Ein begrenztes Feld ist eine Reihe von Zahlen mit vier verallgemeinerten Operationen. Die Operationen werden Hinzufügung, Subtraktion, Multiplikation und Abteilung genannt und haben ihre üblichen Eigenschaften, wie commutativity, associativity und distributivity. Ein Beispiel eines begrenzten Feldes ist der Satz von 13 Zahlen {0, 1, 2, …, 12} das Verwenden der Modularithmetik. In diesem Feld werden die Ergebnisse jeder mathematischen Operation (addition/subtraction/multiplication/division) modulo 13 reduziert; d. h. Vielfachen 13 werden hinzugefügt oder abgezogen, bis das Ergebnis innerhalb der Reihe 0-12 gebracht wird. Zum Beispiel, das Ergebnis von 5 × 7 = 35 mod 13 = 9. Solche begrenzten Felder können für jeden ersten p definiert werden; mit hoch entwickelteren Definitionen können sie auch für jede Macht M eines ersten p definiert werden. Begrenzte Felder werden häufig Felder von Galois genannt, und werden als GF (p) oder GF (p) abgekürzt.

In solch einem Feld mit der M Zahlen, jedes Nichtnullelement ein Haben eines einzigartigen multiplicative Modulgegenteils, ein solcher dass aa = aa  1 mod M. Dieses Gegenteil kann durch das Lösen der Kongruenz-Gleichungsaxt  1 mod M oder die gleichwertige geradlinige Gleichung von Diophantine gefunden werden

: Axt + mein = 1.

Diese Gleichung kann durch den Euklidischen Algorithmus, wie beschrieben, oben gelöst werden. Entdeckung multiplicative Gegenteile ist ein wesentlicher Schritt im RSA Algorithmus, der im elektronischen Handel weit verwendet wird; spezifisch beschließt die Gleichung, dass die ganze Zahl gepflegt hat, die Nachricht zu entschlüsseln. Bemerken Sie dass, obwohl die RSA Algorithmus-Gebrauch-Ringe aber nicht Felder, der Euklidische Algorithmus noch verwendet werden kann, um ein multiplicative Gegenteil zu finden, wo man besteht. Der Euklidische Algorithmus hat auch andere Anwendungen in Fehlerkorrekturcodes; zum Beispiel kann es als eine Alternative zum Berlekamp-Massey Algorithmus verwendet werden, um BCH und Codes des Rohres-Solomon zu decodieren, die auf Feldern von Galois basieren.

Chinesischer Rest-Lehrsatz

Der Algorithmus von Euklid kann auch verwendet werden, um vielfache geradlinige Gleichungen von Diophantine zu lösen. Solche Gleichungen entstehen im chinesischen Rest-Lehrsatz, der eine neuartige Methode beschreibt, eine ganze Zahl x zu vertreten. Anstatt eine ganze Zahl durch seine Ziffern zu vertreten, kann es durch seine Reste x modulo eine Reihe von N coprime Zahlen M vertreten werden.

: x &equiv; x mod M

: x &equiv; x mod M

: …

: x &equiv; x mod M

Die Absicht ist, x von seinen N Resten x zu bestimmen. Die Lösung ist, die vielfachen Gleichungen in eine einzelne geradlinige Gleichung von Diophantine mit einem viel größeren Modul M zu verbinden, die das Produkt aller individuellen Module M ist, und definieren Sie die M

: M = M / M

So ist jede M das Produkt aller Module außer der M. Die Lösung hängt davon ab, N neue Zahlen h solch dass zu finden

:Mh &equiv; 1 mod M

Mit diesen Zahlen h kann jede ganze Zahl x von seinen Resten x durch die Gleichung wieder aufgebaut werden

: x &equiv; (xMh + xMh + … + xMh) mod M

Seit diesen Zahlen sind h die multiplicative Gegenteile der M, sie können mit dem Algorithmus von Euklid, wie beschrieben, im vorherigen Paragraph gefunden werden.

Strenger-Brocot Baum

Die Folge von durch den Euklidischen Algorithmus verwendeten Subtraktionen gibt einen Pfad von der Wurzel des Strengen-Brocot Baums zu jeder gegebenen rationalen Zahl. Diese Tatsache kann verwendet werden, um zu beweisen, dass es eine 1-1 Ähnlichkeit zwischen den Scheitelpunkten des Baums und der positiven rationalen Zahlen gibt.

Zum Beispiel kann 3/4 durch das Starten an der Wurzel, das Gehen nach links einmal dann nach rechts zweimal gefunden werden.

:\begin {richten }\aus

& \gcd (3,4) & \leftarrow \\

& \gcd (3,1) & \rightarrow \\

& \gcd (2,1) & \rightarrow \\

& \gcd (1,1)

\end {richten }\aus</Mathematik>

Der Euklidische Algorithmus hat fast dieselbe Beziehung zum Baum des Stollens-Wilf. Der Unterschied ist, dass der Pfad umgekehrt wird: Anstatt einen Pfad von der Wurzel des Baums zu einem Ziel zu erzeugen, erzeugt es einen Pfad vom Ziel bis die Wurzel.

Fortlaufende Bruchteile

Der Euklidische Algorithmus hat eine nahe Beziehung mit fortlaufenden Bruchteilen. Die Folge von Gleichungen kann in der Form geschrieben werden

:\begin {richten }\aus

\frac {b} &= q_0 + \frac {r_0} {b} \\

\frac {b} {r_0} &= q_1 + \frac {r_1} {r_0} \\

\frac {r_0} {r_1} &= q_2 + \frac {r_2} {r_1} \\

& {}\\\vdots \\

\frac {r_ {k-2}} {r_ {k-1}} &= q_k + \frac {r_k} {r_ {k-1}} \\

& {}\\\vdots \\

\frac {r_ {n-2}} {r_ {n-1}} &= q_N

\end {richten }\aus</Mathematik>

Der letzte Begriff kommt auf der rechten Seite immer dem Gegenteil der linken Seite der folgenden Gleichung gleich. So können die ersten zwei Gleichungen verbunden werden, um zu bilden

:

Die dritte Gleichung kann verwendet werden, um den Nenner-Begriff r/r einzusetzen, tragend

:

Das Endverhältnis von Resten r/r kann immer mit der folgenden Gleichung in der Reihe bis zur Endgleichung ersetzt werden. Das Ergebnis ist ein fortlaufender Bruchteil

:

Im bearbeiteten Beispiel oben wurde der GCD (1071, 462) berechnet, und die Quotienten q waren 2, 3 und 7, beziehungsweise. Deshalb kann der Bruchteil 1071/462 geschrieben werden

:

wie durch die Berechnung bestätigt werden kann.

Algorithmen von Factorization

Das Rechnen eines größten allgemeinen Teilers ist ein wesentlicher Schritt in mehrerer ganzer Zahl factorization Algorithmen, wie der rho Algorithmus von Pollard, der Algorithmus von Shor, die factorization Methode von Dixon und Lenstra elliptische Kurve factorization. Der Euklidische Algorithmus kann verwendet werden, um diesen GCD effizient zu finden. Fortlaufender Bruchteil factorization Gebrauch hat Bruchteile fortgesetzt, die mit dem Algorithmus von Euklid bestimmt werden.

Algorithmische Leistungsfähigkeit

Die rechenbetonte Leistungsfähigkeit des Algorithmus von Euklid ist gründlich studiert worden. Diese Leistungsfähigkeit kann durch die Zahl von Schritten beschrieben werden, die der Algorithmus, multipliziert mit dem rechenbetonten Aufwand jedes Schritts verlangt. Wie gezeigt, zuerst durch Gabriel Lamé 1844 ist die Zahl von für die Vollziehung erforderlichen Schritten nie wieder als fünfmal die Nummer h von Ziffern (stützen Sie 10) der kleineren Nummer b. Da der rechenbetonte Aufwand jedes Schritts auch normalerweise des Auftrags h ist, wächst der gesamte Aufwand wie h.

Zahl von Schritten

Die Zahl von Schritten, den GCD von zwei natürlichen Zahlen, a und b zu berechnen, kann durch T (a, b) angezeigt werden. Wenn g der GCD von a und b, dann = Mg und b = ng für zwei coprime Zahlen M und n ist. Dann

: T (a, b) = T (M, n)

wie durch das Teilen aller Schritte im Euklidischen Algorithmus durch g gesehen werden kann. Durch dasselbe Argument bleibt die Zahl von Schritten dasselbe, wenn a und b mit einem gemeinsamen Faktor w multipliziert werden: T (a, b) = T (wa, wb). Deshalb kann sich die Zahl von Schritten T drastisch zwischen benachbarten Paaren von Zahlen, wie T (a, b) und T (a, b + 1) abhängig von der Größe der zwei GCDs ändern.

Die rekursive Natur des Euklidischen Algorithmus gibt eine andere Gleichung

: T (a, b) = 1 + T (b, r) = 2 + T (r, r) = … = N + T (r, r) = N + 1

wo T (x, 0) = 0 durch die Annahme.

Grenzfall-Zahl von Schritten

Wenn der Euklidische Algorithmus N-Schritte für ein Paar von natürlichen Zahlen a> b> 0 verlangt, sind die kleinsten Werte von a und b, für den das wahr ist, die Fibonacci-Zahlen F und F beziehungsweise. Das kann durch die Induktion gezeigt werden. Wenn sich N = 1, b ohne Rest teilt; die kleinsten natürlichen Zahlen, für die das wahr ist, sind b = 1 und = 2, die F und F beziehungsweise sind. Nehmen Sie jetzt an, dass das Ergebnis für alle Werte von N bis zur M  1 hält. Der erste Schritt der M Schritt-Algorithmus ist = qb + r, und der zweite Schritt ist b = qr + r. Da der Algorithmus rekursiv ist, hat er M  1 Schritte verlangt, GCD zu finden (b, r), und ihre kleinsten Werte sind F und F. Der kleinste Wert, deshalb wenn q = 1 zu sein, der = b + r = F + F = F gibt. Dieser Beweis, der von Gabriel Lamé 1844 veröffentlicht ist, vertritt den Anfang der rechenbetonten Kompliziertheitstheorie und auch der ersten praktischen Anwendung der Fibonacci-Zahlen.

Dieses Ergebnis genügt, um zu zeigen, dass die Zahl von Schritten im Algorithmus von Euklid mehr als fünfmal die Zahl seiner Ziffern nie sein kann (stützen Sie 10). Weil, wenn der Algorithmus N-Schritte verlangt, dann ist b größer oder gleich F, der der Reihe nach größer oder gleich φ ist, wo φ das goldene Verhältnis ist. Seitdem b  φ, dann N &minus; 1  logb. Seit logφ> 1/5, (N &minus; 1)/5 φ logb = logb. So, N  5 logb. So braucht der Euklidische Algorithmus immer weniger als O (h) Abteilungen, wo h die Zahl von Ziffern in der kleineren Nummer b ist.

Durchschnittliche Zahl von Schritten

Die durchschnittliche Zahl von durch den Euklidischen Algorithmus gemachten Schritten ist auf drei verschiedene Weisen definiert worden. Die erste Definition ist die durchschnittliche Zeit T (a) erforderlich, den GCD einer gegebenen Zahl a und einer kleineren natürlichen Zahl b gewählt mit der gleichen Wahrscheinlichkeit aus den ganzen Zahlen 0 zu einem  1 zu berechnen

:

T (a) = \frac {1} {ein} \sum_ {0 \leq b

Jedoch, seitdem T (a, b) schwankt drastisch mit dem GCD der zwei Zahlen, die durchschnittliche Funktion T (a) ist ebenfalls "laut".

Um dieses Geräusch zu reduzieren, wird ein zweiter Durchschnitt τ (a) alle Zahlen coprime mit einem übernommen

:

\tau (a) = \frac {1} {\\varphi (a)} \sum_ {0 \leq b

Es gibt φ (a) coprime ganze Zahlen weniger als a, wo φ die Totient-Funktion von Euler ist. Dieser tau Durchschnitt wächst glatt mit einem

:τ (a) = (12/π) ln 2 ln + C + O (ein)

mit dem Restfehler, der von der Ordnung a ist, wo ε unendlich klein ist. Der unveränderliche C in dieser Formel kommt gleich

:C =  (1/2) + 6 (ln 2/π) (4γ  24πζ' (2) + 3 ln 2  2)  1.467

wo γ die Euler-Mascheroni Konstante ist und ζ' die Ableitung des Riemanns zeta Funktion ist. Der Hauptkoeffizient (12/π) ln 2 wurde durch zwei unabhängige Methoden bestimmt.

Da der erste Durchschnitt vom tau Durchschnitt durch das Summieren über die Teiler d von einem berechnet werden kann

:

T (a) = \frac {1} {ein} \sum_ {d |} \varphi (d) \tau (d)

</Mathematik>

ihm kann durch die Formel näher gekommen werden

:T (a)  C + (12/π) ln 2 (ln ein  Σ Λ (d)/d)

wo Λ (d) die Funktion von Mangoldt ist.

Ein dritter Durchschnitt Y (n) wird als die Mittelzahl von erforderlichen Schritten definiert, wenn sowohl a als auch b zufällig (mit der Rechteckverteilung) von 1 bis n gewählt werden

:

Y (n) = \frac {1} {n^ {2}} \sum_ {a=1} ^n \sum_ {b=1} ^n T (a, b) = \frac {1} {n} \sum_ {a=1} ^n T (a).

</Mathematik>

Das Auswechseln gegen die ungefähre Formel für T (a) in diese Gleichung gibt eine Schätzung für Y (n) nach

:Y (n)  (12/π) ln 2 ln n + 0.06.

Rechenbetonter Aufwand pro Schritt

In jedem Schritt k des Euklidischen Algorithmus werden der Quotient q und Rest r für ein gegebenes Paar von ganzen Zahlen r und r geschätzt

: r = q r + r.

Der rechenbetonte Aufwand pro Schritt wird hauptsächlich mit der Entdeckung q vereinigt, da der Rest r schnell von r, r, und q berechnet werden kann

: r = r  q r.

Der rechenbetonte Aufwand von sich teilenden H-Bit-Zahlen klettert als O (h ( +1)), wo  die Länge des Quotienten ist.

Zum Vergleich kann der ursprüngliche Subtraktionsbasierte Algorithmus von Euklid viel langsamer sein. Eine einzelne Abteilung der ganzen Zahl ist zum Quotienten q Zahl von Subtraktionen gleichwertig. Wenn das Verhältnis von a und b sehr groß ist, ist der Quotient groß, und viele Subtraktionen werden erforderlich sein. Andererseits ist es gezeigt worden, dass die Quotienten sehr wahrscheinlich kleine ganze Zahlen sein werden. Die Wahrscheinlichkeit eines gegebenen Quotienten q ist ungefähr ln|u / (u  1) | wo u = (q + 1). Für die Illustration ist die Wahrscheinlichkeit eines Quotienten 1, 2, 3, oder 4 ungefähr 41.5 %, 17.0 %, 9.3 % und 5.9 % beziehungsweise. Da die Operation der Subtraktion schneller ist als Abteilung besonders für die große Anzahl, ist der Algorithmus des Subtraktionsbasierten Euklids mit der Abteilungsbasierten Version konkurrenzfähig. Das wird in der binären Version des Algorithmus von Euklid ausgenutzt.

Das Kombinieren der geschätzten Zahl von Schritten mit dem geschätzten rechenbetonten Aufwand pro Schritt zeigt, dass der Algorithmus von Euklid quadratisch (h) mit der durchschnittlichen Zahl von Ziffern h in den anfänglichen zwei Zahlen a und b wächst. Lassen Sie h, h, …, h vertreten die Zahl von Ziffern in den aufeinander folgenden Resten r, r, …, r. Seit der Zahl von Schritten wächst N geradlinig mit h, die Laufzeit wird durch begrenzt

:

O\Big (\sum_ {ich

Leistungsfähigkeit von alternativen Methoden

Der Algorithmus von Euklid wird in der Praxis besonders für kleine Zahlen wegen seiner Einfachheit weit verwendet. Zum Vergleich kann die Leistungsfähigkeit von Alternativen zum Algorithmus von Euklid bestimmt werden.

Eine ineffiziente Annäherung an die Entdeckung des GCD von zwei natürlichen Zahlen a und b soll alle ihre allgemeinen Teiler berechnen; der GCD ist dann der größte allgemeine Teiler. Die allgemeinen Teiler können durch das Teilen beider Zahlen durch aufeinander folgende ganze Zahlen von 2 bis die kleinere Nummer b gefunden werden. Die Zahl von Schritten dieser Annäherung wächst geradlinig mit b, oder exponential in der Zahl von Ziffern. Eine andere ineffiziente Annäherung soll die Hauptfaktoren von einem oder beiden Zahlen finden. Wie bemerkt, oben kommt der GCD dem Produkt der Hauptfaktoren gleich, die durch die zwei Zahlen a und b geteilt sind. Vorliegende Methoden für ersten factorization sind auch ineffizient; viele moderne Geheimschrift-Systeme verlassen sich sogar auf diese Wirkungslosigkeit.

Der binäre GCD Algorithmus ist eine effiziente Alternative, die Abteilung mit schnelleren Operationen durch die Ausnutzung der binären durch Computer verwendeten Darstellung einsetzt. Jedoch klettert diese Alternative auch wie O (h ²). Es ist allgemein schneller als der Euklidische Algorithmus auf echten Computern, wenn auch es ebenso klettert. Zusätzliche Leistungsfähigkeit kann durch das Überprüfen nur der Hauptziffern der zwei Zahlen a und b nachgelesen werden. Der binäre Algorithmus kann zu anderen Basen (k-ary Algorithmen), mit bis zu fünffachen Zunahmen in der Geschwindigkeit erweitert werden.

Eine rekursive Annäherung für sehr große ganze Zahlen (mit mehr als 25,000 Ziffern) führt zu subquadratischer ganzer Zahl GCD Algorithmen, wie diejenigen von Schönhage, und Stehlé und Zimmermann. Diese Algorithmen nutzen 2×2 Matrixform des Euklidischen Algorithmus aus, der oben gegeben ist. Diese subquadratischen Methoden klettern allgemein als

Andere Zahl-Systeme

Wie beschrieben, oben wird der Euklidische Algorithmus verwendet, um den größten allgemeinen Teiler von zwei natürlichen Zahlen (positive ganze Zahlen) zu finden. Jedoch kann es zu den reellen Zahlen, und zu exotischeren Zahl-Systemen wie Polynome, quadratische ganze Zahlen und Hurwitz quaternions verallgemeinert werden. In den letzten Fällen wird der Euklidische Algorithmus verwendet, um das entscheidende Eigentum von einzigartigem factorization zu demonstrieren, d. h., dass solche Zahlen factored einzigartig in nicht zu vereinfachende Elemente, die Kopien von Primzahlen sein können. Einzigartiger factorization ist für viele Beweise der Zahlentheorie notwendig.

Rationale Zahlen und reelle Zahlen

Der Algorithmus von Euklid kann auf reelle Zahlen, wie beschrieben, von Euklid im Buch 10 seiner Elemente angewandt werden. Die Absicht des Algorithmus ist, eine reelle Zahl g solch zu identifizieren, dass zwei gegebene reelle Zahlen, a und b, Vielfachen der ganzen Zahl davon sind: = Mg und b = ng, wo M und n ganze Zahlen sind. Diese Identifizierung ist zur Entdeckung einer Beziehung der ganzen Zahl unter den reellen Zahlen a und b gleichwertig; d. h. es bestimmt ganze Zahlen s und solchen t dass sa + tb = 0. Euklid verwendet diesen Algorithmus, um die Frage von nicht vergleichbaren Längen zu behandeln.

Die reelle Zahl Euklidischer Algorithmus unterscheidet sich von seinem Kollegen der ganzen Zahl in zwei Hinsicht. Erstens sind die Reste r reelle Zahlen, obwohl die Quotienten q ganze Zahlen wie zuvor sind. Zweitens, wie man versichert, endet der Algorithmus in einer begrenzten Nummer N von Schritten nicht. Wenn es tut, ist der Bruchteil a/b eine rationale Zahl, d. h., das Verhältnis von zwei ganzen Zahlen

: a/b = mg/ng = m/n

und kann als ein begrenzter fortlaufender Bruchteil [q geschrieben werden; q, q, …, q]. Wenn der Algorithmus nicht anhält, ist der Bruchteil a/b eine irrationale Zahl und kann durch einen unendlichen fortlaufenden Bruchteil [q beschrieben werden; q, q, …]. Beispiele von unendlichen fortlaufenden Bruchteilen sind das goldene Verhältnis φ = [1; 1, 1, …] und die Quadratwurzel zwei, 2 = [1; 2, 2, …]. Im Allgemeinen wird der Algorithmus kaum anhalten, da fast alle Verhältnisse a/b zwei reeller Zahlen vernunftwidrig sind.

Ein unendlicher fortlaufender Bruchteil kann an einem Schritt k [q gestutzt sein; q, q, …, um q] eine Annäherung an a/b nachzugeben, der sich verbessert, weil wird k vergrößert. Die Annäherung wird durch convergents m/n beschrieben; der Zähler und die Nenner sind coprime und folgen dem recursion

:m = q M + M

:n = q n + n

wo M = n = 1 und M = n = 0 die Anfangswerte des recursion sind. Der konvergente m/n ist die beste Annäherung der rationalen Zahl an a/b mit dem Nenner n:

:

\left |\frac {b} - \frac {m_k} {n_k }\\Recht |

Polynome

Polynome in einer einzelnen Variable x können hinzugefügt, multipliziert werden und factored in nicht zu vereinfachende Polynome, die die Analoga der Primzahlen für ganze Zahlen sind. Das größte allgemeine Teiler-Polynom g (x) von zwei Polynomen (x) und b (x) wird als das Produkt ihrer geteilten nicht zu vereinfachenden Polynome definiert, die mit dem Euklidischen Algorithmus identifiziert werden können. Das grundlegende Verfahren ist ganzen Zahlen ähnlich. An jedem Schritt k werden ein Quotient-Polynom q (x) und ein Rest-Polynom r (x) identifiziert, um die rekursive Gleichung zu befriedigen

: r (x) = q (x) r (x) + r (x)

wo r (x) = (x) und r (x) = b (x). Das Quotient-Polynom wird gewählt, so dass der Hauptbegriff von q (x) r (x) dem Hauptbegriff von r (x) gleichkommt; das stellt sicher, dass der Grad jedes Rests kleiner ist als der Grad seines Vorgängers deg [r (x)] (x)]. Da der Grad eine natürliche Zahl ist, und da er mit jedem Schritt abnimmt, hört der Euklidische Algorithmus in einer begrenzten Zahl von Schritten auf. Der Endnichtnullrest ist der größte allgemeine Teiler der ursprünglichen zwei Polynome, (x) und b (x).

Denken Sie zum Beispiel die folgenden zwei quartic Polynome, der jeder Faktor in zwei quadratische Polynome

: (x) = x  4x + 4 x  3x + 14 = (x  5x + 7) (x + x + 2)

und

: b (x) = x + 8x + 12x + 17x + 6 = (x + 7x + 3) (x + x + 2).

Das Teilen (x) durch b (x) Erträge ein Rest r (x) = x + (2/3) x + (5/3) x  (2/3). Im nächsten Schritt, b (x) wird durch r (x) das Nachgeben eines Rests r (x) = x + x + 2 geteilt. Schließlich, sich r (x) durch r (x) Erträge ein Nullrest teilend, anzeigend, dass r (x) das größte allgemeine Teiler-Polynom (x) und b (x), im Einklang stehend mit ihrem factorization ist.

Viele der Anwendungen, die oben für ganze Zahlen beschrieben sind, tragen zu Polynomen vor. Der Euklidische Algorithmus kann verwendet werden, um geradlinige Gleichungen von Diophantine und chinesische Rest-Probleme für Polynome zu lösen; fortlaufende Bruchteile von Polynomen können auch definiert werden.

Der polynomische Euklidische Algorithmus hat andere Anwendungen ebenso, wie Ketten von Sturm, eine Methode, für die Zahl von echten Wurzeln eines Polynoms innerhalb eines gegebenen Zwischenraums auf der echten Achse aufzuzählen. Das hat Anwendungen in mehreren Gebieten wie das Routh-Hurwitz Stabilitätskriterium in der Steuerungstheorie.

Schließlich brauchen die Koeffizienten der Polynome nicht von ganzen Zahlen, reellen Zahlen oder sogar den komplexen Zahlen gezogen zu werden. Zum Beispiel können die Koeffizienten von einem allgemeinen Feld, wie die begrenzten Felder GF (p) beschrieben oben gezogen werden. Die entsprechenden Beschlüsse über den Euklidischen Algorithmus und seine Anwendungen halten sogar für solche Polynome.

Ganze Zahlen von Gaussian

Die Gaussian ganzen Zahlen sind komplexe Zahlen der Form α = u + vi, wo u und v gewöhnliche ganze Zahlen sind und ich die Quadratwurzel von negativer bin. Durch das Definieren eines Analogons des Euklidischen Algorithmus, wie man zeigen kann, sind ganze Zahlen von Gaussian einzigartig factorizable durch das Argument oben. Dieser einzigartige factorization ist in vielen Anwendungen nützlich, wie das Abstammen des ganzen Pythagoreers verdreifacht sich oder Beweis des Lehrsatzes von Fermat auf Summen von zwei Quadraten. Im Allgemeinen ist der Euklidische Algorithmus in solchen Anwendungen günstig, aber nicht notwendig; zum Beispiel können die Lehrsätze häufig durch andere Argumente bewiesen werden.

Der Euklidische Algorithmus, der für zwei ganze Zahlen von Gaussian α und β entwickelt ist, ist fast dasselbe als das für normale ganze Zahlen, aber unterscheidet sich in zwei Hinsicht. Wie zuvor ist die Aufgabe an jedem Schritt k, einen Quotienten q und einen Rest r solch dass zu identifizieren

: r = r  q r

wo r = α, r = β, und jeder Rest ausschließlich kleiner ist als sein Vorgänger, |r. Der erste Unterschied ist, dass die Quotienten und Reste selbst ganze Zahlen von Gaussian sind, und so komplexe Zahlen sind. Die Quotienten q werden allgemein durch das Runden der echten und komplizierten Teile des genauen Verhältnisses (wie die komplexe Zahl α/β) zu den nächsten ganzen Zahlen gefunden. Der zweite Unterschied liegt in der Notwendigkeit des Definierens, wie ein komplizierter Rest "kleiner" sein kann als ein anderer. Um das zu tun, definieren wir eine Norm-Funktion f (u + vi) = u + v, der jede ganze Zahl von Gaussian u + vi in eine normale ganze Zahl umwandelt. Nach jedem Schritt k des Euklidischen Algorithmus ist die Norm des Rests f (r) kleiner als die Norm des vorhergehenden Rests, f (r). Da die Norm eine natürliche Zahl und Abnahmen mit jedem Schritt, dem Euklidischen Algorithmus seit Enden der ganzen Zahlen von Gaussian in einer begrenzten Zahl von Schritten ist. Der Endnichtnullrest ist der GCD (α,β), die ganze Zahl von Gaussian der größten Norm, die sowohl α als auch β teilt; es ist bis zur Multiplikation durch eine Einheit, ±1 oder ±i einzigartig.

Viele der anderen Anwendungen des Euklidischen Algorithmus tragen zu ganzen Zahlen von Gaussian vor. Zum Beispiel kann es verwendet werden, um geradlinige Gleichungen von Diophantine und chinesische Rest-Probleme für ganze Zahlen von Gaussian zu lösen; fortlaufende Bruchteile von ganzen Zahlen von Gaussian können auch definiert werden.

Euklidische Gebiete

Eine Reihe von Elementen unter zwei binären Operationen, + und ·, wird ein Euklidisches Gebiet genannt, wenn es einen Ersatzring R und, grob das Sprechen bildet, wenn ein verallgemeinerter Euklidischer Algorithmus auf ihnen durchgeführt werden kann. Die zwei Operationen solch eines Rings brauchen nicht die Hinzufügung und Multiplikation der gewöhnlichen Arithmetik zu sein; eher können sie, wie die Operationen einer mathematischen Gruppe oder monoid allgemeiner sein. Dennoch sollten diese allgemeinen Operationen viele der Gesetze respektieren, gewöhnliche Arithmetik, wie commutativity, associativity und distributivity regelnd.

Der verallgemeinerte Euklidische Algorithmus verlangt eine Euklidische Funktion, d. h., ein kartografisch darstellender f von R in den Satz von solchen natürlichen Zahlen, dass, für irgendwelche zwei Nichtnullelemente a und b in R, dort q und r in solchem R bestehen, dass = qb + r und f (r) Einzigartiger factorization auch ein Schlüsselelement in einem versuchten Beweis des Letzten Lehrsatzes von Fermat veröffentlicht 1847 von Gabriel Lamé, demselben Mathematiker war, der die Leistungsfähigkeit des Algorithmus von Euklid analysiert hat, der auf einem Vorschlag von Joseph Liouville gestützt ist. Die Annäherung von Lamé hat den einzigartigen factorization von Zahlen der Form x + ωy verlangt, wo x und y ganze Zahlen sind, und ω = e eine n-te Wurzel 1, d. h. ω = 1 ist. Obwohl diese Annäherung für einige Werte von n erfolgreich ist (wie n=3, die ganzen Zahlen von Eisenstein), im Allgemeinen tun solche Zahlen nicht Faktor einzigartig. Dieser Misserfolg von einzigartigem factorization in einigen cyclotomic Feldern hat Ernst Kummer zum Konzept idealer Zahlen und, später, Richard Dedekind zu Idealen geführt.

Einzigartiger factorization von quadratischen ganzen Zahlen

Die quadratischen Ringe der ganzen Zahl sind nützlich, um Euklidische Gebiete zu illustrieren. Quadratische ganze Zahlen sind Generalisationen der ganzen Zahlen von Gaussian, in denen die imaginäre Einheit ich durch eine Zahl ω ersetzt werde. So haben sie die Form u + v ω, wo u und v ganze Zahlen sind und ω eine von zwei Formen, abhängig von einem Parameter D hat. Wenn D keinem Vielfache vier plus eines, dann gleichkommt

: ω = D.

Wenn, jedoch, D wirklich einem Vielfache vier plus eines, dann gleichkommt

: ω = (1 + D)/2.

Wenn die Funktion f einer Norm-Funktion entspricht, wie das hat gepflegt, die ganzen Zahlen von Gaussian oben zu bestellen, dann ist das Gebiet als mit der Norm euklidisch bekannt. Die mit der Norm euklidischen Ringe von quadratischen ganzen Zahlen sind genau diejenigen wo D = 11, 7, 3, 2, 1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 oder 73. Die quadratischen ganzen Zahlen mit D = 1 und 3 sind als die ganzen Zahlen von Gaussian und ganzen Zahlen von Eisenstein beziehungsweise bekannt.

Wenn f erlaubt wird, Euklidische Funktion zu sein, dann ist die Liste von möglichen D-Werten, für die das Gebiet Euklidisch ist, noch nicht bekannt. Das erste Beispiel eines Euklidischen Gebiets, das nicht mit der Norm euklidisch war (mit D = 69) wurde 1994 veröffentlicht. 1973 hat Weinberger bewiesen, dass ein quadratischer Ring der ganzen Zahl mit D> 0 Euklidisch ist, wenn, und nur wenn es ein ideales Hauptgebiet ist, vorausgesetzt, dass die verallgemeinerte Hypothese von Riemann hält.

Nichtersatzringe

Es ist auch möglich, den Euklidischen Algorithmus auf Nichtersatzringe wie der Satz von Hurwitz quaternions anzuwenden. Lassen Sie α, und β vertreten zwei Elemente von solch einem Ring. Sie haben einen allgemeinen richtigen Teiler δ wenn α = ξδ und β = ηδ für etwas Wahl von ξ und η im Ring. Ähnlich haben sie einen allgemeinen linken Teiler wenn α = δξ und β = δη für etwas Wahl von ξ und η im Ring. Da Multiplikation nicht auswechselbar ist, gibt es zwei Versionen des Euklidischen Algorithmus, ein für richtige Teiler und ein für linke Teiler. Die richtigen Teiler wählend, kann der erste Schritt in der Entdeckung des GCD (α, β) durch den Euklidischen Algorithmus geschrieben werden

: ρ = α  ψβ = (ξ  ψη)δ\

wo ψ den Quotienten und ρ der Rest vertritt. Diese Gleichung zeigt, dass jeder allgemeine richtige Teiler von α und β ebenfalls ein allgemeiner Teiler des Rests ρ ist. Die analoge Gleichung für die linken Teiler würde sein

: ρ = α  βψ = δ (ξ  ηψ)

Entweder mit der Wahl wird der Prozess als oben wiederholt, bis der größte allgemeine richtige oder linke Teiler identifiziert wird. Als im Euklidischen Gebiet muss die "Größe" des Rests ρ ausschließlich kleiner sein als β, und es muss nur eine begrenzte Zahl möglicher Größen für ρ geben, so dass, wie man versichert, der Algorithmus endet.

Die meisten Ergebnisse für den GCD tragen zu Nichtersatzzahlen vor. Zum Beispiel stellt die Identität von Bézout fest, dass der richtige GCD (α, β) als eine geradlinige Kombination von α und β ausgedrückt werden kann. Mit anderen Worten gibt es Zahlen σ und solcher τ dass

: Γ = σα + τβ\

Die analoge Identität für den linken GCD ist fast derselbe

: Γ = ασ + βτ\

Die Identität von Bézout kann verwendet werden, um Gleichungen von Diophantine zu lösen.

Generalisationen zu anderen mathematischen Strukturen

Der Euklidische Algorithmus hat drei allgemeine Eigenschaften, die zusammen sicherstellen, dass er unbestimmt nicht weitergehen wird. Erstens kann es als eine Folge von rekursiven Gleichungen geschrieben werden

: r = r  q r

wo jeder Rest ausschließlich kleiner ist als sein Vorgänger, |r. Zweitens hat die Größe jedes Rests einen strengen tiefer, beschränken wie |r  0. Drittens gibt es nur eine begrenzte Zahl von Größen, die kleiner sind als ein gegebener Rest |r. Generalisationen des Algorithmus von Euklid mit diesen grundlegenden Eigenschaften sind auf andere mathematische Strukturen, wie Gewirr und transfinite Ordinalzahlen angewandt worden.

Eine wichtige Generalisation des Euklidischen Algorithmus ist das Konzept einer Basis von Gröbner in der algebraischen Geometrie. Wie gezeigt, oben, der GCD g zwei ganzer Zahlen a und b ist der Generator ihres Ideales. Mit anderen Worten, für jede Wahl der ganzen Zahlen s und t, gibt es eine andere ganze Zahl solche M dass

: sa + tb = Mg.

Obwohl das wahr bleibt, wenn s, t, M, a und b Polynome einer einzelnen Variable vertreten, ist es für Ringe von mehr als einer Variable nicht wahr. In diesem Fall kann ein begrenzter Satz von Generator-Polynomen g, g, usw. solch definiert werden, dass jede geradlinige Kombination von zwei mehrvariablen Polynomen a und b als Vielfachen der Generatoren ausgedrückt werden kann

: sa + tb = Σ Mg

wo s, t und M mehrvariable Polynome sind. Jedes solches mehrvariable Polynom f kann als solch eine Summe von Generator-Polynomen plus ein einzigartiges Rest-Polynom r ausgedrückt, manchmal die normale Form des Polynoms f genannt werden

: f = r + Σ qg

obwohl die Quotient-Polynome q nicht einzigartig sein können. Der Satz dieser Generator-Polynome ist als eine Basis von Gröbner bekannt.

Siehe auch

• Binärer GCD Algorithmus
• Größter allgemeiner Teiler von zwei Polynomen
• Beziehungsalgorithmus der ganzen Zahl
• Der GCD Algorithmus von Lehmer

Referenzen

• a. Einige weit verwendete Lehrbücher, wie ich. Die Themen von N. Herstein in der Algebra und der Algebra von Serge Lang, gebrauchen Sie den Begriff "Euklidischer Algorithmus", um sich auf den Abteilungsalgorithmus zu beziehen. Jedoch ist der Abteilungsalgorithmus ein Lehrsatz, nicht ein Algorithmus.

Bibliografie

• . Siehe auch Vorlesungen über Zahlentheorie

Links

• Demonstrationen des Algorithmus von Euklid
• Der Algorithmus von Euklid an der Knoten-Kürzung
• Der euklidische Algorithmus an MathPages
• Das Spiel von Euklid an der Knoten-Kürzung
• Musik und der Algorithmus von Euklid