Euklidischer Algorithmus - Euclidean algorithm

Euklids Methode zum Finden des größten gemeinsamen Teilers (GCD) von zwei Startlängen BA und DC, die beide als Vielfache einer gemeinsamen "Einheitslänge" definiert sind. Da die Länge DC kürzer ist, wird sie zum "Messen" von BA verwendet, jedoch nur einmal, da der Rest EA kleiner als DC ist. EA misst nun (zweimal) die kürzere Länge DC, wobei der Rest FC kürzer als EA ist. Dann misst FC (dreimal) die Länge EA. Da kein Rest übrig bleibt, endet der Prozess damit, dass FC der GCD ist. Rechts das Beispiel von Nicomachus mit den Zahlen 49 und 21, die zu ihrem GCD von 7 führen (abgeleitet von Heath 1908:300).

In der Mathematik ist der euklidische Algorithmus oder der Euklid-Algorithmus eine effiziente Methode zur Berechnung des größten gemeinsamen Teilers (GCD) von zwei ganzen Zahlen (Zahlen), der größten Zahl, die beide ohne Rest teilt . Es ist nach dem antiken griechischen Mathematiker Euklid benannt , der es erstmals in seinen Elementen (ca. 300 v. Chr.) beschrieb. Es ist ein Beispiel für einen Algorithmus , ein schrittweises Verfahren zum Durchführen einer Berechnung nach wohldefinierten Regeln, und ist einer der ältesten gebräuchlichen Algorithmen. Es kann verwendet werden, um Brüche auf ihre einfachste Form zu reduzieren , und ist Teil vieler anderer zahlentheoretischer und kryptographischer Berechnungen.

Der euklidische Algorithmus basiert auf dem Prinzip, dass sich der größte gemeinsame Teiler zweier Zahlen nicht ändert, wenn die größere Zahl durch ihre Differenz mit der kleineren Zahl ersetzt wird. Zum Beispiel ist 21 die GCD von 252 und 105 (als 252 = 21 × 12 und 105 = 21 × 5), und dieselbe Zahl 21 ist auch die GCD von 105 und 252 − 105 = 147. Da diese Ersetzung die größeren der beiden Zahlen ergibt das Wiederholen dieses Vorgangs nacheinander kleinere Zahlenpaare, bis die beiden Zahlen gleich werden. In diesem Fall sind sie die GCD der beiden ursprünglichen Zahlen. Durch Umkehrung der Schritte oder Verwendung des erweiterten euklidischen Algorithmus kann die GCD als Linearkombination der beiden ursprünglichen Zahlen ausgedrückt werden, d. h. die Summe der beiden Zahlen, die jeweils mit einer ganzen Zahl multipliziert werden (zum Beispiel 21 = 5 × 105 + (−2) × 252). Dass sich die GCD immer auf diese Weise ausdrücken lässt, wird als Bézouts Identität bezeichnet .

Die oben beschriebene Version des euklidischen Algorithmus (und von Euklid) kann viele Subtraktionsschritte benötigen, um die GCD zu finden, wenn eine der gegebenen Zahlen viel größer ist als die andere. Eine effizientere Version des Algorithmus verkürzt diese Schritte und ersetzt stattdessen die größere der beiden Zahlen durch ihren Rest, wenn sie durch die kleinere der beiden geteilt wird (bei dieser Version stoppt der Algorithmus, wenn ein Rest von Null erreicht wird). Mit dieser Verbesserung erfordert der Algorithmus nie mehr Schritte als das Fünffache der Anzahl der Stellen (Basis 10) der kleineren ganzen Zahl. Dies wurde 1844 von Gabriel Lamé bewiesen und markiert den Beginn der Computational Complexity Theory . Im 20. Jahrhundert wurden weitere Methoden zur Verbesserung der Effizienz des Algorithmus entwickelt.

Der euklidische Algorithmus hat viele theoretische und praktische Anwendungen. Es wird verwendet, um Brüche auf ihre einfachste Form zu reduzieren und um eine Division in modularer Arithmetik durchzuführen . Berechnungen, die diesen Algorithmus verwenden , sind Teil der kryptografischen Protokolle , die zur Sicherung der Internetkommunikation verwendet werden, und in Verfahren zum Brechen dieser Kryptosysteme durch Faktorisieren großer zusammengesetzter Zahlen . Der euklidische Algorithmus kann verwendet werden , zu lösen Diophantische Gleichungen , wie Zahlen zu finden , die nach dem mehrfachen Kongruenzen erfüllen chinesischen Restsatz , zu konstruieren Fraktionen fortgesetzt und präzise finden rationale Annäherungen an reellen Zahlen. Schließlich kann es als grundlegendes Werkzeug zum Beweisen von Theoremen in der Zahlentheorie wie dem Vier-Quadrat-Theorem von Lagrange und der Eindeutigkeit von Primfaktorzerlegungen verwendet werden . Der ursprüngliche Algorithmus wurde beschrieben nur für natürliche Zahlen und geometrische Längen (reelle Zahlen), aber der Algorithmus wurde im 19. Jahrhundert auf andere Arten von Zahlen, wie generali Gaußschen Zahlen und Polynomen einer Variablen. Dies führte zu modernen abstrakten algebraischen Begriffen wie euklidischen Domänen .

Hintergrund: größter gemeinsamer Teiler

Der euklidische Algorithmus berechnet den größten gemeinsamen Teiler (GCD) zweier natürlicher Zahlen a und b . Der größte gemeinsame Teiler g ist die größte natürliche Zahl, die a und b ohne Rest teilt . Synonyme für den GCD sind der größte gemeinsame Faktor (GCF), der höchste gemeinsame Faktor (HCF), der höchste gemeinsame Teiler (HCD) und das größte gemeinsame Maß (GCM). Der größte gemeinsame Teiler wird oft als gcd( ab ) oder einfacher als ( ab ) geschrieben, obwohl letztere Notation mehrdeutig ist, wird sie auch für Konzepte wie ein Ideal im Ring der ganzen Zahlen verwendet , was eng im Zusammenhang mit GCD.

Wenn gcd( ab ) = 1, dann heißen a und b teilerfremd (oder teilerfremd). Diese Eigenschaft impliziert nicht, dass a oder b selbst Primzahlen sind . Zum Beispiel ist weder 6 noch 35 eine Primzahl, da beide zwei Primfaktoren haben: 6 = 2 × 3 und 35 = 5 × 7. Trotzdem sind 6 und 35 teilerfremd. Keine andere natürliche Zahl als 1 teilt sowohl 6 als auch 35, da sie keine gemeinsamen Primfaktoren haben.

"Großes, schlankes Rechteck, das in ein Raster von Quadraten unterteilt ist. Das Rechteck ist zwei Quadrate breit und fünf Quadrate hoch."
Ein 24-mal-60-Rechteck wird mit zehn 12-mal-12-Quadratkacheln bedeckt, wobei 12 die GCD von 24 und 60 ist. Allgemeiner kann ein a- mal- b- Rechteck mit quadratischen Kacheln der Seitenlänge c . bedeckt werden nur wenn c ein gemeinsamer Teiler von a und b ist .

Sei g = gcd( ab ). Da a und b beide Vielfache von g sind , können sie a  =  mg und b  =  ng geschrieben werden , und es gibt keine größere Zahl G  >  g, für die dies gilt. Die natürlichen Zahlen m und n müssen teilerfremd sein, da jeder gemeinsame Faktor aus m und n herausgerechnet werden könnte , um g größer zu machen . Somit muss jede andere Zahl c , die sowohl a als auch b teilt, auch g teilen . Der größte gemeinsame Teiler g von a und b ist der eindeutige (positive) gemeinsame Teiler von a und b , der durch jeden anderen gemeinsamen Teiler c teilbar ist .

Die GCD kann wie folgt visualisiert werden. Betrachten Sie eine rechteckige Fläche a durch b und einen beliebigen gemeinsamen Teiler c , der sowohl a als auch b exakt teilt . Die Seiten des Rechtecks ​​können in Segmente der Länge c unterteilt werden , wodurch das Rechteck in ein Raster von Quadraten der Seitenlänge c unterteilt wird . Der größte gemeinsame Teiler g ist der größte Wert von c, für den dies möglich ist. Zur Veranschaulichung kann ein rechteckiger Bereich von 24 x 60 in ein Raster unterteilt werden: 1-mal-1-Quadrate, 2-mal-2-Quadrate, 3-mal-3-Quadrate, 4-mal-4-Quadrate, 6-mal -6 Quadrate oder 12 x 12 Quadrate. Daher ist 12 der größte gemeinsame Teiler von 24 und 60. Eine rechteckige Fläche von 24 x 60 kann in ein Raster von 12 x 12 Quadraten unterteilt werden, mit zwei Quadraten entlang einer Kante (24/12 = 2) und fünf Quadrate entlang der anderen (60/12 = 5).

Die GCD zweier Zahlen a und b ist das Produkt der Primfaktoren, die sich die beiden Zahlen teilen, wobei ein Primfaktor mehrmals verwendet werden kann, aber nur solange das Produkt dieser Faktoren sowohl a als auch b teilt . Da beispielsweise 1386 in 2 × 3 × 3 × 7 × 11 zerlegt werden kann und 3213 in 3 × 3 × 3 × 7 × 17 zerlegt werden kann, ist der größte gemeinsame Teiler von 1386 und 3213 gleich 63 = 3 × 3 × 7, das Produkt ihrer gemeinsamen Primfaktoren. Wenn zwei Zahlen keine gemeinsamen Primfaktoren haben, ist ihr größter gemeinsamer Teiler 1 (hier als Instanz des leeren Produkts erhalten ), also teilerfremd. Ein wesentlicher Vorteil des euklidischen Algorithmus besteht darin, dass er die GCD effizient finden kann, ohne die Primfaktoren berechnen zu müssen. Es wird angenommen, dass die Faktorisierung großer Ganzzahlen ein rechentechnisch sehr schwieriges Problem ist, und die Sicherheit vieler weit verbreiteter kryptografischer Protokolle basiert auf ihrer Undurchführbarkeit.

Eine andere Definition der GCD ist in der fortgeschrittenen Mathematik hilfreich, insbesondere in der Ringtheorie . Der größte gemeinsame Teiler g   zweier von Null verschiedenen Zahlen a und b ist auch ihre kleinste positive ganzzahlige Linearkombination, d. h. die kleinste positive Zahl der Form ua  +  vb, wobei u und v ganze Zahlen sind. Die Menge aller ganzzahligen Linearkombinationen von a und b ist eigentlich dieselbe wie die Menge aller Vielfachen von g ( mg , wobei m eine ganze Zahl ist). In der modernen Sprache der Mathematik, die ideal , die durch ein und b ist die durch erzeugt ideal  g allein (eine von einem Element erzeugt ideal ist ein sogenannter Hauptideal , und alle Ideale der ganzen Zahlen sind Hauptideale). Einige Eigenschaften der GCD sind mit dieser Beschreibung tatsächlich leichter zu erkennen, zum Beispiel die Tatsache, dass jeder gemeinsame Teiler von a und b auch die GCD teilt (er teilt beide Terme von ua  +  vb ). Die Äquivalenz dieser GCD-Definition mit den anderen Definitionen wird unten beschrieben.

Der GCD von drei oder mehr Zahlen ist gleich dem Produkt der allen Zahlen gemeinsamen Primfaktoren, kann aber auch durch wiederholtes Nehmen der GCDs von Zahlenpaaren berechnet werden. Zum Beispiel,

gcd( abc ) = gcd( a , gcd( bc )) = gcd(gcd( ab ),  c ) = gcd(gcd( ac ),  b ).

Somit reicht der Algorithmus von Euklid, der die GCD von zwei ganzen Zahlen berechnet, aus, um die GCD von beliebig vielen ganzen Zahlen zu berechnen.

Beschreibung

Verfahren

Der euklidische Algorithmus läuft in einer Reihe von Schritten ab, so dass die Ausgabe jedes Schrittes als Eingabe für den nächsten verwendet wird. Sei k eine ganze Zahl, die die Schritte des Algorithmus zählt, beginnend mit Null. Somit entspricht der Anfangsschritt k  = 0, der nächste Schritt entspricht k  = 1 und so weiter.

Jeder Schritt beginnt mit zwei nichtnegativen Resten r k −1 und r k −2 . Da der Algorithmus dafür sorgt, dass die Reste mit jedem Schritt stetig abnehmen, ist r k −1 kleiner als sein Vorgänger r k −2 . Das Ziel des k- ten Schrittes ist es, einen Quotienten q k und Rest r k zu finden , der die Gleichung

und die 0 ≤ r k  <  r k –1 haben . Mit anderen Worten werden Vielfache der kleineren Zahl r k –1 von der größeren Zahl r k –2 abgezogen, bis der Rest r k kleiner als r k –1 ist .

Im ersten Schritt ( k  = 0) sind die Reste r −2 und r −1 gleich a und b , den Zahlen, für die die GCD gesucht wird. Im nächsten Schritt ( k  = 1) sind die Reste gleich b und der Rest r 0 des Anfangsschrittes und so weiter. Somit kann der Algorithmus als Folge von Gleichungen geschrieben werden

Wenn a kleiner als b ist , vertauscht der erste Schritt des Algorithmus die Zahlen. Wenn beispielsweise a  <  b ist , ist der anfängliche Quotient q 0 gleich Null und der Rest r 0 ist a . Somit ist r k kleiner als sein Vorgänger r k −1 für alle k  ≥ 0.

Da die Reste mit jedem Schritt abnehmen, aber niemals negativ sein können, muss ein Rest r N schließlich gleich Null sein, an welchem ​​Punkt der Algorithmus stoppt. Der letzte von Null verschiedene Rest r N −1 ist der größte gemeinsame Teiler von a und b . Die Zahl N kann nicht unendlich sein, da zwischen dem Anfangsrest r 0 und Null nur endlich viele nichtnegative ganze Zahlen liegen .

Gültigkeitsnachweis

Die Gültigkeit des euklidischen Algorithmus kann durch ein zweistufiges Argument bewiesen werden. Im ersten Schritt wird gezeigt , dass der letzte von Null verschiedene Rest r N −1 sowohl a als auch b teilt . Da es sich um einen gemeinsamen Teiler handelt, muss er kleiner oder gleich dem größten gemeinsamen Teiler g sein . Im zweiten Schritt wird gezeigt, dass jeder gemeinsame Teiler von a und b , einschließlich g , r N −1 teilen muss ; daher muss g kleiner oder gleich r N −1 sein . Diese beiden Schlussfolgerungen sind widersprüchlich, es sei denn, r N −1  =  g .

Um zu zeigen, dass r N −1 sowohl a als auch b teilt (erster Schritt), teilt r N −1 seinen Vorgänger r N −2

r N −2 = q N r N −1

da der letzte Rest r N Null ist. r N −1 teilt auch seinen nächsten Vorgänger r N −3

r N −3 = q N −1 r N −2 + r N −1

weil es beide Terme auf der rechten Seite der Gleichung teilt. Durch Iterieren desselben Arguments dividiert r N −1 alle vorhergehenden Reste, einschließlich a und b . Keiner der vorhergehenden Reste r N –2 , r N –3 usw. teilen a und b , da sie einen Rest hinterlassen. Da r N −1 ein gemeinsamer Teiler von a und b ist , gilt r N −1  ≤  g .

Im zweiten Schritt teilt jede natürliche Zahl c , die sowohl a als auch b teilt (mit anderen Worten, jeder gemeinsame Teiler von a und b ) die Reste r k . Per Definition können a und b als Vielfaches von c geschrieben werden  : a  =  mc und b  =  nc , wobei m und n natürliche Zahlen sind. Daher dividiert c den anfänglichen Rest r 0 , da r 0  =  a  −  q 0 b  =  mc  −  q 0 nc  = ( m  −  q 0 n ) c . Ein analoges Argument zeigt, dass c auch die nachfolgenden Reste r 1 , r 2 usw. teilt . Daher muss der größte gemeinsame Teiler g r N −1 teilen , was impliziert, dass g  ≤  r N −1 . Da der erste Teil des Arguments das Gegenteil zeigt ( r N −1  ≤  g ), folgt g  =  r N −1 . Somit ist g der größte gemeinsame Teiler aller folgenden Paare:

g = gcd( a , b ) = gcd( b , r 0 ) = gcd( r 0 , r 1 ) = … = gcd( r N −2 , r N −1 ) = r N −1 .

Gearbeitetes Beispiel

Animation, bei der zunehmend kleinere quadratische Kacheln hinzugefügt werden, um ein Rechteck vollständig abzudecken.
Subtraktionsbasierte Animation des euklidischen Algorithmus. Das ursprüngliche Rechteck hat die Abmessungen a  = 1071 und b  = 462. Quadrate der Größe 462 × 462 werden darin platziert, sodass ein Rechteck von 462 × 147 übrig bleibt. Dieses Rechteck wird mit 147 × 147 Quadraten gekachelt, bis ein 21 × 147-Rechteck übrig bleibt, das wiederum mit 21 × 21 Quadraten gekachelt wird, sodass keine unbedeckte Fläche übrig bleibt. Die kleinste Quadratgröße, 21, ist die GCD von 1071 und 462.

Zur Veranschaulichung kann der euklidische Algorithmus verwendet werden, um den größten gemeinsamen Teiler von a  = 1071 und b  = 462 zu finden. Zu Beginn werden Vielfache von 462 von 1071 abgezogen, bis der Rest kleiner als 462 ist. Zwei solche Vielfache können subtrahiert werden ( q 0  = 2), wobei ein Rest von 147 übrig bleibt:

1071 = 2 × 462 + 147.

Dann werden Vielfache von 147 von 462 abgezogen, bis der Rest kleiner als 147 ist. Drei Vielfache können subtrahiert werden ( q 1  = 3), so dass ein Rest von 21 verbleibt:

462 = 3 × 147 + 21.

Dann werden Vielfache von 21 von 147 abgezogen, bis der Rest kleiner als 21 ist. Sieben Vielfache können subtrahiert werden ( q 2  = 7), wobei kein Rest übrig bleibt :

147 = 7 × 21 + 0.

Da der letzte Rest null ist, endet der Algorithmus mit 21 als dem größten gemeinsamen Teiler von 1071 und 462. Dies stimmt mit der oben durch die Primfaktorzerlegung gefundenen gcd(1071, 462) überein . In tabellarischer Form sind die Schritte:

Schritt k Gleichung Quotient und Rest
0 1071 = q 0 462 + r 0 q 0 = 2 und r 0 = 147
1 462 = q 1 147 + r 1 q 1 = 3 und r 1 = 21
2 147 = q 2 21 + R 2 q 2 = 7 und r 2 = 0 ; Algorithmus endet

Visualisierung

Der euklidische Algorithmus kann anhand der oben angegebenen Kachelanalogie für den größten gemeinsamen Teiler visualisiert werden. Angenommen, wir möchten ein a- mal- b- Rechteck genau mit quadratischen Kacheln überdecken , wobei a die größere der beiden Zahlen ist. Wir versuchen zunächst, das Rechteck mit b- mal- b- Quadratkacheln zu kacheln ; dies lässt jedoch ein r 0 -mal- b- Restrechteck unbelegt, wobei r 0  <  b ist . Wir versuchen dann, das Restrechteck mit r 0 -by- r 0 quadratischen Kacheln zu kacheln . Dies hinterlässt ein zweites Restrechteck r 1 -by- r 0 , das wir versuchen, mit r 1 -by- r 1 quadratischen Kacheln zu kacheln , und so weiter. Die Sequenz endet, wenn kein Restrechteck vorhanden ist, dh wenn die quadratischen Kacheln das vorherige Restrechteck genau überdecken. Die Länge der Seiten der kleinsten quadratischen Kachel ist die GCD der Abmessungen des ursprünglichen Rechtecks. Die kleinste quadratische Kachel in der nebenstehenden Abbildung ist beispielsweise 21 x 21 (in Rot dargestellt) und 21 ist die GCD von 1071 und 462, den Abmessungen des ursprünglichen Rechtecks ​​(in Grün dargestellt).

Euklidische Teilung

Bei jedem Schritt k berechnet der euklidische Algorithmus einen Quotienten q k und Rest r k aus zwei Zahlen r k −1 und r k −2

r k −2 = q k r k −1 + r k

wobei r k nicht negativ ist und strikt kleiner als der Absolutwert von r k –1 ist . Der Satz, der der Definition der euklidischen Division zugrunde liegt, stellt sicher, dass ein solcher Quotient und ein solcher Rest immer existieren und eindeutig sind.

In Euklids Originalversion des Algorithmus werden Quotient und Rest durch wiederholte Subtraktion gefunden; das heißt, r k –1 wird wiederholt von r k –2 subtrahiert, bis der Rest r k kleiner als r k –1 ist . Danach werden r k und r k –1 ausgetauscht und der Prozess iteriert. Die euklidische Division reduziert alle Schritte zwischen zwei Börsen in einen einzigen Schritt, der somit effizienter ist. Außerdem werden die Quotienten nicht benötigt, daher kann man die euklidische Division durch die Modulo-Operation ersetzen , die nur den Rest ergibt. Damit wird die Iteration des euklidischen Algorithmus einfach

R k = R k -2 mod r k -1 .

Implementierungen

Implementierungen des Algorithmus können in Pseudocode ausgedrückt werden . Zum Beispiel kann die Division-basierte Version wird programmiert als

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

Zu Beginn der k- ten Iteration enthält die Variable b den letzten Rest r k −1 , während die Variable a ihren Vorgänger r k −2 enthält . Der Schritt b  := a mod b entspricht der obigen Rekursionsformel r kr k −2 mod r k −1 . Die temporäre Variable t hält den Wert von r k –1 während der nächste Rest r k berechnet wird. Am Ende der Schleifeniteration enthält die Variable b den Rest r k , während die Variable a ihren Vorgänger r k −1 enthält .

(Wenn negative Eingaben erlaubt sind oder die mod- Funktion negative Werte zurückgeben kann, muss die letzte Zeile in return max (a, −a) geändert werden .)

In der subtraktionsbasierten Version, der ursprünglichen Version von Euklid, wird die Restberechnung ( ) durch wiederholte Subtraktion ersetzt. Im Gegensatz zur Divisions-basierten Version, die mit beliebigen ganzen Zahlen als Eingabe arbeitet, geht die subtraktionsbasierte Version davon aus, dass die Eingabe aus positiven ganzen Zahlen besteht und stoppt, wenn a = b : b := a mod b

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

Die Variablen a und b halten abwechselnd die vorherigen Reste r k –1 und r k -2 . Angenommen, a ist zu Beginn einer Iteration größer als b ; dann ist a gleich r k -2 , da r k -2 > r k -1 . Während der Schleifeniteration wird a um ein Vielfaches des vorherigen Rests b reduziert, bis a kleiner als b ist . Dann a ist der nächste Rest r k . Dann wird b um ein Vielfaches von a reduziert, bis es wieder kleiner als a ist , was den nächsten Rest r k +1 ergibt , und so weiter.

Die rekursive Version basiert auf der Gleichheit der GCDs aufeinander folgender Reste und der Stoppbedingung gcd( r N −1 , 0) =  r N −1 .

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

(Wie oben, wenn negative Eingaben erlaubt sind oder die mod- Funktion negative Werte zurückgeben kann, muss die Anweisung " return a" in " return max (a, −a)" geändert werden .)

Zur Veranschaulichung wird der gcd(1071, 462) aus dem äquivalenten gcd(462, 1071 mod 462) = gcd(462, 147) berechnet. Letzteres GCD berechnet sich aus gcd(147, 462 mod 147) = gcd(147, 21), die wiederum aus gcd(21, 147 mod 21) = gcd(21, 0) = 21 berechnet wird.

Methode der kleinsten absoluten Reste

In einer anderen Version des Algorithmus von Euklid wird der Quotient bei jedem Schritt um eins erhöht, wenn der resultierende negative Rest betragsmäßig kleiner ist als der typische positive Rest. Zuvor war die Gleichung

r k −2 = q k r k −1 + r k

angenommen, dass | r k −1 | >  R k  > 0 ist . Es kann jedoch ein alternativer negativer Rest e k berechnet werden:

r k −2 = ( q k + 1) r k −1 + e k

wenn r k −1  > 0 oder

r k −2 = ( q k − 1) r k −1 + e k

wenn r k –1  < 0 .

Wenn r k durch e k ersetzt wird . wenn | e k | < | r k | , dann erhält man eine Variante des euklidischen Algorithmus, so dass

| r k | | r k −1 | / 2

bei jedem Schritt.

Leopold Kronecker hat gezeigt, dass diese Version die wenigsten Schritte von allen Versionen des Euklid-Algorithmus erfordert. Allgemeiner gesagt wurde bewiesen, dass für jede Eingabezahl a und b die Anzahl der Schritte genau dann minimal ist, wenn q k in der Reihenfolge gewählt wird, wo der goldene Schnitt ist .

Historische Entwicklung

"Darstellung von Euklid als bärtiger Mann, der ein Paar Trennwände an eine Tafel hält."
Der euklidische Algorithmus wurde wahrscheinlich vor Euklid erfunden , der hier in einem Gemälde von etwa 1474 einen Kompass hält .

Der euklidische Algorithmus ist einer der ältesten gebräuchlichen Algorithmen. Es erscheint in Euklids Elements (ca. 300 v. Chr.), insbesondere in Buch 7 (Propositionen 1-2) und Buch 10 (Propositionen 2-3). In Buch 7 wird der Algorithmus für ganze Zahlen formuliert, während er in Buch 10 für Längen von Liniensegmenten formuliert wird. (Im modernen Sprachgebrauch würde man sagen, dass es dort für reelle Zahlen formuliert wurde . Aber Längen, Flächen und Volumen, die im modernen Sprachgebrauch als reelle Zahlen dargestellt werden, werden nicht in den gleichen Einheiten gemessen und es gibt keine natürliche Einheit für Länge, Fläche, oder Volumen; das Konzept der reellen Zahlen war zu dieser Zeit unbekannt.) Der letztere Algorithmus ist geometrisch. Die GCD von zwei Längen a und b entspricht der größten Länge g , die a und b gleichmäßig misst ; mit anderen Worten, die Längen a und b sind beide ganzzahlige Vielfache der Länge g .

Der Algorithmus wurde wahrscheinlich nicht von Euklid entdeckt , der in seinen Elementen die Ergebnisse früherer Mathematiker zusammengetragen hat . Der Mathematiker und Historiker BL van der Waerden schlägt vor, dass Buch VII aus einem Lehrbuch über die Zahlentheorie stammt, das von Mathematikern in der Schule des Pythagoras geschrieben wurde . Der Algorithmus war wahrscheinlich von Eudoxus von Knidos (ca. 375 v. Chr.) bekannt. Der Algorithmus könnte sogar Eudoxus vorausgehen , wenn man von der Verwendung des Fachbegriffs ἀνθυφαίρεσις ( Anthyphairese , reziproke Subtraktion) in Werken von Euklid und Aristoteles urteilt .

Jahrhunderte später wurde Euklids Algorithmus sowohl in Indien als auch in China unabhängig voneinander entdeckt, hauptsächlich um diophantische Gleichungen zu lösen , die in der Astronomie entstanden und genaue Kalender zu erstellen. Im späten 5. Jahrhundert beschrieb der indische Mathematiker und Astronom Aryabhata den Algorithmus als "Pulverisierer", vielleicht wegen seiner Wirksamkeit bei der Lösung diophantischer Gleichungen. Obwohl ein Spezialfall des chinesischen Restsatzes bereits im chinesischen Buch Sunzi Suanjing beschrieben wurde , wurde die allgemeine Lösung von Qin Jiushao in seinem 1247 erschienenen Buch Shushu Jiuzhang (數書九章Mathematical Treatise in Nine Sections ) veröffentlicht. Der euklidische Algorithmus wurde zum ersten Mal beschrieben numerisch in der zweiten Auflage in Europa und popularisierte Bachet der Problèmes plaisants et Delectables ( angenehm und erfreulich Probleme , 1624). In Europa wurde ebenfalls verwendet Diophantine Gleichungen und in der Entwicklung zu lösen Fraktionen fortgesetzt . Der erweiterte euklidische Algorithmus wurde von dem englischen Mathematiker Nicholas Saunderson veröffentlicht , der ihn Roger Cotes als Methode zur effizienten Berechnung von Kettenbrüchen zuschrieb .

Im 19. Jahrhundert führte der euklidische Algorithmus zur Entwicklung neuer Zahlensysteme, wie Gaußsche Ganzzahlen und Eisenstein-Ganzzahlen . Im Jahr 1815 verwendete Carl Gauss den Euklidischen Algorithmus, um die einzigartige Faktorisierung von Gaußschen ganzen Zahlen zu demonstrieren , obwohl seine Arbeit erstmals 1832 veröffentlicht wurde. Gauss erwähnte den Algorithmus in seinen Disquisitiones Arithmeticae (veröffentlicht 1801), jedoch nur als Methode für Kettenbrüche . Peter Gustav Lejeune Dirichlet scheint der erste gewesen zu sein, der den euklidischen Algorithmus als Grundlage für einen Großteil der Zahlentheorie beschrieben hat. Lejeune Dirichlet bemerkte, dass viele Ergebnisse der Zahlentheorie, wie die eindeutige Faktorisierung, für jedes andere Zahlensystem gelten würden, auf das der euklidische Algorithmus angewendet werden könnte. Die Vorlesungen von Lejeune Dirichlet über Zahlentheorie wurden von Richard Dedekind herausgegeben und erweitert , der den Euklid-Algorithmus benutzte, um algebraische ganze Zahlen , einen neuen allgemeinen Zahlentyp , zu studieren . Zum Beispiel war Dedekind der erste, der den Zweiquadratsatz von Fermat unter Verwendung der einzigartigen Faktorisierung von Gaußschen ganzen Zahlen bewies. Dedekind definierte auch das Konzept einer euklidischen Domäne , ein Zahlensystem, in dem eine verallgemeinerte Version des euklidischen Algorithmus definiert werden kann (wie unten beschrieben ). In den letzten Jahrzehnten des 19. Jahrhunderts wurde der euklidische Algorithmus allmählich von Dedekinds allgemeinerer Idealtheorie in den Schatten gestellt .

"[Der euklidische Algorithmus] ist der Urvater aller Algorithmen, weil er der älteste nichttriviale Algorithmus ist, der bis heute überlebt hat."

Donald Knuth , Die Kunst der Computerprogrammierung, Bd. 2: Seminumerical Algorithms , 2. Auflage (1981), p. 318.

Andere Anwendungen des Algorithmus von Euklid wurden im 19. Jahrhundert entwickelt. Im Jahr 1829 zeigte Charles Sturm , dass der Algorithmus in der Sturm-Kettenmethode zum Zählen der reellen Nullstellen von Polynomen in jedem gegebenen Intervall nützlich ist .

Der euklidische Algorithmus war der erste ganzzahlige Relationsalgorithmus , der eine Methode zum Auffinden ganzzahliger Relationen zwischen entsprechenden reellen Zahlen ist. Es wurden mehrere neuartige ganzzahlige Relationsalgorithmen entwickelt, wie der Algorithmus von Helaman Ferguson und RW Forcade (1979) und der LLL-Algorithmus .

1969 entwickelten Cole und Davie ein Spiel für zwei Spieler, das auf dem euklidischen Algorithmus basiert, genannt The Game of Euclid , das eine optimale Strategie hat. Die Spieler beginnen mit zwei Haufen ein und b Steinen. Die Spieler entfernen abwechselnd m Vielfache des kleineren Stapels vom größeren. Wenn also die beiden Stapel aus x und y Steinen bestehen, wobei x größer als y ist , kann der nächste Spieler den größeren Stapel von x Steinen auf xmeine Steine reduzieren , solange letztere eine nicht negative ganze Zahl ist. Der Gewinner ist der erste Spieler, der einen Stapel auf null Steine ​​reduziert hat.

Mathematische Anwendungen

Bézouts Identität

Bézouts Identität besagt, dass der größte gemeinsame Teiler g zweier ganzer Zahlen a und b als lineare Summe der beiden ursprünglichen Zahlen a und b dargestellt werden kann . Mit anderen Worten, es ist immer möglich, ganze Zahlen s und t zu finden, so dass g  =  sa  +  tb .

Die ganzen Zahlen s und t können aus den Quotienten q 0 , q 1 usw. berechnet werden, indem die Reihenfolge der Gleichungen im Euklid-Algorithmus umgekehrt wird. Ausgehend von der vorletzten Gleichung kann g durch den Quotienten q N −1 und die beiden vorhergehenden Reste r N −2 und r N −3 ausgedrückt werden :

g = r N −1 = r N −3q N −1 r N −2  .

Diese beiden Reste können ebenfalls durch ihre Quotienten und vorhergehenden Reste ausgedrückt werden,

r N −2 = r N −4q N −2 r N −3 und
r N –3 = r N –5q N –3 r N –4  .

Einsetzen dieser Formeln für r N –2 und r N –3 in die erste Gleichung ergibt g als lineare Summe der Reste r N –4 und r N –5 . Der Vorgang des Ersetzens von Resten durch Formeln mit ihren Vorgängern kann fortgesetzt werden, bis die ursprünglichen Zahlen a und b erreicht sind:

r 2 = r 0q 2 r 1
r 1 = bq 1 r 0
r 0 = aq 0 b .

Nachdem alle Reste r 0 , r 1 usw. ersetzt wurden, drückt die letzte Gleichung g als eine lineare Summe von a und b aus : g  =  sa  +  tb . Die Identität von Bézout und damit der vorherige Algorithmus können beide auf den Kontext euklidischer Domänen verallgemeinert werden .

Hauptideale und verwandte Probleme

Die Identität von Bézout liefert noch eine weitere Definition des größten gemeinsamen Teilers g zweier Zahlen a und b . Betrachten Sie die Menge aller Zahlen ua  +  vb , wobei u und v zwei beliebige ganze Zahlen sind. Da a und b beide durch g teilbar sind , ist jede Zahl in der Menge durch g teilbar . Mit anderen Worten, jede Zahl der Menge ist ein ganzzahliges Vielfaches von g . Dies gilt für jeden gemeinsamen Teiler von a und b . Im Gegensatz zu anderen gemeinsamen Teilern ist der größte gemeinsame Teiler jedoch ein Mitglied der Menge; nach Bézouts Identität ergibt die Wahl von u  =  s und v  =  t g . Ein kleinerer gemeinsamer Teiler kann kein Mitglied der Menge sein, da jedes Mitglied der Menge durch g teilbar sein muss . Umgekehrt können beliebige Vielfache m von g erhalten werden, indem u  =  ms und v  =  mt gewählt werden , wobei s und t die ganzen Zahlen der Bézout-Identität sind. Dies kann man sehen, indem man Bézouts Identität mit m multipliziert ,

mg = msa + mtb .

Daher ist die Menge aller Zahlen ua  +  vb äquivalent zur Menge der Vielfachen m von g . Mit anderen Worten, die Menge aller möglichen Summen ganzzahliger Vielfacher zweier Zahlen ( a und b ) entspricht der Menge der Vielfachen von gcd ( a , b ). Die GCD wird als Generator des Ideals von a und b bezeichnet . Diese GCD-Definition führte zu den modernen abstrakten algebraischen Konzepten eines Hauptideals (ein Ideal, das von einem einzelnen Element erzeugt wird) und eines Hauptidealbereichs (ein Bereich, in dem jedes Ideal ein Hauptideal ist).

Bestimmte Probleme können mit diesem Ergebnis gelöst werden. Betrachten Sie zum Beispiel zwei Messbecher mit Volumen a und b . Durch Addieren/Subtrahieren von u Vielfachen des ersten Bechers und v Vielfachen des zweiten Bechers kann jedes Volumen ua  +  vb ausgemessen werden. Diese Volumina sind alle Vielfache von g  = gcd( ab ).

Erweiterter euklidischer Algorithmus

Die ganzen Zahlen s und t der Bézout-Identität können unter Verwendung des erweiterten euklidischen Algorithmus effizient berechnet werden . Diese Erweiterung fügt dem Euklid-Algorithmus zwei rekursive Gleichungen hinzu

s k = s k −2q k s k −1
t k = t k -2 - q k t k -1

mit den Startwerten

s −2 = 1, t −2 = 0
s −1 = 0, t −1 = 1.

Unter Verwendung dieser Rekursion sind die ganzen Zahlen s und t von Bézout gegeben durch s  =  s N und t  =  t N , wobei N+1 der Schritt ist, auf dem der Algorithmus mit r N+1  = 0 endet .

Die Gültigkeit dieses Ansatzes kann durch Induktion gezeigt werden. Nehmen Sie an, dass die Rekursionsformel bis zum Schritt k  − 1 des Algorithmus korrekt ist ; mit anderen Worten, nehmen Sie an, dass

r j = s j a + t j b

für alle j kleiner als k . Der k- te Schritt des Algorithmus ergibt die Gleichung

R k = R k -2 - q k R k -1 .

Da angenommen wurde, dass die Rekursionsformel für r k −2 und r k −1 korrekt ist , können sie durch die entsprechenden s- und t- Variablen ausgedrückt werden

r k = ( s k –2 a + t k –2 b ) – q k ( s k –1 a + t k –1 b ).

Die Umordnung dieser Gleichung ergibt die Rekursionsformel für Schritt k , wie erforderlich

r k = s k a + t k b = ( s k −2q k s k −1 ) a + ( t k −2q k t k −1 ) b .

Matrixmethode

Die ganzen Zahlen s und t können auch mit einem äquivalenten Matrixverfahren gefunden werden. Die Gleichungsfolge des Euklidschen Algorithmus

kann als Produkt von 2-mal-2 Quotientenmatrizen geschrieben werden, die einen zweidimensionalen Restvektor multiplizieren

Sei M das Produkt aller Quotientenmatrizen

Dies vereinfacht den euklidischen Algorithmus auf die Form

Um g als lineare Summe von a und b auszudrücken , können beide Seiten dieser Gleichung mit dem Inversen der Matrix M multipliziert werden . Die Determinante von M ist gleich (−1) N +1 , da sie gleich dem Produkt der Determinanten der Quotientenmatrizen ist, von denen jede negativ ist. Da die Determinante von M niemals Null ist, kann der Vektor der Endreste mit der Inversen von M . gelöst werden

Da die obere Gleichung ergibt

g = (−1) N +1 ( m 22 am 12 b ),

die beide ganzen Zahlen von Bézout Identität sind s  = (-1) N + 1 m 22 und t  = (-1) N m 12 . Die Matrixmethode ist mit zwei Multiplikationen und zwei Additionen pro Schritt des euklidischen Algorithmus genauso effizient wie die äquivalente Rekursion.

Lemma von Euklid und eindeutige Faktorisierung

Die Identität von Bézout ist für viele Anwendungen von Euklids Algorithmus wesentlich, wie zum Beispiel die einzigartige Faktorisierung von Zahlen in Primfaktoren. Um dies zu veranschaulichen, nehmen wir an, dass eine Zahl L als Produkt zweier Faktoren u und v geschrieben werden kann , d. h. L  =  uv . Wenn eine andere Zahl w ebenfalls L teilt, aber zu u teilerfremd ist , dann muss w durch folgendes Argument v teilen : Wenn der größte gemeinsame Teiler von u und w 1 ist, dann können ganze Zahlen s und t so gefunden werden, dass

1 = su + tw  .

von Bézouts Identität. Die Multiplikation beider Seiten mit v ergibt die Beziehung

v = suv + twv = sL + twv  .

Da w beide Terme auf der rechten Seite teilt, muss es auch die linke Seite v teilen . Dieses Ergebnis ist als Lemma von Euklid bekannt . Insbesondere wenn eine Primzahl L teilt , muss sie mindestens einen Faktor von L teilen . Umgekehrt, wenn eine Zahl w zu jeder einer Reihe von Zahlen a 1 , a 2 , ..., a n teilerfremd ist , dann ist w auch zu ihrem Produkt a 1  ×  a 2  × ... ×  a n teilerfremd .

Das Lemma von Euklid reicht aus, um zu beweisen, dass jede Zahl eine eindeutige Zerlegung in Primzahlen hat. Um dies zu sehen, nehmen wir das Gegenteil an, dass es zwei unabhängige Faktorisierungen von L in m bzw. n Primfaktoren gibt

L = p 1 p 2p m = q 1 q 2q n  .

Da jede Primzahl p L durch Annahme teilt , muss sie auch einen der q Faktoren teilen ; da jedes q auch eine Primzahl ist, muss p  =  q sein . Die iterative Division durch die p- Faktoren zeigt, dass jedes p ein gleiches Gegenstück q hat ; die beiden Primfaktorzerlegungen sind bis auf ihre Reihenfolge identisch. Die einzigartige Faktorisierung von Zahlen in Primzahlen hat viele Anwendungen in mathematischen Beweisen, wie unten gezeigt.

Lineare diophantische Gleichungen

"Eine diagonale Linie, die von der oberen linken Ecke nach unten rechts verläuft. Fünfzehn Kreise sind in regelmäßigen Abständen entlang der Linie angeordnet. Senkrechte xy-Koordinatenachsen haben ihren Ursprung in der unteren linken Ecke; die Linie kreuzte die y-Achse oben links und kreuze die x-Achse unten rechts."
Plot einer linearen diophantischen Gleichung , 9 x  + 12 y  = 483. Die Lösungen sind als blaue Kreise dargestellt.

Diophantine Gleichungen sind Gleichungen, bei denen die Lösungen auf ganze Zahlen beschränkt sind; sie sind nach dem alexandrinischen Mathematiker Diophantus aus dem 3. Jahrhundert benannt . Eine typische lineare diophantische Gleichung sucht ganze Zahlen x und y, so dass

ax + by = c

wobei a , b und c ganze Zahlen sind. Dies kann als Gleichung für x in modularer Arithmetik geschrieben werden :

axc mod b .

Sei g der größte gemeinsame Teiler von a und b . Beide Terme in ax  +  by sind durch g teilbar ; daher muss c auch durch g teilbar sein , oder die Gleichung hat keine Lösungen. Durch Teilen beider Seiten durch c / g kann die Gleichung auf die Identität von Bezout reduziert werden

sa + tb = g

wobei s und t durch den erweiterten euklidischen Algorithmus gefunden werden können . Dies liefert eine Lösung der diophantischen Gleichung, x 1  =  s ( c / g ) und y 1  =  t ( c / g ).

Im Allgemeinen hat eine lineare diophantische Gleichung keine oder unendlich viele Lösungen. Um letzteres zu finden, betrachten Sie zwei Lösungen, ( x 1y 1 ) und ( x 2y 2 ), wobei

ax 1 + um 1 = c = ax 2 + um 2

oder gleichwertig

a ( x 1x 2 ) = b ( y 2y 1 ).

Daher ist die kleinste Differenz zwischen zwei x- Lösungen b / g , während die kleinste Differenz zwischen zwei y- Lösungen a / g ist . Somit können die Lösungen ausgedrückt werden als

x = x 1bu / g
y = y 1 + au / g .

Indem man u über alle möglichen ganzen Zahlen variieren lässt, kann eine unendliche Familie von Lösungen aus einer einzigen Lösung ( x 1y 1 ) erzeugt werden. Wenn die Lösungen positive ganze Zahlen sein müssen ( x  > 0,  y  > 0), kann nur eine endliche Anzahl von Lösungen möglich sein. Diese Einschränkung der akzeptablen Lösungen ermöglicht es einigen Systemen diophantischer Gleichungen mit mehr Unbekannten als Gleichungen, eine endliche Anzahl von Lösungen zu haben; dies ist für ein lineares Gleichungssystem unmöglich, wenn die Lösungen eine beliebige reelle Zahl sein können (siehe Unterbestimmtes System ).

Multiplikative Inverse und der RSA-Algorithmus

Ein endlicher Körper ist eine Menge von Zahlen mit vier verallgemeinerten Operationen. Die Operationen heißen Addition, Subtraktion, Multiplikation und Division und haben ihre üblichen Eigenschaften, wie Kommutativität , Assoziativität und Distributivität . Ein Beispiel für einen endlichen Körper ist die Menge von 13 Zahlen {0, 1, 2, ..., 12} mit modularer Arithmetik . In diesem Feld werden die Ergebnisse jeder mathematischen Operation (Addition, Subtraktion, Multiplikation oder Division) modulo 13 reduziert ; das heißt, Vielfache von 13 werden addiert oder subtrahiert, bis das Ergebnis im Bereich von 0–12 liegt. Zum Beispiel das Ergebnis von 5 × 7 = 35 mod 13 = 9. Solche endlichen Körper können für jede beliebige Primzahl p definiert werden ; mit anspruchsvollere Definitionen, können sie auch für jede Leistung definiert werden m einer Primzahl p m . Finiten Felder werden oft auch als Galois - Felder, und werden als GF (abgekürzt p ) oder GF ( p m ).   

In einem solchen Feld mit m Zahlen, jeder Nicht - Null - Element a hat eine einzigartige modulare multiplikativen Inversen , a -1 , so dass aa -1  =  eine -1 eine  ≡ 1 mod  m . Diese Umkehrung kann durch Lösen der Kongruenzgleichung ax  ≡ 1 mod  m oder der äquivalenten linearen diophantischen Gleichung

Axt + mein = 1.

Diese Gleichung kann durch den Euklidischen Algorithmus, wie oben beschrieben, gelöst werden . Das Auffinden multiplikativer Inversen ist ein wesentlicher Schritt im RSA-Algorithmus , der im elektronischen Handel weit verbreitet ist ; insbesondere bestimmt die Gleichung die ganze Zahl, die zum Entschlüsseln der Nachricht verwendet wird. Obwohl der RSA-Algorithmus Ringe anstelle von Feldern verwendet, kann der euklidische Algorithmus immer noch verwendet werden, um eine multiplikative Inverse zu finden, wo eine existiert. Der euklidische Algorithmus hat auch andere Anwendungen in fehlerkorrigierenden Codes ; er kann beispielsweise als Alternative zum Berlekamp-Massey-Algorithmus zur Dekodierung von BCH- und Reed-Solomon-Codes verwendet werden , die auf Galois-Feldern basieren.

Chinesischer Restsatz

Der Algorithmus von Euklid kann auch verwendet werden, um mehrere lineare diophantische Gleichungen zu lösen. Solche Gleichungen entstehen im chinesischen Restsatz , der eine neuartige Methode zur Darstellung einer ganzen Zahl x beschreibt . Anstatt eine ganze Zahl durch ihre Ziffern darzustellen, kann sie durch ihre Reste x i modulo einer Menge von N teilerfremden Zahlen m i dargestellt werden :

Ziel ist es, x aus seinen N Resten x i zu bestimmen . Die Lösung besteht darin, die mehreren Gleichungen zu einer einzigen linearen diophantischen Gleichung mit einem viel größeren Modul M , das das Produkt aller einzelnen Moduli m i ist, zu kombinieren und M i als . zu definieren

Somit ist jedes M i das Produkt aller Moduli außer m i . Die Lösung hängt davon ab, N neue Zahlen h i zu finden, so dass

Mit diesen Zahlen h i lässt sich jede ganze Zahl x aus ihren Resten x i durch die Gleichung rekonstruieren

Da diese Zahlen h i die multiplikativen Inversen von M i sind , können sie unter Verwendung des Euklid-Algorithmus gefunden werden, wie im vorherigen Unterabschnitt beschrieben.

Stern-Brocot-Baum

Der euklidische Algorithmus kann verwendet werden, um die Menge aller positiven rationalen Zahlen in einem unendlichen binären Suchbaum anzuordnen , der als Stern-Brocot-Baum bezeichnet wird . Die Zahl 1 (ausgedrückt als Bruch 1/1) wird an der Wurzel des Baums platziert, und die Position jeder anderen Zahl a / b kann durch Berechnung von gcd( a , b ) unter Verwendung der ursprünglichen Form des euklidischen Algorithmus ermittelt werden , bei dem jeder Schritt die größere der beiden gegebenen Zahlen durch ihre Differenz mit der kleineren Zahl (nicht ihren Rest) ersetzt und stoppt, wenn zwei gleiche Zahlen erreicht sind. Ein Schritt des euklidischen Algorithmus, der die erste der beiden Zahlen ersetzt, entspricht einem Schritt im Baum von einem Knoten zu seinem rechten Kind, und ein Schritt, der die zweite der beiden Zahlen ersetzt, entspricht einem Schritt im Baum von einem Knoten zu seinem linken Kind. Die so konstruierte Schrittfolge hängt nicht davon ab, ob a / b in niedrigsten Zahlen angegeben ist, und bildet einen Pfad von der Wurzel zu einem Knoten, der die Zahl a / b enthält . Mit dieser Tatsache kann man beweisen, dass jede positive rationale Zahl genau einmal in diesem Baum vorkommt.

3/4 kann zum Beispiel gefunden werden, indem man bei der Wurzel beginnt, einmal nach links und dann zweimal nach rechts geht:

Der Stern-Brocot-Baum und die Stern-Brocot-Folgen der Ordnung i für i = 1, 2, 3, 4

Der euklidische Algorithmus hat fast die gleiche Beziehung zu einem anderen binären Baum auf den rationalen Zahlen, der Calkin-Wilf-Baum genannt wird . Der Unterschied besteht darin, dass der Pfad umgekehrt wird: Anstatt einen Pfad von der Wurzel des Baums zu einem Ziel zu erstellen, wird ein Pfad vom Ziel zur Wurzel erzeugt.

Fortsetzungsbrüche

Der euklidische Algorithmus hat eine enge Beziehung zu Kettenbrüchen . Die Gleichungsfolge kann in der Form geschrieben werden

Der letzte Term auf der rechten Seite ist immer gleich dem Kehrwert der linken Seite der nächsten Gleichung. Somit können die ersten beiden Gleichungen kombiniert werden zu

Die dritte Gleichung kann verwendet werden, um den Nennerterm r 1 / r 0 zu ersetzen , was

Das Endverhältnis der Reste r k / r k –1 kann immer mit der nächsten Gleichung in der Reihe bis zur Endgleichung ersetzt werden. Das Ergebnis ist ein Kettenbruch

Im obigen Arbeitsbeispiel wurde gcd(1071, 462) berechnet, und die Quotienten q k waren 2, 3 bzw. 7. Daher kann der Bruch 1071/462 geschrieben werden

wie durch Berechnung bestätigt werden kann.

Faktorisierungsalgorithmen

Einen größten gemeinsamen Teiler der Berechnung ist ein wesentlicher Schritt in mehrer ganzzahligen Faktorisierung Algorithmen wie Pollard der rho - Algorithmus , Shor-Algorithmus , Dixons Faktorisierungsmethode und die Lenstra elliptische Kurve Faktorisierung . Der euklidische Algorithmus kann verwendet werden, um diese GCD effizient zu finden. Die Faktorisierung von fortgesetzten Brüchen verwendet Kettenbrüche, die unter Verwendung des Euklid-Algorithmus bestimmt werden.

Algorithmische Effizienz

"Ein Satz farbiger Linien, die vom Ursprung eines xy-Koordinatensystems nach außen strahlen. Jede Linie entspricht einem Satz von Zahlenpaaren, die die gleiche Anzahl von Schritten im euklidischen Algorithmus erfordern."
Anzahl der Schritte im euklidischen Algorithmus für gcd( x , y ). Hellere (rote und gelbe) Punkte zeigen relativ wenige Schritte an, während dunklere (violett und blau) Punkte mehr Schritte anzeigen. Der größte dunkle Bereich folgt der Linie y = Φx , wobei Φ der Goldene Schnitt ist .

Die Recheneffizienz des Euklid-Algorithmus wurde gründlich untersucht. Diese Effizienz kann durch die Anzahl der Divisionsschritte beschrieben werden, die der Algorithmus benötigt, multipliziert mit dem Rechenaufwand jedes Schrittes. Die erste bekannte Analyse von Euklids Algorithmus stammt von AAL Reynaud im Jahr 1811, der zeigte, dass die Anzahl der Divisionsschritte bei der Eingabe ( u , v ) durch v begrenzt ist ; später verbesserte er dies auf v /2 + 2. Später, im Jahr 1841, zeigte PJE Finck , dass die Anzahl der Divisionsschritte höchstens 2 log 2  v  + 1 beträgt , und daher läuft Euklids Algorithmus in der Größe der Eingabe zeitpolynomial. Émile Léger untersuchte 1837 den schlimmsten Fall, wenn die Eingaben aufeinanderfolgende Fibonacci-Zahlen sind . Fincks Analyse wurde 1844 von Gabriel Lamé verfeinert , der zeigte, dass die Anzahl der Schritte, die für die Vervollständigung erforderlich sind, nie mehr als das Fünffache der Anzahl h der Basis-10-Ziffern der kleineren Zahl b beträgt  .

Im Modell mit einheitlichen Kosten (geeignet für die Analyse der Komplexität der gcd-Berechnung auf Zahlen, die in ein einzelnes Maschinenwort passen) benötigt jeder Schritt des Algorithmus eine konstante Zeit , und die Analyse von Lamé impliziert, dass die Gesamtlaufzeit ebenfalls O ( h ) ist. In einem Berechnungsmodell, das für Berechnungen mit größeren Zahlen geeignet ist, kann jedoch der Berechnungsaufwand einer einzelnen Restberechnung im Algorithmus bis zu 0 ( h 2 ) betragen . In diesem Fall kann die Gesamtzeit für alle Schritte des Algorithmus mit einer Teleskopserie analysiert werden , die zeigt, dass sie auch O ( h 2 ) ist. Moderne algorithmische Techniken basierend auf dem Schönhage-Strassen-Algorithmus für die schnelle ganzzahlige Multiplikation können verwendet werden, um dies zu beschleunigen, was zu quasilinearen Algorithmen für die GCD führt.

Anzahl der Schritte

Die Anzahl der Schritte zum Berechnen der GCD von zwei natürlichen Zahlen a und b kann mit T ( ab ) bezeichnet werden. Wenn g die GCD von a und b ist , dann gilt a  =  mg und b  =  ng für zwei Teilprimzahlen m und n . Dann

T ( a , b ) = T ( m , n )

wie man sehen kann, indem man alle Schritte im euklidischen Algorithmus durch g dividiert . Nach demselben Argument bleibt die Anzahl der Schritte gleich, wenn a und b mit einem gemeinsamen Faktor w multipliziert werden : T ( a , b ) = T ( wa , wb ). Daher kann die Anzahl der Schritte T zwischen benachbarten Zahlenpaaren, wie beispielsweise T( a , b ) und T( ab  +1), in Abhängigkeit von der Größe der beiden GCDs dramatisch variieren.

Die rekursive Natur des euklidischen Algorithmus ergibt eine weitere Gleichung

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

wobei T ( x , 0) = 0 nach Annahme ist.

Schlimmsten Fall

Wenn der euklidische Algorithmus N Schritte für ein Paar natürlicher Zahlen a  >  b  > 0 erfordert , sind die kleinsten Werte von a und b, für die dies gilt, die Fibonacci-Zahlen F N +2 bzw. F N +1 . Wenn der euklidische Algorithmus erfordert genauer gesagt, N Paar der Schritte zum a  >  b , dann hat man ein  ≥  F N + 2 und b  ≥  F N +1 . Dies kann durch Induktion gezeigt werden . Wenn N  = 1, teilt b a ohne Rest; die kleinsten natürlichen Zahlen, für die dies gilt, sind b  = 1 und a  = 2, also F 2 bzw. F 3 . Nehmen Sie nun an, dass das Ergebnis für alle Werte von N bis M  − 1 gilt. Der erste Schritt des M -Schritt-Algorithmus ist a  =  q 0 b  +  r 0 , und der euklidische Algorithmus erfordert M  − 1 Schritte für das Paar b  >  r 0 . Durch Induktionsvoraussetzung hat man b  ≥  F M + 1 und r 0  ≥  F M . Daher a  =  q 0 b  +  r 0  ≥  b  +  r 0  ≥  F M + 1  +  F M  =  F M + 2 , der die gewünschte Ungleichung ist. Dieser 1844 von Gabriel Lamé veröffentlichte Beweis stellt den Beginn der Computational Complexity Theory und auch die erste praktische Anwendung der Fibonacci-Zahlen dar.

Dieses Ergebnis reicht aus, um zu zeigen, dass die Anzahl der Schritte in Euklids Algorithmus niemals mehr als das Fünffache der Anzahl seiner Stellen (Basis 10) betragen kann. Denn wenn der Algorithmus N Schritte erfordert , dann ist b größer oder gleich F N +1, was wiederum größer oder gleich φ N −1 ist , wobei φ der Goldene Schnitt ist . Da b  ≥  φ N −1 ist , ist N  − 1 ≤ log φ b . Da log 10 φ  > 1/5 ist ( N  − 1)/5 < log 10 φ  log φ b  = log 10 b . Somit ist N  ≤ 5 log 10 b . Somit benötigt der euklidische Algorithmus immer weniger als O ( h ) Divisionen, wobei h die Anzahl der Stellen in der kleineren Zahl b ist .

Durchschnitt

Die durchschnittliche Schrittzahl des euklidischen Algorithmus wurde auf drei verschiedene Arten definiert. Die erste Definition ist die durchschnittliche Zeit T ( a ), die benötigt wird, um die GCD einer gegebenen Zahl a und einer kleineren natürlichen Zahl b zu berechnen, die mit gleicher Wahrscheinlichkeit aus den ganzen Zahlen 0 bis a  − 1 . gewählt wird

Da jedoch T ( ab ) mit der GCD der beiden Zahlen stark schwankt, ist die gemittelte Funktion T ( a ) ebenfalls "verrauscht".

Um dieses Rauschen zu reduzieren, wird ein zweiter Mittelwert τ ( a ) über alle Zahlen gebildet, die mit a . teilerfremd sind

Es gibt φ ( a ) teilerfremde ganze Zahlen kleiner als a , wobei φ die Eulersche Totient - Funktion ist . Dieser Tau-Durchschnitt wächst glatt mit a

mit der Restfehler der Ordnung ist eine - (1/6) + ε , wobei ε ist unendlich . Die Konstante C ( Porter-Konstante ) in dieser Formel ist gleich

wobei γ die Euler-Mascheroni-Konstante und ζ' die Ableitung der Riemannschen Zetafunktion ist . Der führende Koeffizient (12/π 2 ) ln 2 wurde durch zwei unabhängige Methoden bestimmt.

Da der erste Durchschnitt aus dem tau-Durchschnitt berechnet werden kann, indem man über die Teiler d von  a . summiert

es kann durch die Formel angenähert werden

wobei Λ( d ) die Mangoldt-Funktion ist .

Ein dritter Durchschnitt Y ( n ) ist definiert als die mittlere Anzahl von Schritten, die erforderlich sind, wenn sowohl a als auch b zufällig (mit gleichmäßiger Verteilung) von 1 bis n . gewählt werden

Einsetzen der Näherungsformel für T ( a ) in diese Gleichung ergibt eine Schätzung für Y ( n )

Rechenaufwand pro Schritt

In jedem Schritt k des euklidischen Algorithmus werden der Quotient q k und der Rest r k für ein gegebenes Paar von ganzen Zahlen r k −2 und r k −1 . berechnet

r k –2 = q k r k –1 + r k .

Der Rechenaufwand pro Schritt hängt hauptsächlich mit der Ermittlung von q k zusammen , da der Rest r k schnell aus r k −2 , r k −1 und q k . berechnet werden kann

R k = R k -2 - q k R k -1 .

Der Rechenaufwand des Teilens h -Bit Zahlen Skalen als O ( h ( l + 1)), wobei l die Länge des Quotienten ist.

Zum Vergleich: Euklids ursprünglicher subtraktionsbasierter Algorithmus kann viel langsamer sein. Eine einzelne ganzzahlige Division entspricht dem Quotienten q Anzahl von Subtraktionen. Wenn das Verhältnis von a und b sehr groß ist, ist der Quotient groß und es sind viele Subtraktionen erforderlich. Andererseits hat sich gezeigt, dass die Quotienten sehr wahrscheinlich kleine ganze Zahlen sind. Die Wahrscheinlichkeit eines gegebenen Quotienten q beträgt ungefähr ln| u /( u  − 1)| wobei u  = ( q  + 1) 2 . Zur Veranschaulichung beträgt die Wahrscheinlichkeit eines Quotienten von 1, 2, 3 oder 4 ungefähr 41,5 %, 17,0 %, 9,3 % bzw. 5,9 %. Da die Subtraktionsoperation schneller als die Division ist, insbesondere bei großen Zahlen, ist der subtraktionsbasierte Euklid-Algorithmus mit der Divisions-basierten Version konkurrenzfähig. Dies wird in der binären Version des Euklid-Algorithmus ausgenutzt .

Die Kombination der geschätzten Anzahl von Schritten mit dem geschätzten Rechenaufwand pro Schritt zeigt, dass der Algorithmus von Euklid quadratisch ( h 2 ) mit der durchschnittlichen Anzahl von Stellen h in den ersten beiden Zahlen a und b wächst . Seien h 0 , h 1 , ..., h N –1 die Anzahl der Stellen in den aufeinanderfolgenden Resten r 0r 1 , ...,  r N –1 . Da die Schrittzahl N linear mit h wächst , ist die Laufzeit durch

Alternative Methoden

Der Algorithmus von Euklid ist in der Praxis aufgrund seiner Einfachheit weit verbreitet, insbesondere für kleine Zahlen. Zum Vergleich kann die Effizienz von Alternativen zum Euklid-Algorithmus bestimmt werden.

Ein ineffizienter Ansatz zum Ermitteln der GCD zweier natürlicher Zahlen a und b besteht darin, alle ihre gemeinsamen Teiler zu berechnen; der GCD ist dann der größte gemeinsame Teiler. Die gemeinsamen Teiler können gefunden werden, indem beide Zahlen durch aufeinanderfolgende ganze Zahlen von 2 bis zur kleineren Zahl b geteilt werden . Die Anzahl der Schritte dieses Ansatzes wächst linear mit b oder exponentiell in der Anzahl der Stellen. Ein anderer ineffizienter Ansatz besteht darin, die Primfaktoren einer oder beider Zahlen zu finden. Wie oben erwähnt , entspricht der GCD dem Produkt der Primfaktoren, die sich die beiden Zahlen a und b teilen . Gegenwärtige Methoden zur Primfaktorzerlegung sind ebenfalls ineffizient; viele moderne Kryptographiesysteme verlassen sich sogar auf diese Ineffizienz.

Der binäre GCD-Algorithmus ist eine effiziente Alternative, die die Division durch schnellere Operationen ersetzt, indem er die von Computern verwendete binäre Darstellung nutzt. Allerdings skaliert diese Alternative auch wie O ( h ²) . Er ist im Allgemeinen schneller als der euklidische Algorithmus auf echten Computern, obwohl er auf die gleiche Weise skaliert. Zusätzliche Effizienz lässt sich erzielen, indem nur die führenden Ziffern der beiden Zahlen a und b untersucht werden . Der binäre Algorithmus kann auf andere Basen ( k- äre Algorithmen) mit bis zu fünffacher Geschwindigkeitssteigerung erweitert werden. Lehmers GCD-Algorithmus verwendet das gleiche allgemeine Prinzip wie der binäre Algorithmus, um GCD-Berechnungen in beliebigen Basen zu beschleunigen.

Ein rekursiver Ansatz für sehr große ganze Zahlen (mit mehr als 25.000 Stellen) führt zu quasilinearen ganzzahligen GCD-Algorithmen, wie denen von Schönhage und Stehlé und Zimmermann. Diese Algorithmen nutzen die 2×2-Matrixform des oben angegebenen euklidischen Algorithmus . Diese quasilinearen Verfahren skalieren im Allgemeinen als O ( h (log h ) 2 (log log h )).

Verallgemeinerungen

Obwohl der euklidische Algorithmus verwendet wird, um den größten gemeinsamen Teiler zweier natürlicher Zahlen (positive ganze Zahlen) zu finden, kann er auf die reellen Zahlen und auf andere mathematische Objekte wie Polynome , quadratische ganze Zahlen und Hurwitz-Quaternionen verallgemeinert werden . In letzteren Fällen wird der euklidische Algorithmus verwendet, um die entscheidende Eigenschaft der eindeutigen Faktorisierung zu demonstrieren, dh dass solche Zahlen eindeutig in irreduzible Elemente zerlegt werden können , die Gegenstücke zu Primzahlen. Eine eindeutige Faktorisierung ist für viele Beweise der Zahlentheorie unerlässlich.

Rationale und reelle Zahlen

Euklids Algorithmus kann auf reelle Zahlen angewendet werden , wie von Euklid in Buch 10 seiner Elemente beschrieben . Das Ziel des Algorithmus ist eine reelle Zahl zu identifizieren , g , so daß zwei gegebene reelle Zahlen sind , a und b , sind ganzzahlige Vielfache davon: a = mg und b = ng , wobei m und n sind ganze Zahlen . Diese Identifizierung ist äquivalent zum Finden einer ganzzahligen Beziehung zwischen den reellen Zahlen a und b ; das heißt, es bestimmt ganze Zahlen s und t, so dass sa + tb = 0 ist . Euklid verwendet diesen Algorithmus, um die Frage nach inkommensurablen Längen zu behandeln .

Der euklidische Algorithmus mit reellen Zahlen unterscheidet sich von seinem ganzzahligen Gegenstück in zweierlei Hinsicht. Erstens sind die Reste r k reelle Zahlen, obwohl die Quotienten q k nach wie vor ganze Zahlen sind. Zweitens ist nicht garantiert, dass der Algorithmus in einer endlichen Anzahl N von Schritten endet . Wenn ja, ist der Bruch a / b eine rationale Zahl, also das Verhältnis zweier ganzer Zahlen

und kann als endlicher Kettenbruch [ q 0 ; q 1 , q 2 , ..., q N ] . Wenn der Algorithmus nicht aufhört, ist der Bruch a / b eine irrationale Zahl und kann durch einen unendlichen Kettenbruch [ q 0 ; q 1 , q 2 , …] . Beispiele für unendliche Kettenbrüche sind der Goldene Schnitt φ = [1; 1, 1, ...] und die Quadratwurzel von zwei , 2 = [1; 2, 2, ...] . Es ist unwahrscheinlich, dass der Algorithmus aufhört, da fast alle Verhältnisse a / b zweier reeller Zahlen irrational sind.

Ein unendlicher Kettenbruch kann in einem Schritt k [ q 0 ; q 1 , q 2 , ..., q k ] , um eine Annäherung an a / b zu erhalten , die sich verbessert, wenn k erhöht wird. Die Approximation wird durch Konvergenten m k / n k beschrieben ; Zähler und Nenner sind teilerfremd und gehorchen der Rekursionsrelation

wobei m −1 = n −2 = 1 und m −2 = n −1 = 0 die Anfangswerte der Rekursion sind. Die Konvergenz m k / n k ist die beste rationale Zahlenapproximation an a / b mit Nenner n k :

Polynome

Polynome in einer einzelnen Variablen x können addiert, multipliziert und in irreduzible Polynome zerlegt werden , die die Analoga der Primzahlen für ganze Zahlen sind. Das größte gemeinsame Teilerpolynom g ( x ) zweier Polynome a ( x ) und b ( x ) ist definiert als das Produkt ihrer gemeinsamen irreduziblen Polynome, die mit dem euklidischen Algorithmus identifiziert werden können. Das grundlegende Verfahren ist ähnlich dem für ganze Zahlen. Bei jedem Schritt k wird ein Quotient - Polynom q k ( x ) und ein Rest - Polynom r k ( x ) identifiziert , die rekursive Gleichung zu erfüllen

wobei r –2 ( x ) = a ( x ) und r –1 ( x ) = b ( x ) ist . Jeder Quotientenpolynom ist so gewählt, dass jeder Rest entweder Null ist oder einen Grad, der kleiner ist als der Grad des Vorgängers ist: Grad [ r k ( x )] <deg [ r k -1 ( x )] . Da der Grad eine nicht negative ganze Zahl ist und mit jedem Schritt abnimmt, schließt der euklidische Algorithmus auf eine endliche Anzahl von Schritten. Der letzte von Null verschiedene Rest ist der größte gemeinsame Teiler der ursprünglichen zwei Polynome, a ( x ) und b ( x ) .

Betrachten Sie zum Beispiel die folgenden zwei quartischen Polynome, die jeweils in zwei quadratische Polynome zerlegt werden

Dividieren von a ( x ) durch b ( x ) ergibt einen Rest r 0 ( x ) = x 3 + (2/3) x 2 + (5/3) x − (2/3) . Im nächsten Schritt, b ( x ) wird durch unterteilt r 0 ( x ) , wodurch man einen Rest R 1 ( x ) = x 2 + x + 2 . Schließlich ergibt die Division von r 0 ( x ) durch r 1 ( x ) einen Rest von Null, was anzeigt, dass r 1 ( x ) das größte gemeinsame Teilerpolynom von a ( x ) und b ( x ) ist , konsistent mit ihrer Faktorisierung.

Viele der oben beschriebenen Anwendungen für ganze Zahlen übertragen sich auf Polynome. Der euklidische Algorithmus kann verwendet werden, um lineare diophantische Gleichungen und chinesische Restprobleme für Polynome zu lösen; Kettenbrüche von Polynomen können auch definiert werden.

Der polynomiale euklidische Algorithmus hat andere Anwendungen, wie Sturmketten , eine Methode zum Zählen der Nullstellen eines Polynoms , die innerhalb eines gegebenen reellen Intervalls liegen . Dies wiederum hat Anwendungen in mehreren Bereichen, wie dem Routh-Hurwitz-Stabilitätskriterium in der Kontrolltheorie .

Schließlich müssen die Koeffizienten der Polynome nicht aus ganzen Zahlen, reellen Zahlen oder gar komplexen Zahlen gezogen werden. Zum Beispiel können die Koeffizienten aus einem allgemeinen Körper gezogen werden, wie beispielsweise den oben beschriebenen endlichen Körpern GF( p ) . Die entsprechenden Schlussfolgerungen über den euklidischen Algorithmus und seine Anwendungen gelten auch für solche Polynome.

Gaußsche ganze Zahlen

"Eine Reihe von Punkten, die innerhalb eines Kreises liegen. Das Punktmuster hat eine vierfache Symmetrie, dh Drehungen um 90 Grad lassen das Muster unverändert. Das Muster kann auch an vier Linien gespiegelt werden, die durch den Mittelpunkt des Kreises gehen: die vertikale und die horizontale Achsen und die beiden diagonalen Linien bei ±45 Grad."
Verteilung der Gaußschen Primzahlen u + vi in der komplexen Ebene, mit Normen u 2 + v 2 kleiner als 500

Die Gaußschen ganzen Zahlen sind komplexe Zahlen der Form α = u + vi , wobei u und v gewöhnliche ganze Zahlen sind und i die Quadratwurzel der negativen Eins ist . Durch die Definition eines Analogons des euklidischen Algorithmus kann gezeigt werden, dass Gaußsche ganze Zahlen durch das obige Argument eindeutig faktorisierbar sind . Diese einzigartige Faktorisierung ist in vielen Anwendungen hilfreich, z. B. beim Ableiten aller pythagoräischen Tripel oder beim Beweis des Satzes von Fermat über Summen von zwei Quadraten . Im Allgemeinen ist der euklidische Algorithmus in solchen Anwendungen praktisch, aber nicht unbedingt erforderlich; zum Beispiel können die Theoreme oft durch andere Argumente bewiesen werden.

Der für zwei Gaußsche ganze Zahlen α und β entwickelte euklidische Algorithmus ist fast der gleiche wie der für gewöhnliche ganze Zahlen, unterscheidet sich jedoch in zweierlei Hinsicht. Wie zuvor besteht die Aufgabe bei jedem Schritt k darin, einen Quotienten q k und einen Rest r k zu identifizieren, so dass

wobei r k −2 = α , wobei r k −1 = β , und wobei jeder Rest strikt kleiner ist als sein Vorgänger: | r k | < | r k −1 | . Der erste Unterschied besteht darin, dass die Quotienten und Reste selbst Gaußsche ganze Zahlen und somit komplexe Zahlen sind . Die Quotienten q k werden im Allgemeinen durch Runden der reellen und komplexen Teile des exakten Verhältnisses (wie der komplexen Zahl α / β ) auf die nächsten ganzen Zahlen gefunden. Der zweite Unterschied liegt in der Notwendigkeit zu definieren, wie ein komplexer Rest "kleiner" als ein anderer sein kann. Dazu wird eine Normfunktion f ( u + vi ) = u 2 + v 2 definiert, die jede Gaußsche ganze Zahl u + vi in eine gewöhnliche ganze Zahl umwandelt . Nach jedem Schritt k des euklidischen Algorithmus ist die Norm des Rests f ( r k ) kleiner als die Norm des vorhergehenden Rests f ( r k −1 ) . Da die Norm eine nichtnegative ganze Zahl ist und mit jedem Schritt abnimmt, endet der euklidische Algorithmus für Gaußsche ganze Zahlen in endlich vielen Schritten. Der letzte von Null verschiedene Rest ist gcd( α , β ) , die Gaußsche ganze Zahl der größten Norm, die sowohl α als auch β teilt ; sie ist bis zur Multiplikation mit einer Einheit, ±1 oder ± i eindeutig .

Viele der anderen Anwendungen des euklidischen Algorithmus übertragen sich auf Gaußsche ganze Zahlen. Es kann beispielsweise verwendet werden, um lineare diophantische Gleichungen und chinesische Restprobleme für Gaußsche ganze Zahlen zu lösen; Kettenbrüche von Gaußschen ganzen Zahlen können auch definiert werden.

Euklidische Domänen

Eine Menge von Elementen unter zwei binären Operationen , die als Addition und Multiplikation bezeichnet werden, heißt euklidischer Bereich, wenn sie einen kommutativen Ring R bildet und grob gesagt, wenn auf ihnen ein verallgemeinerter euklidischer Algorithmus durchgeführt werden kann. Die beiden Operationen eines solchen Rings müssen nicht die Addition und Multiplikation der gewöhnlichen Arithmetik sein; Vielmehr können sie allgemeiner sein, wie die Operationen einer mathematischen Gruppe oder eines Monoids . Dennoch sollten diese allgemeinen Operationen viele der Gesetze respektieren, die die gewöhnliche Arithmetik regeln, wie z. B. Kommutativität , Assoziativität und Distributivität .

Der verallgemeinerte euklidische Algorithmus erfordert eine euklidische Funktion , dh eine Zuordnung f von R in den Satz von nicht - negativen ganzen Zahlen , so dass für zwei beliebigen von Null verschiedenen Elemente a und b in R existieren q und r in R , so dass ein = QB + r und f ( r ) < f ( b ) . Beispiele für solche Abbildungen sind der Absolutwert für ganze Zahlen, der Grad für univariate Polynome und die Norm für Gaußsche ganze Zahlen oben . Das Grundprinzip besteht darin , dass jeder Schritt des Algorithmus reduziert f unerbittlich; Wenn f nur endlich oft reduziert werden kann, muss der Algorithmus also in endlich vielen Schritten anhalten. Dieses Prinzip beruht auf der Wohlordnungseigenschaft der nicht-negativen ganzen Zahlen, die behauptet, dass jede nichtleere Menge von nicht-negativen ganzen Zahlen ein kleinstes Mitglied hat.

Der fundamentale Satz der Arithmetik gilt für jedes euklidische Gebiet: Jede Zahl aus einem euklidischen Gebiet kann eindeutig in irreduzible Elemente zerlegt werden . Jede euklidische Domäne ist eine eindeutige Faktorisierungsdomäne (UFD), obwohl das Umgekehrte nicht gilt. Die euklidischen Domänen und die UFDs sind Unterklassen der GCD-Domänen , Domänen, in denen immer ein größter gemeinsamer Teiler von zwei Zahlen existiert. Mit anderen Worten, es kann einen größten gemeinsamen Teiler geben (für alle Paare von Elementen in einer Domäne), obwohl es möglicherweise nicht möglich ist, ihn mit einem euklidischen Algorithmus zu finden. Ein euklidischer Bereich ist immer ein Hauptidealbereich (PID), ein Integralbereich, in dem jedes Ideal ein Hauptideal ist . Auch hier gilt nicht das Umgekehrte: Nicht jede PID ist eine euklidische Domäne.

Die einzigartige Faktorisierung von euklidischen Domänen ist in vielen Anwendungen nützlich. Zum Beispiel ist die eindeutige Faktorisierung der Gaußschen ganzen Zahlen praktisch, um Formeln für alle pythagoräischen Tripel abzuleiten und den Satz von Fermat über Summen von zwei Quadraten zu beweisen . Die einzigartige Faktorisierung war auch ein Schlüsselelement in einem versuchten Beweis von Fermats letztem Satz, der 1847 von Gabriel Lamé veröffentlicht wurde, dem gleichen Mathematiker, der die Effizienz von Euklids Algorithmus basierend auf einem Vorschlag von Joseph Liouville analysierte . Lamé Ansatz erforderlich , um die einzigartige Faktorisierung von Zahlen der Form x + & omega; y , wobei x und y ganze Zahlen sind, und ω = e 2 / n ist eine n - te Wurzel von 1, das heißt, ω n = 1 . Obwohl dieser Ansatz für einige Werte von n erfolgreich ist (wie n = 3 , die Eisenstein-Ganzzahlen ), faktorisieren solche Zahlen im Allgemeinen nicht eindeutig. Dieses Versagen der eindeutigen Faktorisierung in einigen zyklotomischen Feldern führte Ernst Kummer zum Konzept der idealen Zahlen und später Richard Dedekind zu Idealen .

Eindeutige Faktorisierung von quadratischen ganzen Zahlen

"Eine Reihe von Punkten, die innerhalb eines Kreises liegen. Das Punktmuster hat eine sechsfache Symmetrie, dh Drehungen um 60 Grad lassen das Muster unverändert. Das Muster kann auch um sechs Linien gespiegelt werden, die durch den Mittelpunkt des Kreises gehen: die vertikale und die horizontale Achsen und die vier diagonalen Linien bei ±30 und ±60 Grad."
Verteilung der Eisenstein-Primzahlen u + in der komplexen Ebene, mit Normen kleiner als 500. Die Zahl ω ist eine Kubikwurzel von 1 .

Die quadratischen Ganzzahlringe sind hilfreich, um euklidische Bereiche zu veranschaulichen. Quadratische ganze Zahlen sind Verallgemeinerungen der Gaußschen ganzen Zahlen, bei denen die imaginäre Einheit i durch eine Zahl ω ersetzt wird . Somit haben sie die Form u + , wobei u und v ganze Zahlen sind und ω abhängig von einem Parameter D eine von zwei Formen hat . Wenn D nicht gleich einem Vielfachen von vier plus eins ist, dann

Wenn D jedoch ein Vielfaches von vier plus eins ist, dann

Wenn die Funktion f einer Normfunktion entspricht, wie sie zum Ordnen der Gaußschen ganzen Zahlen oben verwendet wurde , dann ist der Bereich als normeuklidisch bekannt . Die normeuklidischen Ringe von quadratischen ganzen Zahlen sind genau diejenigen, bei denen D einer der Werte −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19 . ist , 21, 29, 33, 37, 41, 57 oder 73. Die Fälle D = −1 und D = −3 ergeben die Gauß-Zahlen bzw. Eisenstein-Zahlen .

Wenn f eine beliebige euklidische Funktion sein darf, ist die Liste der möglichen Werte von D, für die der Bereich euklidisch ist, noch nicht bekannt. Das erste Beispiel für einen nicht normeuklidischen euklidischen Bereich (mit D = 69 ) wurde 1994 veröffentlicht. 1973 bewies Weinberger, dass ein quadratischer ganzzahliger Ring mit D > 0 genau dann euklidisch ist, wenn er ein Prinzipal ist idealer Bereich , vorausgesetzt, die verallgemeinerte Riemann-Hypothese gilt.

Nichtkommutative Ringe

Der euklidische Algorithmus kann auf einige nichtkommutative Ringe wie die Menge der Hurwitz-Quaternionen angewendet werden . Seien α und β zwei Elemente eines solchen Rings. Sie haben einen gemeinsamen rechten Teiler δ, wenn α = ξδ und β = ηδ für eine beliebige Wahl von ξ und η im Ring. In ähnlicher Weise haben sie einen gemeinsamen linken Teiler, wenn α = und β = für eine beliebige Wahl von ξ und η im Ring. Da die Multiplikation nicht kommutativ ist, gibt es zwei Versionen des euklidischen Algorithmus, eine für rechte Teiler und eine für linke Teiler. Durch die Wahl der richtigen Teiler kann der erste Schritt zur Bestimmung der gcd( α , β ) durch den euklidischen Algorithmus geschrieben werden

wobei ψ 0 den Quotienten und ρ 0 den Rest darstellt. Diese Gleichung zeigt, dass jeder gemeinsame rechte Teiler von α und β ebenfalls ein gemeinsamer Teiler des Restes ρ 0 ist . Die analoge Gleichung für die linken Teiler wäre

Bei jeder Wahl wird der Vorgang wie oben wiederholt, bis der größte gemeinsame rechte oder linke Teiler identifiziert ist. Wie im euklidischen Gebiet muss die "Größe" des Restes ρ 0 (formal seine Norm ) strikt kleiner als β sein , und es darf nur endlich viele mögliche Größen für ρ 0 geben , damit der Algorithmus garantiert kündigen.

Die meisten Ergebnisse für die GCD übertragen sich auf nichtkommutative Zahlen. Zum Beispiel besagt die Identität von Bézout , dass das richtige gcd( α , β ) als eine Linearkombination von α und β ausgedrückt werden kann . Mit anderen Worten, es gibt Zahlen σ und τ, so dass

Die analoge Identität für die linke GCD ist fast dieselbe:

Die Identität von Bézout kann verwendet werden, um diophantische Gleichungen zu lösen. Zum Beispiel basiert einer der Standardbeweise von Lagranges Vierquadratsatz, dass jede positive ganze Zahl als Summe von vier Quadraten dargestellt werden kann, auf diese Weise auf Quaternionen-GCDs.

Siehe auch

  • Euklidischer Rhythmus , eine Methode zur Verwendung des Euklidischen Algorithmus zur Erzeugung musikalischer Rhythmen

Anmerkungen

Verweise

Literaturverzeichnis

Externe Links