Das Fotonexus-Wiki befindet sich im Testbetrieb.

---

Aus Fotonexus.

Der größte gemeinsame Teiler (Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT} ) und das kleinste gemeinsame Vielfache (Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV} ) sind zwei eng zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle.

Für zwei ganze Zahlen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): n

, die nicht beide Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 0

sind, gibt es stets einen größten gemeinsamen Teiler Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(m, n)

, d. h. die größte natürliche Zahl, durch die sowohl Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m

als auch Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): n
ohne Rest teilbar sind. Sind Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): n
nicht null, so gibt es auch ein kleinstes gemeinsames Vielfaches Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}(m,n)

, d. h. eine kleinste positive ganze Zahl, die sowohl Vielfaches von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m

als auch Vielfaches von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): n
ist. Ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m
oder Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): n
gleich null, so legt man Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}(m, n) = 0
fest.

Insbesondere ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(m,1)=1

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}(m,1)=|m|
sowie Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(m,0)=|m|
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}(m,0)=0

.

Es gilt stets Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): |m \cdot n| = \operatorname{ggT}(m,n) \cdot \operatorname{kgV}(m, n) , also lässt sich jeweils das Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}

aus dem Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}
errechnen, und umgekehrt.

In der englischsprachigen internationalen Literatur wird der Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

mit Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{gcd}
(greatest common divisor) und das Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}
mit Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{lcm}
(least common multiple) bezeichnet.

Inhaltsverzeichnis 1 Anwendung in der Bruchrechnung 2 Berechnung 2.1 Berechnung über die Primfaktorzerlegung 2.2 Berechnung durch den euklidschen Algorithmus 3 Berechnung des ggT und des kgV von mehreren Zahlen 4 Darstellung von ggT(m, n) aus m und n 5 Rechenregeln 6 kgV und ggT in weiteren algebraischen Strukturen 6.1 Beispiel

Anwendung in der Bruchrechnung

Angenommen, wir möchten zwei Brüche addieren:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \frac{17}{21} + \frac{44}{35}

Dann wird man zuerst einen möglichst kleinen gemeinsamen Nenner der beiden Brüche suchen. Man kann natürlich der Einfachheit halber Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 21

mit Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 35
multiplizieren, was Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 735
ergibt. Man kann aber auch das Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}
von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 21
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 35
berechnen, welches Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 105
ist. Die beiden Brüche werden auf den Nenner Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 105
erweitert:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \frac{17}{21} + \frac{44}{35} = \frac{5 \cdot 17}{5 \cdot 21} + \frac{3 \cdot 44}{3 \cdot 35} = \frac{85 + 132}{105} = \frac{217}{105}

Um Zähler und Nenner kleiner zu bekommen, bestimmt man den Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 217
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 105

, der Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 7

beträgt. Damit lässt sich der Bruch durch Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 7
kürzen:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \frac{217}{105} = \frac{31 \cdot 7}{15 \cdot 7} = \frac{31}{15}

Berechnung

Berechnung über die Primfaktorzerlegung

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}
kann man über die Primfaktorzerlegung (Faktorisierung) von a und b bestimmen. Ein Beispiel: 

a = 3528 = 2³ · 3² · 5⁰ · 7²

b = 3780 = 2² · 3³ · 5¹ · 7¹

Für den Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

nimmt man die kleinsten Exponenten der zugehörigen Basen die in beiden Primfaktorzerlegungen vorkommen:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

(3528,3780) = 2² · 3² · 5⁰ · 7¹ = 252

Für das Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}

verwendet man die größten Exponenten der jeweiligen Basen:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}

(3528,3780) = 2³ · 3³ · 5¹ · 7² = 52.920

Berechnung durch den euklidschen Algorithmus

Die Berechnung der Primfaktorzerlegung großer Zahlen und damit auch die Bestimmung des größten gemeinsamen Teilers bzw. des kleinsten gemeinsamen Vielfachen nach obiger Methode ist sehr aufwändig. Mit dem euklidschen Algorithmus existiert jedoch ein effizientes Verfahren, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen. Dieses Verfahren wird durch den Steinschen Algorithmus noch weiter verbessert.

Mit Hilfe des größten gemeinsamen Teilers kann dann auch das kleinste gemeinsame Vielfache effizient berechnet werden:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}(m,n) = \frac{|m \cdot n|}{\operatorname{ggT}(m,n)}

Berechnung des ggT und des kgV von mehreren Zahlen

Der Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

und das Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}
lassen sich von beliebig vielen Zahlen berechnen, da beide Abbildungen assoziativ sind:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(m,\,\operatorname{ggT}(n,p)) = \operatorname{ggT}(\operatorname{ggT}(m,n),\,p) = \operatorname{ggT}(m,n,p)

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}(m,\,\operatorname{kgV}(n,p)) = \operatorname{kgV}(\operatorname{kgV}(m,n),\,p) = \operatorname{kgV}(m,n,p)

Darstellung von ggT(m, n) aus m und n

Hauptartikel: Erweiterter euklidischer Algorithmus.

Der Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
lässt sich als Linearkombination von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
mit zwei ganzzahligen Koeffizienten Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): s
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): t
darstellen:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a,b)=sa+tb

Die Koeffizienten Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): s

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): t
können mit einer Erweiterung des Euklidischen Algorithmus bestimmt werden. Nützlich ist dies z. B. bei der Berechnung von Inversen in Restklassenringen.

Beispiele:

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(12,18) = 6 = (-1)\cdot 12 + 1\cdot 18

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(3,8) = 1 = (-5)\cdot 3 + 2\cdot 8

Rechenregeln

Für alle ganzen Zahlen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
gilt:

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a, b) = \operatorname{ggT}(b, a)

Kommutativgesetz

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(-a, b) = \operatorname{ggT}(a, b)

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a, a) = |a|

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a, 0) = |a|

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a, 1) = 1

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a, b) = \operatorname{ggT}(b,a \;\bmod\; b)

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a, b) = \operatorname{ggT}(b,a-b)

Ist zusätzlich Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m

eine natürliche Zahl, dann gilt:

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(m a, m b) = m \cdot\operatorname{ggT}(a, b)

Distributivgesetz

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a + m b, b) = \operatorname{ggT}(a, b)

Ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): m

ein gemeinsamer Teiler von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b

, dann gilt:

• Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a/m, b/m) = \operatorname{ggT}(a, b)/m

Der Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

ist in folgendem Sinne eine multiplikative Funktion: Sind Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
teilerfremd, dann ist

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(a b, m) = \operatorname{ggT}(a, m) \cdot\operatorname{ggT}(b, m)

kgV und ggT in weiteren algebraischen Strukturen

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}
lassen sich nicht nur für natürliche (und ganze) Zahlen definieren. Man kann sie z. B. auch für Polynome bilden. Statt der Primzahlzerlegung nimmt man hier die Zerlegung in irreduzible Faktoren:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): f(x) = x^2 + 2xy + y^2 = (x + y)^2

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): g(x) = x^2 - y^2 = (x + y) (x - y)

Dann ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}(f, g) = x + y

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}(f, g) = (x + y)^2 (x - y)

.

Möglich wird dies, da auch für Polynome eine Division mit Rest existiert.

Um den Begriff des größten gemeinsamen Teilers auf beliebige kommutative Ringe ausdehnen zu können, muss man die Definition ändern, da in beliebigen Ringen nicht vorausgesetzt werden kann, dass die Elemente bezüglich Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): <

angeordnet werden können. Deshalb ersetzt man diese Anordnung durch die durch den Teilbarkeitsbegriff definierte partielle Ordnung.

Ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): d

ein Ringelement, das sowohl Teiler von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
als auch Teiler von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
ist, dann heißt Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): d
ein gemeinsamer Teiler von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b

. Gilt zusätzlich, dass jeder weitere gemeinsame Teiler von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
auch ein Teiler von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): d
ist, dann heißt Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): d
ein größter gemeinsamer Teiler von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b

.

Analog ist das Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}

definiert: Ein Ringelement Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): v
heißt kleinstes gemeinsames Vielfaches zweier Ringelemente Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b

, wenn Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): v

ein gemeinsames Vielfaches von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
ist und seinerseits jedes andere gemeinsame Vielfache von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
ein Vielfaches von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): v
ist.

Formal schreibt man diese Definition für einen Ring Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): R

so:

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): d = \operatorname{ggT}(a, b)\quad :\Longleftrightarrow\quad d \mid a,\; d \mid b,\; \forall e \in R: (e \mid a,\, e \mid b) \Rightarrow e \mid d

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): v = \operatorname{kgV}(a, b)\quad :\Longleftrightarrow\quad a \mid v,\; b \mid v,\; \forall e \in R: (a \mid e,\, b \mid e) \Rightarrow v \mid e

Diese allgemeinere Definition lässt sich auf mehrere Zahlen ausweiten (sogar auf unendlich viele).

Beispiel: Im Gaußschen Zahlenring Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \Z+\mathrm{i}\Z

ist der größte gemeinsame Teiler von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 2
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1 + 3i
gerade Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1 + i

, denn Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 2 = -i (1 + i)^2

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1 + 3i = (1 + i) (2 + i)

. Genau genommen ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1 + i

ein größter gemeinsamer Teiler, da alle zu dieser Zahl assoziierten Zahlen ebenfalls größte gemeinsame Teiler sind.

Nicht in jedem Ring existiert für zwei Elemente ein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

oder ein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}

. Wenn sie einen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

haben, können sie mehrere Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

’s haben. Ist der Ring ein Integritätsring, dann sind alle Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT} ’s zueinander assoziiert.

Ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): R

ein Integritätsring, und haben die Elemente Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
ein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}

, dann haben sie auch einen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT} , und es gilt die Gleichung

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a \cdot b = \operatorname{ggT}(a, b) \cdot \operatorname{kgV}(a, b)

Ist jedoch nur bekannt, dass ein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b
existiert, dann muss nicht unbedingt auch ein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}
existieren.

Beispiel

Im Integritätsring Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): R = \mathbb{Z}[\sqrt{-3}]

haben die Elemente

Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a := 4 = 2\cdot 2 = (1 + \sqrt{-3})(1 - \sqrt{-3}),\quad b := (1 + \sqrt{-3})\cdot 2

keinen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

Die Elemente Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1 + \sqrt{-3}

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 2
sind zwei maximale gemeinsame Teiler (d. h. jeder gemeinsame Teiler, der von einem der beiden Elemente geteilt wird, ist zu diesem assoziiert), aber diese zwei Elemente sind nicht zueinander assoziiert, also gibt es keinen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}
von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): a
und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): b

.

Die genannten Elemente Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1+\sqrt{-3}

und Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 2
haben aber ihrerseits einen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

, nämlich Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 1 . Dagegen haben sie kein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV} , denn wenn Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): v

ein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}
wäre, dann folgt aus der „Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

-Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV} -Gleichung“, dass Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): v

assoziiert zu Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): k:=(1 + \sqrt{-3})\cdot2
sein muss. Das gemeinsame Vielfache Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): 4
ist jedoch kein Vielfaches von Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): k

, also ist Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): k

kein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}
und die beiden Elemente haben gar kein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV}

.

Ein Integritätsring, in dem je zwei Elemente einen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

besitzen, heißt Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

-Ring oder Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT} -Bereich.

In einem Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT} -Ring haben je zwei Elemente auch ein Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{kgV} .

In einem faktoriellen Ring haben je zwei Elemente einen Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT} .

In einem euklidischen Ring lässt sich der Parser-Fehler (Das temporäre Verzeichnis für mathematische Formeln kann nicht angelegt oder beschrieben werden.): \operatorname{ggT}

zweier Elemente mit dem Euklidischen Algorithmus bestimmen.

[[Hilfe:Cache|Fehler beim Thumbnail-Erstellen]]: convert: unable to open image `/var/www/fotonexus/w/images/c/ca/Wikipedia_lexikon3e.jpg': No such file or directory.

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler_und_kleinstes_gemeinsames_Vielfaches, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.