Größter gemeinsamer Teiler – Wikipedia

before-content-x4

Größte positive ganze Zahl, die zwei oder mehr ganze Zahlen teilt

In der Mathematik ist die größter gemeinsamer Teiler (GCD) von zwei oder mehr ganzen Zahlen, die nicht alle null sind, ist die größte positive ganze Zahl, die jede der ganzen Zahlen teilt. Für zwei ganze Zahlen x, ja, der größte gemeinsame Teiler von x und ja wird bezeichnet

gcd(x,ja){displaystyle gcd(x,y)}

. Der GCD von 8 und 12 ist beispielsweise 4, d. h.

gcd(8,12)=4{displaystyle gcd(8,12)=4}

.[1][2]

Im Namen “größter gemeinsamer Teiler” kann das Adjektiv “größter” durch “höchster” und das Wort “Teiler” durch “Faktor” ersetzt werden, so dass andere Namen enthalten: höchster gemeinsamer Teiler (hcf), etc.[3][4][5][6] Historisch gesehen haben andere Namen für das gleiche Konzept enthalten größte gemeinsame Maßnahme.[7]

Dieser Begriff kann auf Polynome (siehe Polynom größter gemeinsamer Teiler) und andere kommutative Ringe (siehe § In kommutativen Ringen unten) erweitert werden.

Überblick[edit]

Definition[edit]

Die größter gemeinsamer Teiler (GCD) von zwei ganzen Zahlen ungleich null ein und B ist die größte positive ganze Zahl D so dass D ist ein Teiler von beiden ein und B; das heißt, es gibt ganze Zahlen e und F so dass ein = de und B = df, und D ist die größte solche ganze Zahl. Die GCD von ein und B wird allgemein bezeichnet gcd(ein, B).[8]

Diese Definition gilt auch, wenn einer von ein und B ist null. In diesem Fall ist der GCD der absolute Wert der ganzen Zahl ungleich null: gcd(ein, 0) = gcd(0, ein) = |ein|. Dieser Fall ist als Abschlussschritt des euklidischen Algorithmus wichtig.

Die obige Definition kann nicht zum Definieren verwendet werden gcd(0, 0), schon seit 0 × n = 0, und Null hat somit keinen größten Teiler. Null ist jedoch sein eigener größter Teiler, wenn größte wird im Kontext der Teilbarkeitsrelation verstanden, also gcd(0, 0) wird üblicherweise als 0 definiert. Dadurch bleiben die üblichen Identitäten für GCD und insbesondere Bézouts Identität erhalten, nämlich dass gcd(ein, B) erzeugt das gleiche Ideal wie {ein, B}.[9][10][11] Diese Konvention wird von vielen Computeralgebrasystemen befolgt.[12] Trotzdem verlassen einige Autoren gcd(0, 0) nicht definiert.[13]

Die GCD von ein und B ist ihr größter positiver gemeinsamer Teiler in der Vorordnungsrelation der Teilbarkeit. Dies bedeutet, dass die gemeinsamen Teiler von ein und B sind genau die Teiler ihrer GCD. Dies wird gewöhnlich bewiesen, indem man entweder das Lemma von Euklid, den fundamentalen Satz der Arithmetik oder den euklidischen Algorithmus verwendet. Dies ist die Bedeutung von “am größten”, die für die Verallgemeinerungen des Konzepts der GCD verwendet wird.

Beispiel[edit]

Die Zahl 54 kann auf verschiedene Weise als Produkt zweier ganzer Zahlen ausgedrückt werden:

Somit ist die vollständige Liste der Teiler von 54 ist

1,2,3,6,9,18,27,54{displaystyle 1,2,3,6,9,18,27,54}

. Ebenso sind die Teiler von 24

1,2,3,4,6,8,12,24{displaystyle 1,2,3,4,6,8,12,24}

. Die Zahlen, die diese beiden Listen haben gemeinsam sind die gemeinsame Teiler von 54 und 24, d.h.

Von diesen ist der Größte 6, also ist es der größter gemeinsamer Teiler:

Die Berechnung aller Teiler der beiden Zahlen auf diese Weise ist normalerweise nicht effizient, insbesondere bei großen Zahlen mit vielen Teilern. Viel effizientere Methoden werden in § Berechnung beschrieben.

Koprimzahlen[edit]

Zwei Zahlen heißen relativ prim oder teilerfremd, wenn ihr größter gemeinsamer Teiler gleich 1 ist.[14] 9 und 28 sind beispielsweise Coprime.

Eine geometrische Ansicht[edit]

Ein 24-mal-60-Rechteck ist mit zehn 12-mal-12-Quadratkacheln bedeckt, wobei 12 die GCD von 24 und 60 ist ein-von-B Rechteck kann mit quadratischen Kacheln der Seitenlänge belegt werden C nur wenn C ist ein gemeinsamer Teiler von ein und B.

Ein rechteckiger Bereich von 24 x 60 kann beispielsweise in ein Raster unterteilt werden: 1 x 1 Quadrate, 2 x 2 Quadrate, 3 x 3 Quadrate, 4 x 4 Quadrate, 6 x -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 somit in ein Raster von 12 x 12 Quadraten mit zwei Quadraten entlang einer Kante (24/12 = 2) unterteilt werden und fünf Quadrate übereinander (60/12 = 5).

Anwendungen[edit]

Reduzieren von Brüchen[edit]

Der größte gemeinsame Teiler ist nützlich, um Brüche auf die niedrigsten Terme zu reduzieren.[15] Zum Beispiel ist gcd(42, 56) = 14, daher

Kleinstes gemeinsames Vielfaches[edit]

Der größte gemeinsame Teiler kann verwendet werden, um das kleinste gemeinsame Vielfache von zwei Zahlen zu finden, wenn der größte gemeinsame Teiler bekannt ist.

Berechnung[edit]

Primfaktorzerlegungen verwenden[edit]

Die größten gemeinsamen Teiler können berechnet werden, indem die Primfaktorzerlegungen der beiden Zahlen bestimmt und Faktoren verglichen werden. Um beispielsweise gcd(48, 180) zu berechnen, finden wir die Primfaktorzerlegungen 48 = 24 · 31 und 180 = 22 · 32 · 51; der GCD ist dann 2min(4,2) · 3min(1,2) · 5min(0,1) = 22 · 31 · 50 = 12, wie im Venn-Diagramm gezeigt. Die entsprechende LCM ist dann 2max(4,2) · 3max(1,2) · 5max(0,1) = 24 · 32 · 51 = 720.

Kleinstes gemeinsames Vielfaches.svg[16]

In der Praxis ist diese Methode nur für kleine Zahlen durchführbar, da die Berechnung der Primfaktorzerlegung zu lange dauert.

Euklids Algorithmus[edit]

Die von Euklid eingeführte Methode zur Berechnung der größten gemeinsamen Teiler beruht darauf, dass bei zwei positiven ganzen Zahlen ein und B so dass ein > B, die gemeinsamen Teiler von ein und B sind die gleichen wie die gemeinsamen Teiler von einB und B.

Euklids Methode zur Berechnung des größten gemeinsamen Teilers von zwei positiven ganzen Zahlen besteht also darin, die größere Zahl durch die Differenz der Zahlen zu ersetzen und dies zu wiederholen, bis die beiden Zahlen gleich sind: das ist ihr größter gemeinsamer Teiler.

Zum Beispiel um zu berechnen gcd(48,18), geht man wie folgt vor:

So gcd(48, 18) = 6.

Diese Methode kann sehr langsam sein, wenn eine Zahl viel größer ist als die andere. Daher wird im Allgemeinen die folgende Variante bevorzugt.

Euklidischer Algorithmus[edit]

Animation, die eine Anwendung des euklidischen Algorithmus zeigt, um den größten gemeinsamen Teiler von 62 und 36 zu finden, der 2 ist.

Eine effizientere Methode ist die Euklidischer Algorithmus, eine Variante, bei der die Differenz der beiden Zahlen ein und B wird ersetzt durch die Rest der euklidischen Teilung (auch Division mit Rest) von ein von B.

Bezeichne diesen Rest als ein mod B, ersetzt der Algorithmus (ein, B) von (B, ein mod B) wiederholt, bis das Paar (D, 0), wo D ist der größte gemeinsame Teiler.

Um beispielsweise gcd(48,18) zu berechnen, ist die Berechnung wie folgt:

Das gibt wieder gcd(48, 18) = 6.

Lehmers GCD-Algorithmus[edit]

Lehmers Algorithmus basiert auf der Beobachtung, dass sich die Anfangsquotienten des Euklid-Algorithmus nur aus den ersten paar Ziffern bestimmen lassen; Dies ist nützlich für Zahlen, die größer als ein Computerwort sind. Im Wesentlichen extrahiert man Anfangsziffern, die typischerweise ein oder zwei Computerwörter bilden, und führt Euklids Algorithmen auf diese kleineren Zahlen aus, solange sichergestellt ist, dass die Quotienten mit denen übereinstimmen, die mit den ursprünglichen Zahlen erhalten würden. Diese Quotienten werden in einer kleinen 2-mal-2-Transformationsmatrix (d. h. einer Matrix von Ganzzahlen aus einzelnen Wörtern) gesammelt. um sie alle auf einmal zu verwenden, um die ursprünglichen Zahlen zu reduzieren[clarification needed]. Dieser Vorgang wird wiederholt, bis die Zahlen klein genug sind, damit der binäre Algorithmus (siehe unten) effizienter ist.

Dieser Algorithmus verbessert die Geschwindigkeit, da er die Anzahl der Operationen bei sehr großen Zahlen reduziert und für die meisten Operationen Hardwarearithmetik verwenden kann. Tatsächlich sind die meisten Quotienten sehr klein, so dass eine beträchtliche Anzahl von Schritten des euklidischen Algorithmus in einer 2-mal-2-Matrix von Einzelwort-Ganzzahlen gesammelt werden kann. Wenn Lehmers Algorithmus auf einen zu großen Quotienten stößt, muss er auf eine Iteration des euklidischen Algorithmus mit einer euklidischen Division großer Zahlen zurückgreifen.

Binärer GCD-Algorithmus[edit]

Der binäre GCD-Algorithmus verwendet nur Subtraktion und Division durch 2. Die Methode ist wie folgt: Sei ein und B seien die beiden nicht-negativen ganzen Zahlen. Lassen Sie die ganze Zahl D 0 sein. Es gibt fünf Möglichkeiten:

Als gcd(ein, ein) = ein, die gewünschte GCD ist ein × 2D (wie ein und B in den anderen Fällen geändert werden, und D zeichnet auf, wie oft ein und B im nächsten Schritt beide durch 2 geteilt wurden, ist die GCD des Anfangspaares das Produkt von ein und 2D).

Dann ist 2 ein gemeinsamer Teiler. Teile beides ein und B um 2, inkrement D durch 1, um die Anzahl der Male aufzuzeichnen, ist 2 ein gemeinsamer Teiler und fahren Sie fort.

Dann ist 2 kein gemeinsamer Teiler. Teilen ein um 2 und weiter.

Dann ist 2 kein gemeinsamer Teiler. Teilen B um 2 und weiter.

Als gcd(ein,B) = gcd(B,ein), wenn ein < B dann tauschen ein und B. Die Nummer C = einB ist positiv und kleiner als ein. Jede Zahl, die teilt ein und B muss sich auch teilen C also jeder gemeinsame Teiler von ein und B ist auch ein gemeinsamer Teiler von B und C. Ähnlich, ein = B + C und jeder gemeinsame Teiler von B und C ist auch ein gemeinsamer Teiler von ein und B. Also die beiden Paare (ein, B) und (B, C) haben die gleichen gemeinsamen Teiler, und daher gcd(ein,B) = gcd(B,C). Außerdem, wie ein und B sind beide seltsam, C gerade ist, kann der Vorgang mit dem Paar fortgesetzt werden (ein, B) ersetzt durch die kleineren Zahlen (C/2, B) ohne die GCD zu ändern.

Jeder der obigen Schritte reduziert mindestens einen von ein und B während sie nicht negativ bleiben und daher nur endlich oft wiederholt werden können. So führt der Prozess schließlich zu ein = B, der Stoppfall. Dann ist die GCD ein × 2D.

Beispiel: (ein, B, D) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) ; die ursprüngliche GCD ist somit das Produkt 6 von 2D = 21 und ein= B= 3.

Der binäre GCD-Algorithmus ist auf binären Computern besonders einfach zu implementieren. Seine Rechenkomplexität ist

Die Rechenkomplexität wird in der Regel als Länge angegeben n der Eingabe. Hier ist diese Länge

n=Protokollein+ProtokollB,{displaystyle n=log a+log b,}

und die Komplexität ist also

Andere Methoden[edit]

Wenn ein und B sind beide ungleich Null, der größte gemeinsame Teiler von ein und B kann unter Verwendung des kleinsten gemeinsamen Vielfachen (LCM) von berechnet werden ein und B:

aber häufiger wird der LCM aus dem GCD berechnet.

Verwendung der Funktion von Thomae F,

was verallgemeinert zu ein und B rationale Zahlen oder kommensurable reelle Zahlen.

Keith Slavin hat gezeigt, dass für ungerade ein 1:

das ist eine Funktion, die für komplex ausgewertet werden kann B.[17] Das hat Wolfgang Schramm gezeigt

ist eine ganze Funktion in der Variablen B für alle positiven ganzen Zahlen ein wo CD(k) ist die Summe von Ramanujan.[18]

Komplexität[edit]

Die rechnerische Komplexität der Berechnung der größten gemeinsamen Teiler wurde umfassend untersucht.[19] Verwendet man den euklidischen Algorithmus und die elementaren Algorithmen zur Multiplikation und Division, so ist die Berechnung des größten gemeinsamen Teilers zweier ganzer Zahlen von höchstens n Bits ist

Ö(n2).{displaystyle O(n^{2}).}

Dies bedeutet, dass die Berechnung des größten gemeinsamen Teilers bis auf einen konstanten Faktor die gleiche Komplexität wie die Multiplikation hat.

Wenn jedoch ein schneller Multiplikationsalgorithmus verwendet wird, kann man den euklidischen Algorithmus modifizieren, um die Komplexität zu verbessern, aber die Berechnung eines größten gemeinsamen Teilers wird langsamer als die Multiplikation. Genauer gesagt, wenn die Multiplikation zweier ganzer Zahlen von n Bits dauert eine Zeit von T(n), dann hat der schnellste bekannte Algorithmus für den größten gemeinsamen Teiler eine Komplexität

Ö(T(n)Protokolln).{displaystyle Oleft(T(n)log nright).}

Dies impliziert, dass der schnellste bekannte Algorithmus eine Komplexität von hat

Ö(n(Protokolln)2).{displaystyle Oleft(n,(log n)^{2}right).}

Bisherige Komplexitäten gelten für die üblichen Berechnungsmodelle, insbesondere Multitape-Turing-Maschinen und Random-Access-Maschinen.

Die Berechnung der größten gemeinsamen Teiler gehört somit zur Klasse der in quasilinearer Zeit lösbaren Probleme. Vom Stärkeren her, gehört das zugehörige Entscheidungsproblem zur Klasse P der in polynomieller Zeit lösbaren Probleme. Es ist nicht bekannt, dass das GCD-Problem in NC auftritt, und daher gibt es keine bekannte Möglichkeit, es effizient zu parallelisieren; es ist auch nicht bekannt, dass es P-vollständig ist, was bedeuten würde, dass es unwahrscheinlich ist, dass die GCD-Berechnung effizient parallelisiert werden kann. Shallcrosset al. zeigte, dass ein verwandtes Problem (EUGCD, Bestimmung der während des euklidischen Algorithmus auftretenden Restfolge) NC-äquivalent zum Problem der ganzzahligen linearen Programmierung mit zwei Variablen ist; wenn eines der Probleme vorhanden ist NC oder ist P-vollständig, das andere auch.[20] Schon seit NC NL enthält, ist auch für nichtdeterministische Turingmaschinen unbekannt, ob ein platzsparender Algorithmus zur Berechnung der GCD existiert.

Obwohl das Problem nicht bekannt ist NC, es existieren parallele Algorithmen, die asymptotisch schneller als der euklidische Algorithmus sind; der schnellste bekannte deterministische Algorithmus ist von Chor und Goldreich, der (im CRCW-PRAM-Modell) das Problem lösen kann in Ö(n/Protokoll n) Zeit mit n1+ε Prozessoren.[21]Randomisierte Algorithmen können das Problem lösen in Ö((Protokoll n)2) Zeit läuft

exp(Ö(nProtokolln)){displaystyle exp left(Oleft({sqrt {nlog n}}right)right)}

Prozessoren[clarification needed] (das ist superpolynom).[22]

Eigenschaften[edit]

  • Jeder gemeinsame Teiler von ein und B ist ein Teiler von gcd(ein, B).
  • gcd(ein, B), wo ein und B nicht beide Null sind, kann alternativ und äquivalent als kleinste positive ganze Zahl definiert werden D was in der Form geschrieben werden kann D = einP + BQ, wo P und Q sind ganze Zahlen. Dieser Ausdruck wird Bézouts Identität genannt. Zahlen P und Q Dies kann mit dem erweiterten euklidischen Algorithmus berechnet werden.
  • gcd(ein, 0) = |ein|, zum ein 0, da jede Zahl ein Teiler von 0 ist und der größte Teiler von ein ist |ein|.[2][5] Dies wird normalerweise als Basisfall im euklidischen Algorithmus verwendet.
  • Wenn ein teilt das Produkt BC, und gcd(ein, B) = D, dann ein/D teilt C.
  • Wenn m eine nicht negative ganze Zahl ist, dann gcd(mein, mB) = mgcd(ein, B).
  • Wenn m eine ganze Zahl ist, dann gcd(ein + mB, B) = gcd(ein, B).
  • Wenn m ist ein positiver gemeinsamer Teiler von ein und B, dann gcd(ein/m, B/m) = gcd(ein, B)/m.
  • Die GCD ist eine multiplikative Funktion im folgenden Sinne: if ein1 und ein2 relativ prim sind, dann gcd(ein1ein2, B) = gcd(ein1, B)⋅gcd(ein2, B). Wenn wir uns insbesondere daran erinnern, dass GCD eine positive ganzzahlige Funktion ist, erhalten wir, dass gcd(ein, BC) = 1 dann und nur dann, wenn gcd(ein, B) = 1 und gcd(ein, C) = 1.
  • Die GCD ist eine kommutative Funktion: gcd(ein, B) = gcd(B, ein).
  • Die GCD ist eine assoziative Funktion: gcd(ein, gcd(B, C)) = gcd(gcd(ein, B), C). Daher gcd(ein, B, C, …) kann verwendet werden, um die GCD mehrerer Argumente anzugeben.
  • gcd(ein, B) ist eng verwandt mit dem kleinsten gemeinsamen Vielfachen lcm(ein, B): wir haben
    gcd(ein, B)⋅lcm(ein, B) = |einB|.
Diese Formel wird häufig verwendet, um kleinste gemeinsame Vielfache zu berechnen: Man berechnet zuerst die GCD mit dem Algorithmus von Euklid und teilt dann das Produkt der gegebenen Zahlen durch ihre GCD.
  • Die folgenden Versionen von Distributivität gelten:
    gcd(ein, lcm(B, C)) = lcm(gcd(ein, B), gcd(ein, C))
    lcm(ein, gcd(B, C)) = gcd(lcm(ein, B), lcm(ein, C)).
  • Wenn wir die eindeutigen Primfaktorzerlegungen von ein = P1e1P2e2 ⋅⋅⋅ Pmem und B = P1F1P2F2 ⋅⋅⋅ PmFm wo eich 0 und Fich 0, dann die GCD von ein und B ist
    gcd(ein,B) = P1Mindest(e1,F1)P2Mindest(e2,F2) ⋅⋅⋅ PmMindest(em,Fm).
  • Manchmal ist es nützlich zu definieren gcd(0, 0) = 0 und lcm(0, 0) = 0 denn dann werden die natürlichen Zahlen zu einem vollständigen Verteilungsgitter mit GCD als Meet und LCM als Join-Operation.[23] Diese Erweiterung der Definition ist auch mit der unten angegebenen Verallgemeinerung für kommutative Ringe kompatibel.
  • In einem kartesischen Koordinatensystem gcd(ein, B) kann als die Anzahl der Segmente zwischen Punkten mit ganzzahligen Koordinaten auf dem geraden Liniensegment interpretiert werden, das die Punkte verbindet (0, 0) und (ein, B).
  • Für nicht negative ganze Zahlen ein und B, wo ein und B nicht beide Null sind, beweisbar durch Betrachtung des euklidischen Algorithmus in base n:[24]
    gcd(nein − 1, nB − 1) = ngcd(ein,B) − 1.
  • Eine Identität, die die Totient-Funktion von Euler beinhaltet:

Wahrscheinlichkeiten und Erwartungswert[edit]

1972 zeigte James E. Nymann, dass k ganze Zahlen, unabhängig und einheitlich ausgewählt aus {1, …, n}, sind teilerfremd mit Wahrscheinlichkeit 1/ζ(k) wie n geht ins Unendliche, wo ζ bezieht sich auf die Riemannsche Zetafunktion.[25] (Siehe coprime für eine Ableitung.) Dieses Ergebnis wurde 1987 erweitert, um zu zeigen, dass die Wahrscheinlichkeit, dass k Zufallszahlen haben den größten gemeinsamen Teiler D ist D−k/ζ(k).[26]

Anhand dieser Informationen kann festgestellt werden, dass der Erwartungswert der größten gemeinsamen Teilerfunktion (informell) nicht existiert, wenn k = 2. In diesem Fall ist die Wahrscheinlichkeit, dass die GCD gleich D ist D-2/ζ(2), und da ζ(2) = π2/6 wir haben

Diese letzte Summation ist die harmonische Reihe, die divergiert. Wenn jedoch k ≥ 3, der Erwartungswert ist wohldefiniert, und nach obigem Argument ist er

Zum k = 3, dies entspricht ungefähr 1,3684. Zum k = 4, es ist ungefähr 1.1106.

In kommutativen Ringen[edit]

Der Begriff des größten gemeinsamen Teilers kann allgemeiner für Elemente eines beliebigen kommutativen Rings definiert werden, obwohl es im Allgemeinen nicht für jedes Paar von Elementen einen geben muss.

Wenn R ein kommutativer Ring ist und ein und B sind in R, dann ein Element D von R heißt a gemeinsamer Teiler von ein und B wenn es beides teilt ein und B (das heißt, wenn es Elemente gibt x und ja in R so dass D·x = ein und D·ja = B). Wenn D ist ein gemeinsamer Teiler von ein und B, und jeder gemeinsame Teiler von ein und B teilt D, dann D heißt a größter gemeinsamer Teiler von ein und B.

Mit dieser Definition sind zwei Elemente ein und B kann sehr wohl mehrere größte gemeinsame Teiler haben oder gar keine. Wenn R ein ganzzahliger Bereich ist, dann sind zwei beliebige GCDs von ein und B müssen assoziierte Elemente sein, da per Definition eines das andere teilen muss; in der Tat, wenn ein GCD existiert, ist jeder seiner Partner ebenfalls ein GCD. Die Existenz einer GCD ist in beliebigen Integralbereichen nicht gewährleistet. Wie auch immer, wenn R eine eindeutige Faktorisierungsdomäne ist, dann haben zwei beliebige Elemente eine GCD, und allgemeiner gilt dies für GCD-Domänen. Wenn R ist eine euklidische Domäne, in der die euklidische Division algorithmisch gegeben ist (wie es zum Beispiel der Fall ist, wenn R = F[X] wo F ein Feld ist, oder wenn R der Ring von Gaußschen ganzen Zahlen ist), dann können die größten gemeinsamen Teiler unter Verwendung einer Form des Euklidischen Algorithmus basierend auf dem Divisionsverfahren berechnet werden.

Das Folgende ist ein Beispiel für einen ganzzahligen Bereich mit zwei Elementen, die keine GCD haben:

Die Elemente 2 und 1 + -3 sind zwei maximale gemeinsame Teiler (d. h. jeder gemeinsame Teiler, der ein Vielfaches von 2 ist, ist mit 2 verknüpft, dasselbe gilt für 1 + -3, aber sie sind nicht verbunden, daher gibt es keinen größten gemeinsamen Teiler von ein und B.

Entsprechend der Bézout-Eigenschaft können wir in jedem kommutativen Ring die Sammlung von Elementen der Form pa + qb, wo P und Q über den Ring reichen. Dies ist das Ideal, das von . erzeugt wird ein und B, und wird einfach (ein, B). In einem Ring, dessen Ideale alle Hauptideale sind (ein Hauptidealbereich oder PID), ist dieses Ideal identisch mit der Menge der Vielfachen eines Ringelements D; dann das D ist ein größter gemeinsamer Teiler von ein und B. Aber das Ideal (ein, B) kann auch dann nützlich sein, wenn es keinen größten gemeinsamen Teiler von gibt ein und B. (In der Tat benutzte Ernst Kummer dieses Ideal als Ersatz für eine GCD in seiner Behandlung von Fermats letztem Satz, obwohl er es sich als Menge von Vielfachen einiger hypothetischer oder Ideal, Ringelement D, daher der ringtheoretische Term.)

Siehe auch[edit]

  1. ^ ein B Lange (1972, S. 33)
  2. ^ ein B C Pettofrezzo & Byrkit (1970, S. 34)
  3. ^ Kelley, W. Michael (2004), Der vollständige Leitfaden für Idioten zur Algebra, Pinguin, p. 142, ISBN 9781592571611.
  4. ^ Jones, Allyn (1999), Ganze Zahlen, Dezimalzahlen, Prozentsätze und Brüche Jahr 7, Pascal-Press, S. 16, ISBN 9781864413786.
  5. ^ ein B C Hardy & Wright (1979, S. 20)
  6. ^ Einige Autoren behandeln größter gemeinsamer Nenner als synonym mit größter gemeinsamer Teiler. Dies widerspricht der gängigen Bedeutung der verwendeten Wörter, da Nenner bezieht sich auf Brüche, und zwei Brüche haben keinen größten gemeinsamen Nenner (wenn zwei Brüche den gleichen Nenner haben, erhält man einen größeren gemeinsamen Nenner, indem man alle Zähler und Nenner mit derselben ganzen Zahl multipliziert).
  7. ^ Barlow, Peter; Pfau, George; Lardner, Dionysius; Luftig, Sir George Biddell; Hamilton, HP; Levy, A.; De Morgan, Augustus; Mosley, Henry (1847), Enzyklopädie der reinen Mathematik, R. Griffin und Co., p. 589.
  8. ^ Einige Autoren verwenden (ein, B),[1][2][5] aber diese Notation ist oft mehrdeutig. Andrews (1994, S. 16) erklärt dies so: “Viele Autoren schreiben (ein,B) zum gcd(ein, B). Wir nicht, weil wir oft verwenden werden (ein,B), um einen Punkt in der euklidischen Ebene darzustellen.”
  9. ^ Thomas H. Cormen, et al., Einführung in Algorithmen (2. Auflage, 2001) ISBN 0262032937, p. 852
  10. ^ Bernard L. Johnston, Fred Richman, Zahlen und Symmetrie: Eine Einführung in die Algebra ISBN 084930301X, p. 38
  11. ^ Martyn R. Dixon, et al., Eine Einführung in wesentliche algebraische Strukturen ISBN 1118497759, p. 59
  12. ^ zB Wolfram Alpha Berechnung und Maxima
  13. ^ Jonathan Katz, Yehuda Lindell, Einführung in die moderne Kryptographie ISBN 1351133012, 2020, Abschnitt 9.1.1, p. 45
  14. ^ Weisstein, Eric W. “Größter gemeinsamer Teiler”. mathworld.wolfram.com. Abgerufen 2020-08-30.
  15. ^ “Größter gemeinsamer Teiler”. www.mathsisfun.com. Abgerufen 2020-08-30.
  16. ^ Gustavo Delfino, “Das kleinste gemeinsame Vielfache und den größten gemeinsamen Teiler verstehen”, Wolfram Demonstrations Project, Veröffentlicht: 1. Februar 2013.
  17. ^ Slavin, Keith R. (2008). “Q-Binome und der größte gemeinsame Teiler”. INTEGERS: Das elektronische Journal der kombinatorischen Zahlentheorie. Westgeorgien-Universität, Karls-Universität Prag. 8: A5. Abgerufen 2008-05-26.
  18. ^ Schramm, Wolfgang (2008). “Die Fourier-Transformation von Funktionen des größten gemeinsamen Teilers”. INTEGERS: Das elektronische Journal der kombinatorischen Zahlentheorie. Westgeorgien-Universität, Karls-Universität Prag. 8: A50. Abgerufen 2008-11-25.
  19. ^ Knuth, Donald E. (1997). Die Kunst der Computerprogrammierung. 2: Seminumerische Algorithmen (3. Aufl.). Addison-Wesley-Profi. ISBN 0-201-89684-2.
  20. ^ Shallcross, D.; Pan, V.; Lin-Kriz, Y. (1993). “Die NC-Äquivalenz von planar ganzzahliger linearer Programmierung und euklidischer GCD” (PDF). 34. IEEE Symp. Grundlagen der Informatik. S. 557–564.
  21. ^ Chor, B.; Goldreich, O. (1990). „Ein verbesserter paralleler Algorithmus für Integer-GCD“. Algorithmica. 5 (1–4): 1–10. mach:10.1007/BF01840374.
  22. ^ Adelmann, LM; Kompella, K. (1988). “Mit Glätte Parallelität erreichen”. 20th Annual ACM Symposium on Theory of Computing. New York. S. 528–538. mach:10.1145/62212.62264. ISBN 0-89791-264-0.
  23. ^ Müller-Hoissen, Folkert; Walther, Hans-Otto (2012), “Dov Tamari (ehemals Bernhard Teitler)”, in Müller-Hoissen, Folkert; Pallo, Jean-Marcel; Stasheff, Jim (Hrsg.), Associahedra, Tamari-Gitter und verwandte Strukturen: Tamari Memorial Festschrift, Fortschritte in Mathematik, 299, Birkhäuser, S. 1–40, ISBN 9783034804059. Fußnote 27, p. 9: “Zum Beispiel die natürlichen Zahlen mit gcd (größter gemeinsamer Teiler) als treffen und lcm (kleinstes gemeinsames Vielfaches) als Join-Operation ein (vollständiges Verteilungs-)Gitter bestimmen.” Für dieses Ergebnis ist die Einbeziehung dieser Definitionen für 0 notwendig: Lässt man stattdessen 0 aus der Menge der natürlichen Zahlen weg, ist das resultierende Gitter nicht vollständig.
  24. ^ Knuth, Donald E.; Graham, RL; Pataschnik, O. (März 1994). Konkrete Mathematik: Eine Grundlage für die Informatik. Addison-Wesley. ISBN 0-201-55802-5.
  25. ^ Nymann, JE (1972). “Auf die Wahrscheinlichkeit, dass k positive ganze Zahlen sind relativ prim”. Zeitschrift für Zahlentheorie. 4 (5): 469–473. mach:10.1016/0022-314X(72)90038-8.
  26. ^ Chidambaraswamy, J.; Sitarmachandrarao, R. (1987). “Über die Wahrscheinlichkeit, dass die Werte von m Polynome haben eine gegebene gcd” Zeitschrift für Zahlentheorie. 26 (3): 237–245. mach:10.1016/0022-314X(87)90081-3.

Verweise[edit]

  • Andrews, George E. (1994) [1971], Zahlentheorie, Dover, ISBN 9780486682525
  • Hardy, GH; Wright, EM (1979), Eine Einführung in die Zahlentheorie (Fünfte Aufl.), Oxford: Oxford University Press, ISBN 978-0-19-853171-5
  • Lange, Calvin T. (1972), Grundlegende Einführung in die Zahlentheorie (2. Aufl.), Lexington: DC Heath and Company, LCCN 77171950
  • Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elemente der Zahlentheorie, Englewood Cliffs: Prentice Hall, LCCN 71081766

Weiterlesen[edit]

  • Donald Knut. Die Kunst der Computerprogrammierung, Band 2: Seminumerische Algorithmen, Dritte Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Abschnitt 4.5.2: Der größte gemeinsame Teiler, S. 333–356.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, Zweite Ausgabe. MIT Press und McGraw-Hill, 2001. ISBN 0-262-03293-7. Abschnitt 31.2: Größter gemeinsamer Teiler, S. 856–862.
  • Saunders Mac Lane und Garrett Birkhoff. Ein Überblick über die moderne Algebra, Vierte Edition. MacMillan Publishing Co., 1977. ISBN 0-02-310070-2. 1–7: “Der euklidische Algorithmus.”


after-content-x4