In der Mathematik der größte allgemeine Teiler (gcd), auch bekannt als der größte gemeinsame Faktor (gcf) oder höchste gemeinsame Faktor ist (hcf), zwei oder mehr ganzer Nichtnullzahlen, die größte positive ganze Zahl, die die Zahlen ohne einen Rest teilt.

Zum Beispiel ist der GCD 8 und 12 4.

Dieser Begriff kann zu Polynomen erweitert werden, größten allgemeinen Teiler von zwei Polynomen zu sehen.

Übersicht

Notation

In diesem Artikel werden wir den größten allgemeinen Teiler von zwei ganzen Zahlen a und b als gcd (a, b) anzeigen. Etwas älterer Lehrbuch-Gebrauch (a, b).

Beispiel

Die Nummer 54 kann als ein Produkt von zwei anderen ganzen Zahlen auf mehrere verschiedene Weisen ausgedrückt werden:

:

So sind die Teiler 54:

:

Ähnlich sind die Teiler 24:

:

Die Zahlen, dass diese zwei Listen Anteil gemeinsam die allgemeinen Teiler 54 und 24 sind:

:

Der größte von diesen ist 6. Das ist der größte allgemeine Teiler 54 und 24. Man schreibt:

:

Das Reduzieren von Bruchteilen

Der größte allgemeine Teiler ist nützlich, um Bruchteile zu reduzieren, um in niedrigsten Begriffen zu sein. Zum Beispiel, gcd (42, 56) = 14, deshalb,

:

Zahlen von Coprime

Zwei Zahlen werden relativ erst, oder coprime genannt, wenn ihr größter allgemeiner Teiler 1 gleich ist. Zum Beispiel, 9 und 28 sind relativ erst.

Eine geometrische Ansicht

Zum Beispiel kann ein 24 durch 60 rechteckiges Gebiet in einen Bratrost geteilt werden: 1 durch 1 Quadrate, 2 durch 2 Quadrate, 3 durch 3 Quadrate, 4 durch 4 Quadrate, 6 durch 6 Quadrate oder 12 durch 12 Quadrate. Deshalb, 12 ist der größte allgemeine Teiler 24 und 60. Ein 24 durch 60 rechteckiges Gebiet kann in einen Bratrost von 12 durch 12 Quadraten, mit zwei Quadraten entlang einem Rand (24/12 = 2) und fünf Quadraten entlang dem anderen (60/12 = 5) geteilt werden.

Berechnung

Das Verwenden von erstem factorizations

Größte allgemeine Teiler können im Prinzip durch die Bestimmung des ersten factorizations der zwei Zahlen und das Vergleichen von Faktoren, als im folgenden Beispiel geschätzt werden: Um gcd (18, 84) zu schätzen, finden wir den ersten factorizations 18 = 2 · 3 und 84 = 2 · 3 · 7 und Benachrichtigung, dass das "Übergreifen" der zwei Ausdrücke 2 ist · 3; so gcd (18, 84) = 6. In der Praxis ist diese Methode nur für kleine Zahlen ausführbar; die Computerwissenschaft von erstem factorizations nimmt im Allgemeinen zu lange.

Hier ist ein anderes konkretes Beispiel, das durch ein Venn-Diagramm illustriert ist. Nehmen Sie an, dass es gewünscht wird, um den größten allgemeinen Teiler 48 und 180 zu finden. Finden Sie erstens den ersten factorizations der zwei Zahlen:

: 48 = 2 × 2 × 2 × 2 × 3,

: 180 = 2 × 2 × 3 × 3 × 5.

Was sie teilen, gemeinsam ist zwei "2" s und "3":

:

: Kleinstes Gemeinsames Vielfaches = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

: Größter allgemeiner Teiler = 2 × 2 × 3 = 12.

Das Verwenden des Algorithmus von Euklid

Eine viel effizientere Methode ist der Euklidische Algorithmus, der den Abteilungsalgorithmus in der Kombination mit der Beobachtung verwendet, dass der gcd von zwei Zahlen auch ihren Unterschied teilt. Um gcd (48,18) zu schätzen, teilen Sie sich 48 durch 18, um einen Quotienten 2 und einen Rest 12 zu bekommen. Dann teilen Sie sich 18 durch 12, um einen Quotienten 1 und einen Rest 6 zu bekommen. Dann teilen Sie sich 12 durch 6, um einen Rest 0 zu bekommen, was bedeutet, dass 6 der gcd ist. Bemerken Sie, dass wir den Quotienten in jedem Schritt ignoriert haben außer zu bemerken, als der Rest 0 gereicht hat, Zeichen gebend, dass wir die Antwort erreicht hatten. Formell kann der Algorithmus als beschrieben werden:

::

Der auch als geschrieben werden konnte

::

Wenn die Argumente beide größer sind als Null dann, kann der Algorithmus in elementareren Begriffen wie folgt geschrieben werden:

:

: wenn b wenn ein

Keith Slavin hat dass für den sonderbaren ein  1 gezeigt:

:

der eine Funktion ist, die für den Komplex b bewertet werden kann. Wolfgang Schramm hat dem gezeigt

:

ist eine komplette Funktion in der Variable b für alle positiven ganzen Zahlen, wo c (k) die Summe von Ramanujan ist. Marcelo Polezzi hat dass gezeigt:

:

für positive ganze Zahlen a und b. Donald Knuth hat die folgende Verminderung bewiesen:

:

für natürliche Zahlen a und b, wo a und b nicht beide Null sind. Mehr allgemein

:

der durch das Betrachten des Euklidischen Algorithmus in der Basis n leicht bewiesen werden kann.

Kompliziertheit

Die Existenz der Euklidischen Algorithmus-Plätze (die Entscheidungsproblem-Version) das größte allgemeine Teiler-Problem in P, der Klasse von in der polynomischen Zeit lösbaren Problemen. Wie man bekannt, ist das GCD Problem nicht in NC, und also gibt es keinen bekannten Weg zu parallelize seine Berechnung über viele Verarbeiter; noch, wie man bekannt, ist es P-complete, der andeuten würde, dass es kaum zu parallelize GCD Berechnung möglich sein wird. In diesem Sinn ist das GCD Problem z.B der ganzen Zahl factorization Problem analog, das keinen bekannten polynomisch-maligen Algorithmus hat, aber nicht bekannt ist, NP-complete zu sein. Shallcross. hat gezeigt, dass ein zusammenhängendes Problem (EUGCD, die Rest-Folge bestimmend, die während des Euklidischen Algorithmus entsteht), NC-equivalent zum Problem der ganzen Zahl geradlinige Programmierung mit zwei Variablen ist; wenn entweder Problem in NC ist oder P-complete ist, der andere ist ebenso. Da NC NL enthält, ist es auch unbekannt, ob ein raumeffizienter Algorithmus, für den GCD zu schätzen, sogar für nichtdeterministische Maschinen von Turing besteht.

Obwohl, wie man bekannt, das Problem in NC nicht ist, bestehen parallele Algorithmen mit der als der Euklidische Algorithmus höheren Zeit; der am besten bekannte deterministische Algorithmus ist durch Chor und Goldreich, der (im CRCW-PRAHM-Modell) das Problem in O (n/log n) Zeit mit n Verarbeitern beheben kann. Algorithmen von Randomized können das Problem in O beheben ((loggen Sie n)) Zeit auf Verarbeitern (bemerken, dass das Superpolynom ist).

Eigenschaften

• Jeder allgemeine Teiler von a und b ist ein Teiler von gcd (a, b).
• gcd (a, b), wo a und b nicht sowohl Null sind, kann wechselweise als auch gleichwertig als die kleinste positive ganze Zahl d definiert werden, der in der Form d = a geschrieben werden kann · p + b · q, wo p und q ganze Zahlen sind. Dieser Ausdruck wird die Identität von Bézout genannt. Nummern p und q wie das können mit dem verlängerten Euklidischen Algorithmus geschätzt werden.
• gcd (a, 0) = a, für einen  0, seit jeder Zahl ist ein Teiler 0 und der größte Teiler, a zu sein. Das wird gewöhnlich als der Grundfall im Euklidischen Algorithmus verwendet.
• Wenn ein Teilen des Produktes b · c, und gcd (a, b) = d, dann teilt a/d c.
• Wenn M eine natürliche Zahl, dann gcd ist (M · a, M · b) = M · gcd (a, b).
• Wenn M eine ganze Zahl, dann gcd ist (+ M · b, b) = gcd (a, b).
• Wenn M ein allgemeiner Nichtnullteiler von a und b, dann gcd (a/m, b/m) = gcd (a, b)/m ist.
• Der gcd ist eine Multiplicative-Funktion im folgenden Sinn: Wenn a und relativ erst, dann gcd (a zu sein · a, b) = gcd (a, b) · gcd (a, b).
• Der gcd ist eine Ersatzfunktion: gcd (a, b) = gcd (b, a).
• Der gcd ist eine assoziative Funktion: gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).
• Der gcd von drei Zahlen kann als gcd (a, b, c) = gcd geschätzt werden (gcd (a, b), c), oder auf eine verschiedene Weise durch die Verwendung commutativity und associativity. Das kann zu jeder Zahl von Zahlen erweitert werden.
• gcd (a, b) ist nah mit kleinstem Gemeinsamem Vielfachem lcm (a, b) verbunden: Wir haben

:: gcd (a, b) · lcm (a, b) = a · b.

:This-Formel wird häufig verwendet, um kleinste Gemeinsame Vielfache zu schätzen: Ein erster schätzt den gcd mit dem Algorithmus von Euklid und teilt dann das Produkt der gegebenen Zahlen durch ihren gcd.

• Die folgenden Versionen von distributivity halten für wahr:

:: gcd (a, lcm (b, c)) = lcm (gcd (a, b), gcd (a, c))

:: lcm (a, gcd (b, c)) = gcd (lcm (a, b), lcm (a, c)).

• Es ist nützlich, gcd (0, 0) = 0 und lcm (0, 0) = 0 zu definieren, weil dann die natürlichen Zahlen ein ganzes verteilendes Gitter mit gcd werden, wie sich treffen und lcm, wie sich Operation anschließen. Diese Erweiterung der Definition ist auch mit der Generalisation für Ersatzringe vereinbar, die unten gegeben sind.
• In einem Kartesianischen Koordinatensystem, gcd (a, b) kann als die Zahl von Punkten mit integrierten Koordinaten auf der Gerade interpretiert werden, die sich den Punkten (0, 0) und (a, b) anschließt, (0, 0) ausschließend.

Wahrscheinlichkeiten und erwarteter Wert

1972 hat James E. Nymann gezeigt, dass die Wahrscheinlichkeit, dass k unabhängig gewählte ganze Zahlen coprime sind, 1/ζ (k) ist. (Sieh coprime für eine Abstammung.) Wurde dieses Ergebnis 1987 erweitert, um zu zeigen, dass die Wahrscheinlichkeit, dass k zufällige ganze Zahlen größten allgemeinen Teiler d haben, d/ζ (k) ist.

Mit dieser Information, wie man sehen kann, besteht der erwartete Wert der größten allgemeinen Teiler-Funktion (informell) wenn k = 2 nicht. In diesem Fall ist die Wahrscheinlichkeit, dass der gcd d gleichkommt, d/ζ (2), und seitdem ζ (2) = π/6 haben wir

:

Diese letzte Summierung ist die harmonische Reihe, die abweicht. Jedoch, wenn k  3, der erwartete Wert, und durch das obengenannte Argument bestimmt ist, ist es

:

Für k = 3 ist das 1.3684 ungefähr gleich. Für k = 4 sind es etwa 1.1106.

Der gcd in Ersatzringen

Der Begriff des größten allgemeinen Teilers kann mehr allgemein für Elemente eines willkürlichen Ersatzrings definiert werden, obwohl im Allgemeinen dort ein für jedes Paar von Elementen nicht zu bestehen braucht.

Wenn R ein Ersatzring ist, und a und b in R sind, dann wird ein Element d R einen allgemeinen Teiler von a und b genannt, wenn es sowohl a als auch b teilt (d. h. wenn es Elemente x und y in solchem R dass d gibt · x = a und d · y = b).

Wenn d ein allgemeiner Teiler von a und b ist, und jeder allgemeine Teiler von a und b d teilt, dann wird d einen größten allgemeinen Teiler von a und b genannt.

Bemerken Sie, dass mit dieser Definition zwei Elemente a und b sehr gut mehrere größte allgemeine Teiler oder niemanden überhaupt haben können. Wenn R ein integriertes Gebiet dann ist, müssen irgendwelche zwei gcd's von a und b Mitelemente sein, da definitionsgemäß jeder den anderen teilen muss; tatsächlich, wenn ein gcd besteht, irgendwelche seiner Partner ist ein gcd ebenso. Die Existenz eines gcd wird in willkürlichen integrierten Gebieten nicht gesichert. Jedoch, wenn R ein einzigartiges factorization Gebiet ist, dann haben irgendwelche zwei Elemente einen gcd, und mehr allgemein ist das in gcd Gebieten wahr.

Wenn R ein Euklidisches Gebiet ist, in dem euklidische Abteilung algorithmisch gegeben wird (wie zum Beispiel der Fall ist, wenn R = F [X], wo F ein Feld ist, oder wenn R der Ring von ganzen Zahlen von Gaussian ist), dann können größte allgemeine Teiler mit einer Form des Euklidischen auf dem Abteilungsverfahren gestützten Algorithmus geschätzt werden.

Der folgende ist ein Beispiel eines integrierten Gebiets mit zwei Elementen, die keinen gcd haben:

:

Die Elemente 2 und 1 +  (−3) sind zwei "maximale allgemeine Teiler" (d. h. jeder allgemeine Teiler, der ein Vielfache 2 ist, wird zu 2 vereinigt, dasselbe hält für 1 +  (−3)), aber sie werden nicht vereinigt, also gibt es keinen größten allgemeinen Teiler von a und b.

Entsprechend dem Eigentum von Bezout können wir, in jedem Ersatzring, die Sammlung von Elementen des Form-Papas + qb denken, wo sich p und q über den Ring erstrecken. Das ist das Ideal, das durch a und b erzeugt ist, und wird einfach (a, b) angezeigt. In einem Ring alle sind dessen Ideale (ein ideales Hauptgebiet oder PID) hauptsächlich, wird dieses Ideal mit dem Satz von Vielfachen von einem Ringelement d identisch sein; dann ist dieser d ein größter allgemeiner Teiler von a und b. Aber das Ideal (a, b) kann nützlich sein, selbst wenn es keinen größten allgemeinen Teiler von a und b gibt. (Tatsächlich hat Ernst Kummer dieses Ideal als ein Ersatz für einen gcd in seiner Behandlung des Letzten Lehrsatzes von Fermat verwendet, obwohl er sich es als der Satz von Vielfachen von einigen hypothetisches oder ideales, Ringelement d, woher der ringtheoretische Begriff vorgestellt hat.)

Siehe auch

• Coprime
• Kleinstes Gemeinsames Vielfaches
• Kleinster gemeinsamer Nenner
• Binärer GCD Algorithmus
• Euklidischer Algorithmus
• Verlängerter Euklidischer Algorithmus
• Größter allgemeiner Teiler von zwei Polynomen

Zeichen

Weiterführende Literatur

• Donald Knuth. Die Kunst der Computerprogrammierung, Bands 2: Halbnumerische Algorithmen, die Dritte Ausgabe. Addison-Wesley, 1997. Internationale Standardbuchnummer 0-201-89684-2. Abschnitt 4.5.2: Der Größte Allgemeine Teiler, Seiten 333-356.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 31.2: Größter allgemeiner Teiler, Seiten 856-862.
• Saunders MacLane und Garrett Birkhoff. Ein Überblick über die Moderne Algebra, die Vierte Ausgabe. MacMillan Publishing Co., 1977. Internationale Standardbuchnummer 0-02-310070-2. 1-7: "Der Euklidische Algorithmus."

Außenverbindungen

• größter allgemeiner Teiler an Everything2.com
• Größtes Allgemeines Maß: Die Letzten 2500 Jahre, durch Alexander Stepanov