Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches

Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache sind zwei eng zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle.

Für zwei natürliche Zahlen m und n gibt es stets einen größten gemeinsamen Teiler ggT(m,n), d.h. eine größte natürliche Zahl, durch die sowohl m als auch n ohne Rest teilbar sind. Es gibt auch ein kleinstes gemeinsames Vielfaches kgV(m,n), d.h. eine kleinste natürliche Zahl, die ihrerseits durch m und n ohne Rest teilbar ist.

Da m \cdot n = \mbox{ggT}(m,n) \cdot \mbox{kgV}(m,n) gilt, lässt sich jeweils der kgV aus dem ggT errechnen, und umgekehrt.

Inhaltsverzeichnis

Anwendung in der Bruchrechnung

Angenommen, man möchte zwei Brüche addieren:

\frac{77}{21} + \frac{91}{35}

Dann wird man zuerst einen möglichst kleinen gemeinsamen Nenner der beiden Brüche suchen. Man kann natürlich der Einfachheit halber 21 mit 35 multiplizieren, was 735 ergibt. Man kann aber auch das kgV von 21 und 35 berechnen, welches 105 ist.

\frac{5 \cdot 77}{5 \cdot 21} + \frac{3 \cdot 91}{3 \cdot 35} = \frac{385 + 273}{105} = \frac{658}{105}

Um Zähler und Nenner kleiner zu bekommen, bestimmt man den ggT von 658 und 105, der 7 beträgt. Damit lässt sich der Bruch nun kürzen:

\frac{658}{105} = \frac{94 \cdot 7}{15 \cdot 7} = \frac{94}{15}

Berechnung

Berechnung über die Primfaktorzerlegung

ggT und kgV kann man über die Primfaktorzerlegung (Faktorisierung) von a und b bestimmen. Ein Beispiel:

a = 3528 = 23 · 32 · 50 · 72
b = 3780 = 22 · 33 · 51 · 71

Für den ggT nimmt man die kleinsten Exponenten der zugehörigen Basen:

ggT(3528,3780) = 22 · 32 · 50 · 71 = 252

Für das kgV verwendet man die größten Exponenten der jeweiligen Basen:

kgV(3528,3780) = 23 · 33 · 51 · 72 = 52.920

Berechnung über den euklidschen Algorithmus

Da die Faktorisierung großer Zahlen kein triviales Problem ist, gibt es einen einfacheren Weg, den ggT über den euklidschen Algorithmus (Beschreibung des Algorithmus siehe dort) zu berechnen, der auf den griechischen Mathematiker Euklid (300 v. Chr.) zurückgeht.

Aus dem Produkt von m und n und dem ggT(m,n) lässt sich über den Zusammenhang \mbox{kgV}(m,n) = \frac{m \cdot n}{\mbox{ggT}(m,n)} das kgV bestimmen.

Berechnung des ggT und des kgV von mehreren Zahlen

Der ggT und das kgV lässt sich von beliebig vielen natürlichen Zahlen berechnen, da beide Abbildungen sowohl kommutativ als auch, was noch viel wichtiger ist, assoziativ sind:

Assoziativgesetz:
ggT(m,ggT(n,o)) = ggT(ggT(m,n),o) = ggT(m,n,o)
kgV(m,kgV(n,o)) = kgV(kgV(m,n),o) = kgV(m,n,o)

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

Der ggT von a und b lässt sich als Linearkombination von a und b mit zwei ganzzahligen Koeffizienten s, t darstellen:

ggT(a,b)=sa+tb.

Die Koeffizienten s und 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:

Rechenregeln

Für alle ganzen Zahlen a, b gilt:

Ist zusätzlich m eine natürliche Zahl, dann gilt:

Ist m ein gemeinsamer Teiler von a und b, dann gilt:

Der ggT ist in folgendem Sinne eine multiplikative Funktion: Sind a und b teilerfremd, dann ist

ggT(ab,m) = ggT(a,m)ggT(b,m)

kgV und ggT in weiteren algebraischen Strukturen

kgV und ggT lassen sich nicht nur für natürliche (und ganze) Zahlen definieren. Man kann ihn z.B. auch für Polynome bilden. Statt der Primzahlzerlegung nimmt man hier die Zerlegung in irreduzible Faktoren:

f(x) = x² + 2xy + y² = (x + y
g(x) = x² - y² = (x + y) (x - y)

Dann ist ggT(f,g) = x + y und kgV(f,g) = (x + y)² (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 "<" angeordnet werden können. Deshalb ersetzt man diese Anordnung durch die durch den Teilbarkeitsbegriff definierte partielle Ordnung.

Ist d ein Ringelement, das sowohl Teiler von a als auch Teiler von b ist, dann heißt d ein gemeinsamer Teiler von a und b. Gilt zusätzlich, dass jeder weitere gemeinsame Teiler von a und b auch ein Teiler von d ist, dann heißt d ein größter gemeinsamer Teiler von a und b.

Analog ist das kgV definiert: Ein Ringelement v heißt kleinstes gemeinsames Vielfaches zweier Ringelemente a und b, wenn v ein gemeinsames Vielfaches von a und b ist und seinerseits jedes andere gemeinsame Vielfache von a und b ein Vielfaches von v ist.

Formell schreibt man diese Definition so:

d = \mathrm{ggT}(a,b) :\Leftrightarrow d \mid a, d \mid b, \forall e \in \mathbb{N}: (e \mid a, e \mid b) \Rightarrow e \mid d
v = \mathrm{kgV}(a,b) :\Leftrightarrow a \mid v, b \mid v, \forall e \in \mathbb{N}: (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 Z+iZ ist der größte gemeinsame Teiler von 2 und 1+3i gerade 1+i, denn 2=-i(1+i)2 und 1+3i=(1+i)(2+i). Genau genommen ist 1+i ein größter gemeinsamer Teiler, da alle zu dieser Zahl assozierten Zahlen ebenfalls größte gemeinsame Teiler sind.

Nicht in jedem Ring existiert für zwei Elemente ein ggT oder ein kgV. Wenn sie einen ggT haben, können sie mehrere ggTs haben. Ist der Ring ein Integritätsring, dann sind alle ggTs zueinander assoziiert.

Ist R ein Integritätsring, und haben die Elemente a und b ein kgV, dann haben sie auch einen ggT, und es gilt die Gleichung

a \cdot b = \mbox{ggT}(a,b) \cdot \mbox{kgV}(a,b)

Ist jedoch nur bekannt, dass ein ggT von a und b existiert, dann muss nicht unbedingt auch ein kgV existieren.

Beispiel:

Im Integritätsring R = \mathbb{Z}[\sqrt{-3}] haben die Elemente

a := 4 = 2\cdot 2 = (1+\sqrt{-3})(1-\sqrt{-3}),\quad b := (1+\sqrt{-3})\cdot 2

keinen ggT: Die Elemente 1+\sqrt{-3} und 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 ggT von a und b.

Die genannten Elemente 1+\sqrt{-3} und 2 haben aber ihrerseits einen ggT, nämlich 1. Dagegen haben sie kein kgV, denn wenn v ein kgV wäre, dann folgt aus der "ggT-kgV-Gleichung", dass v assoziiert zu k:=(1+\sqrt{-3})\cdot2 sein muss. Das gemeinsame Vielfache 4 ist jedoch kein Vielfaches von k, also ist k kein kgV und die beiden Elemente haben gar kein kgV.

Ein Integritätsring, in dem je zwei Elemente einen ggT besitzen, heißt ggT-Ring oder ggT-Bereich.

In einem ggT-Ring haben je zwei Elemente auch ein kgV.

In einem faktoriellen Ring haben je zwei Elemente einen ggT.

In einem euklidischen Ring lässt sich der ggT zweier Elemente mit dem Euklidischen Algorithmus bestimmen.

See also: Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches, 300 v. Chr., Division mit Rest, Euklid, Euklidischer Algorithmus, Euklidischer Ring, Faktorieller Ring, Integritätsring, Inverses Element, Irreduzibles Polynom