KgV und ggT

KgV und ggT

In den natürlichen Zahlen N spielen der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) eine wichtige Rolle.

Man sagt, eine Zahl a teilt b (oder a ist Teiler von b, geschrieben a | b), wenn es eine Zahl c gibt, so dass a·c = b ist. Umgekehrt heißt b dann auch ein Vielfaches von a.

Als ggT zweier Zahlen a und b bezeichnet man die größte natürliche Zahl t, welche sowohl a als auch b teilt. Das kgV von a und b ist die kleinste natürliche Zahl v, die sowohl von a als auch b geteilt wird.

Formell schreibt man:

t = ggT(a,b) <=> e | a und e | b, dann gilt auch e | t
v = kgV(a,b) <=> a | f und b | f, dann gilt auch v | f

Table of contents

1 Berechnung
2 Beispiele für die praktische Anwendung
3 kgV und ggT in weiteren algebraischen Strukturen

Berechnung

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

a = 63 = 3²*7

b = 105 = 3*5*7

Für den ggT nimmt man alle Primfaktorenen, die a und b gemeinsam haben - in dem Fall 3 und 7 - und bildet daraus das Produkt. Kommen Faktoren mit einem Exponenten vor, wird jeweils der kleinste Exponent genommen. Das kgV wird ähnlich berechnet, hier wird allerdings jeder Primfaktor mit jeweils dem höchsten Exponenten genommen. Für unser Beispiel also 3², 5 und 7, das kgV ist 315.

Die Faktorisierung großer Zahlen ist kein triviales Problem. Eine einfachere Methode, um den ggT zu berechnen, hat der griechische Mathematiker Euklid bereits um 300 v. Chr. angegeben, den so genannte Euklidischen Algorithmus:

setze m = a; n = b
berechne m:n mit Divisionsrest r
setze m = n, n = r
ist n ≠ 0 fahre fort mit Schritt 2

Nach Ablauf erhält man m = ggT(a,b). Oftmals wird a ≥ b als Eingabe vorausgesetzt. Das ist bei dieser Form des Euklidischen Algorithmus aber nicht notwendig, da sich hier die Zahlen von selbst vertauschen, wenn a < b sein sollte.

Durch den Zusammenhang

kann man nun aus dem ggT das kgV berechnen.

Beispiele für die praktische Anwendung

kgV und ggT sind nützliche Hilfsmittel bei der Bruchrechnung. Zur Vereinfachung eines Bruchs berechnet teilt man Zähler und Nenner durch ihren ggT:

Zur Addition von Brüchen muss man diese auf einen gemeinsamen Hauptnenner bringen. Der kleinste gemeinsame Nenner ist mit dem kgV identisch.

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 Linearfaktoren:

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.

Teilbarkeit ist ein Grundbegriff aus der Ringtheorie. Nicht in jedem Ring lässt sich jedoch ein kleinster gemeinsamer Teiler definieren. Gibt es jedoch für je zwei Ringelemente einen eindeutigen ggT, so sind auch kgV und Division mit Rest eindeutig. Solche Ringe heißen euklidisch, da in ihnen der Euklidische Algorithmus terminiert.