Kleinstes gemeinsames Vielfaches

Begriff und Grundidee

Das kleinste gemeinsame Vielfache (kgV) zweier ganzer Zahlen m und n ist die kleinste positive natürliche Zahl, die sowohl ein Vielfaches von m als auch ein Vielfaches von n ist. Für m = 0 oder n = 0 wird zusätzlich festgelegt: kgV(m,n) := 0. Das Gegenstück zum kgV ist der größte gemeinsame Teiler (ggT). Beide Begriffe sind unter anderem in der Arithmetik und Zahlentheorie wichtig. Die englische Bezeichnung lautet least common multiple (lcm).

Berechnung über gemeinsame Vielfache

Eine einfache Methode besteht darin, die positiven Vielfachen beider Zahlen aufzuschreiben und das kleinste gemeinsame Vielfache auszuwählen. Die positiven Vielfachen von 12 sind 12, 24, 36, 48, 60, 72, 84, 96, 108, …; die positiven Vielfachen von 18 sind 18, 36, 54, 72, 90, 108, …. Die gemeinsamen positiven Vielfachen sind 36, 72, 108, …. Daher gilt: kgV(12,18) = 36.

Primfaktorzerlegung

Bei der Primfaktorzerlegung werden die Zahlen in Produkte von Primzahlpotenzen zerlegt. Für das kgV nimmt man alle Primfaktoren, die in mindestens einer Zerlegung vorkommen. Als Exponent verwendet man jeweils den größten der vorkommenden Exponenten.

Beispiel: 3528 = 2³ · 3² · 7² und 3780 = 2² · 3³ · 5¹ · 7¹. Deshalb gilt: kgV(3528,3780) = 2³ · 3³ · 5¹ · 7² = 52.920.

Berechnung mit dem ggT und mehreren Zahlen

Für zwei ganze Zahlen gilt die wichtige Beziehung: ggT(m,n) · kgV(m,n) = |m · n|.

Sind beide Zahlen positiv oder beide negativ, können die Betragsstriche entfallen. Kennt man den ggT, kann man daher eine Zahl durch den ggT teilen und das Ergebnis mit der anderen Zahl multiplizieren: kgV(m,n) = |m · n| : ggT(m,n) = |(m : ggT(m,n)) · n|.

Beispiel: Der ggT von 18 und 24 ist 6. Somit ist kgV(18,24) = (18 : 6) · 24 = 3 · 24 = 72. Der ggT kann beispielsweise mit dem euklidischen Algorithmus bestimmt werden.

Bei mehreren Zahlen nimmt man ebenfalls alle Primfaktoren, die in mindestens einer Zahl vorkommen, jeweils mit der höchsten vorkommenden Potenz. Für 144 = 2⁴ · 3², 160 = 2⁵ · 5¹ und 175 = 5² · 7¹ ergibt sich: kgV(144,160,175) = 2⁵ · 3² · 5² · 7¹ = 50.400.

Das kgV ist assoziativ. Daher kann man schrittweise rechnen: kgV(144,160) = 1440 und anschließend kgV(1440,175) = 50.400. Formal gilt kgV(m,kgV(n,p)) = kgV(kgV(m,n),p). Deshalb ist die Schreibweise kgV(m,n,p) gerechtfertigt.

Anwendung bei Brüchen

Beim Addieren oder Subtrahieren von Brüchen müssen die Brüche auf einen gemeinsamen Nenner erweitert werden. Der kleinstmögliche gemeinsame Nenner heißt Hauptnenner und ist das kgV der ursprünglichen Nenner.

Für 17/21 und 44/35 ist der Hauptnenner kgV(21,35) = 105. Daher gilt: 17/21 + 44/35 = 85/105 + 132/105 = 217/105 = 31/15.

Man könnte die Nenner auch direkt multiplizieren und den Nenner 735 erhalten; das kgV liefert jedoch den kleinstmöglichen gemeinsamen Nenner.

KgV in Ringen und weitere Beispiele

Die Definition des kgV lässt sich auf Ringe verallgemeinern. Ein Ringelement v heißt kleinstes gemeinsames Vielfaches zweier Ringelemente a und b, wenn a und b Teiler von v sind und jedes andere gemeinsame Vielfache von a und b seinerseits ein Vielfaches von v ist. Formal: v = kgV(a,b) ⇔ a ∣ v, b ∣ v und für alle e ∈ R gilt: Aus a ∣ e und b ∣ e folgt v ∣ e.

Diese Definition kann auch auf mehrere oder sogar unendlich viele Elemente ausgedehnt werden. Für Polynome verwendet man anstelle der Primfaktorzerlegung die Zerlegung in irreduzible Faktoren. Aus f(x) = x² + 2xy + y² = (x+y)² und g(x) = x² − y² = (x+y)(x−y) folgt: kgV(f,g) = (x+y)²(x−y).

Im gaußschen Zahlenring Z + iZ ist 1+i ein größter gemeinsamer Teiler von 2 und 1+3i, denn 2 = −i(1+i)² und 1+3i = (1+i)(2+i). Genau genommen ist 1+i ein größter gemeinsamer Teiler; alle zu dieser Zahl assoziierten Zahlen sind ebenfalls größte gemeinsame Teiler.

Nicht in jedem Ring existieren für zwei Elemente ein ggT oder ein kgV. In einem Integritätsring sind alle ggT zueinander assoziiert. Haben a und b in einem Integritätsring ein kgV, gilt: a · b ∼ ggT(a,b) · kgV(a,b). Aus der Existenz eines ggT folgt jedoch nicht immer die Existenz eines kgV.

Im Integritätsring R = Z[√−3] haben a = 4 = 2·2 = (1+√−3)(1−√−3) und b = (1+√−3)·2 keinen ggT. Die Elemente 1+√−3 und 2 sind maximale gemeinsame Teiler, aber nicht zueinander assoziiert. Sie haben ihrerseits den ggT 1, jedoch kein kgV. Ein Integritätsring, in dem je zwei Elemente einen ggT besitzen, heißt ggT-Ring oder ggT-Bereich. In einem ggT-Ring besitzen je zwei Elemente auch ein kgV. In einem faktoriellen Ring haben je zwei Elemente einen ggT; in einem euklidischen Ring kann man den ggT mit dem euklidischen Algorithmus bestimmen.