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

Berechnung

ggT und 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 ggT nimmt man die kleinsten Exponenten der zugehörigen Basen:

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

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

kgV(3528,3780) = 2³ * 3³ * 5¹ * 7² = 52920

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:

1. setze m = a; n = b
2. berechne m:n mit Divisionsrest r
3. setze m = n, n = r
4. 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 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.