2001:9E8:B567:C200:69B2:5A:C89D:2D77: /* Berechnung über den größten gemeinsamen Teiler (ggT) */ Bei uns unübliches Divisionszeichen ersetzt

2025-01-13T09:52:17Z

Berechnung über den größten gemeinsamen Teiler (ggT): Bei uns unübliches Divisionszeichen ersetzt

Neue Seite

Das '''kleinste gemeinsame Vielfache''' ('''kgV''') ist ein mathematischer Begriff. Sein Pendant ist der ''[[Größter gemeinsamer Teiler|größte gemeinsame Teiler]]'' (ggT). Beide spielen unter anderem in der [[Arithmetik]] und der [[Zahlentheorie]] eine Rolle.

Das ''kleinste gemeinsame Vielfache'' zweier [[Ganze Zahlen|ganzer Zahlen]] <math>m</math> und <math>n</math> ist die kleinste [[Positive und negative Zahlen|positive]] [[natürliche Zahl]], die sowohl [[Vielfaches]] von <math>m</math> als auch Vielfaches von <math>n</math> ist.<ref>''Schüler-Duden. Die Mathematik I.'' Dudenverlag, Mannheim 1990, ISBN 3-411-04205-2, S. 210.</ref> Zusätzlich wird für den Fall <math>m=0</math> oder <math>n=0</math> das kgV definiert als <math>\operatorname{kgV}(m,\,n):=0</math>.<ref>Harald Scheid: ''Einführung in die Zahlentheorie.'' Klett Verlag, Stuttgart, 1972, ISBN 3-12-983240-8, S. 79.</ref>

Die englische Bezeichnung für das kleinste gemeinsame Vielfache ist ''least common multiple'' oder kurz ''lcm'' und findet in mathematischen Texten ebenfalls Verwendung.<ref>G. H. Hardy, E. M. Wright: ''An Introduction to the Theory of Numbers.'' 5. Auflage. Oxford University Press, Oxford, 1979, ISBN 0-19-853171-0, § 5.1, S. 48.</ref>

== Berechnung des kgV von natürlichen Zahlen ==

=== Berechnung über die Vielfachen ===

* 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 von 12 und 18 sind also 36, 72, 108, …
* und das kleinste von diesen ist 36; in Zeichen:
:<math>\operatorname{kgV}(12, 18) = 36</math>.

=== Berechnung über die Primfaktorzerlegung ===

Man kann das kgV über die [[Primfaktorzerlegung]] der beiden gegebenen Zahlen bestimmen. Beispiel:

:<math>3528 = 2^{\color{Red}3} \cdot 3^{\color{Red}2} \cdot 7^{\color{Red}2}</math>
:<math>3780= 2^{\color{OliveGreen}2} \cdot 3^{\color{OliveGreen}3} \cdot 5^{\color{OliveGreen}1} \cdot 7^{\color{OliveGreen}1}</math>

Für das kgV nimmt man die Primfaktoren, die in mindestens einer der beiden Zerlegungen vorkommen, und als zugehörigen Exponenten den jeweils größeren der Ausgangsexponenten:
:<math>\operatorname{kgV}(3528,3780) = 2^{\color{Red}3} \cdot 3^{\color{OliveGreen}3} \cdot 5^{\color{OliveGreen}1} \cdot 7^{\color{Red}2} = 52.920</math>.<ref>H. Athen, J. Bruhn: ''Lexikon der Schulmathematik.'' Band 2, Aulis Verlag, Köln 1977, S. 488.</ref>

=== Berechnung über den größten gemeinsamen Teiler (ggT) ===

Es gilt die folgende Gleichung:

:<math>\operatorname{ggT}(m,n) \cdot \operatorname{kgV}(m,n) = |m \cdot n| </math>

Sind beide Zahlen positiv oder negativ, so entfallen die Betragsstriche. Damit lässt sich das kgV berechnen, falls der ggT z. B. mit dem [[Euklidischer Algorithmus|euklidischen Algorithmus]] bereits bestimmt wurde. (Umgekehrt kann man mit dieser Formel auch den ggT aus dem kgV berechnen.) Am einfachsten ist es meist, nach der Bestimmung des ggT eine der beiden Zahlen durch den ggT zu teilen und mit der anderen Zahl zu multiplizieren. Der Betrag des Ergebnisses ist das gesuchte kgV. Also gilt:

:<math>\operatorname{kgV}(m,n)= |m \cdot n| : \operatorname{ggT}(m,n) = |(m : \operatorname{ggT}(m,n)) \cdot n|</math>

Beispiel: Der ggT von 18 und 24 ist 6. Zur Berechnung des ggT mittels [[Euklidischer Algorithmus|euklidischem Algorithmus]] siehe den Artikel zum [[Größter gemeinsamer Teiler|ggT]]. Das kgV ist folglich (da beide Zahlen positiv sind, entfällt der Betrag)

:<math>(18 : 6) \cdot 24 = 3 \cdot 24 = 72</math>.

Die Gleichung zu Beginn des Abschnitts ist übrigens leicht zu beweisen:

Nachweis für positive ganze Zahlen m und n, alle anderen Fälle lassen sich analog behandeln. Ist <math>k = \operatorname{kgV}(m,n)</math>, dann ist <math>k</math> auch Teiler des Produkts <math>m \cdot n</math>. Die Zahl <math>g</math> enthalte dagegen alle Primfaktoren des Produkts <math>m \cdot n</math>, die <math>k</math> nicht enthält. Betrachtet man, wie der <math>\operatorname {ggT}(m,n)</math> aus der Primfaktordarstellung des Produkts aus <math>m</math> und <math>n</math> berechnet wird, dann folgt <math>g = \operatorname{ggT}(m,n)</math>. Daraus ergibt sich die obige Gleichung.<ref>[http://math-www.uni-paderborn.de/~chris/Index37/V/par4.pdf math-www.uni-paderborn.de], S. 14 ggT und kgV</ref>

== Das kgV von mehreren Zahlen ==

Man verwendet alle Primfaktoren, die in mindestens einer der Zahlen vorkommen, mit der jeweils höchsten vorkommenden Potenz, zum Beispiel:

:<math>144 = 2^{\color{Red}4} \cdot 3^{\color{Red}2}</math>
:<math>160= 2^{\color{OliveGreen}5} \cdot 5^{\color{OliveGreen}1}</math>
:<math>175= 5^{\color{Blue}2} \cdot 7^{\color{Blue}1},</math>

also:

:<math>\operatorname{kgV}(144,160,175) = 2^{\color{OliveGreen}5} \cdot 3^{\color{Red}2} \cdot 5^{\color{Blue}2} \cdot 7^{\color{Blue}1} = 50.400.</math>

Man könnte auch zunächst <math>\operatorname{kgV}(144,160) = 1440</math> berechnen und danach <math>\operatorname{kgV}(1440,175) = 50.400,</math> denn als eine zweistellige [[Verknüpfung (Mathematik)|Verknüpfung]] auf den ganzen Zahlen ist das kgV [[Assoziativgesetz|assoziativ]]:

:<math>\operatorname{kgV}(m,\operatorname{kgV}(n,p)) = \operatorname{kgV}(\operatorname{kgV}(m,n),\,p).</math>

Dies rechtfertigt die Schreibweise <math>\operatorname{kgV}(m,n,p)</math>.<ref>Harald Scheid: ''Einführung in die Zahlentheorie.'' Klett Verlag, Stuttgart 1972, ISBN 3-12-983240-8, S. 84/85.</ref>

== Anwendungen ==
=== Bruchrechnung ===
Angenommen, man möchte die Brüche <math>\tfrac{17}{21}</math> und <math>\tfrac{44}{35}</math> addieren. Dazu müssen diese durch [[Erweitern]] auf einen gemeinsamen Nenner gebracht werden. Man könnte <math>21</math> mit <math>35</math> multiplizieren, was <math>735</math> ergibt. Der kleinstmögliche gemeinsame Nenner (der sog. [[Hauptnenner]]) ist aber <math>\operatorname{kgV}(21,35) = 105</math>.<ref>Heinz Griesel und andere: ''Elemente der Mathematik'' Niedersachsen 5. Schuljahr, Schroedel Verlag, Hannover 2005, ISBN 3-507-87205-6, S. 173.</ref> Die beiden Brüche werden auf diesen Nenner erweitert und dann addiert. Das Ergebnis wird gekürzt:
:<math>\frac{17}{21} + \frac{44}{35} = \frac{{\color{Red}5} \cdot 17}{{\color{Red}5} \cdot 21} + \frac{{\color{Red}3} \cdot 44}{{\color{Red}3} \cdot 35} = \frac{85}{105} + \frac{132}{105}= \frac{217}{105} = \frac{31}{15}</math><ref>Heinz Griesel und andere: ''Elemente der Mathematik'' Niedersachsen 6. Schuljahr, Schroedel Verlag, Hannover 2005, ISBN 3-507-87206-4, S. 9.</ref>

{{Belege fehlen|Quellenangaben mangels Einzelnachweisen ungenau}}

== Das kgV in Ringen ==
Analog zum ggT ist das kgV in [[Ring (Algebra)|Ringen]] definiert: Ein Ringelement <math>v</math> heißt kleinstes gemeinsames Vielfaches zweier Ringelemente <math>a</math> und <math>b</math>, wenn <math>v</math> ein gemeinsames Vielfaches von <math>a</math> und <math>b</math> ist und seinerseits jedes andere gemeinsame Vielfache von <math>a</math> und <math>b</math> ein Vielfaches von <math>v</math> ist.

Formal schreibt man diese Definition für einen Ring <math>R</math> so:

:<math>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
</math>

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

=== Beispiele ===

==== Das kgV von Polynomen ====
Das kgV lässt sich nicht nur für natürliche (und ganze) Zahlen definieren. Man kann es z. B. auch für [[Polynom]]e bilden. Statt der [[Primfaktorzerlegung]] nimmt man hier die Zerlegung in [[Irreduzibles Polynom|irreduzible]] Faktoren:

:<math>\begin{align}
f(x) &= x^2 + 2xy + y^2 = (x + y)^2\\
g(x) &= x^2 - y^2 = (x + y) (x - y)
\end{align}</math>

Dann ist
:<math>\operatorname{kgV}(f, g) = (x + y)^2 (x - y)</math>.

Die [[Division mit Rest]], die auch für Polynome existiert, erleichtert das Auffinden von gemeinsamen Teilern.

==== Gaußscher Zahlenring ====
Im [[Gaußsche Zahl|gaußschen Zahlenring]] <math>\Z+\mathrm i\Z</math> ist der größte gemeinsame Teiler von <math>2</math> und <math>1 + 3\mathrm i</math> gerade <math>1 + \mathrm i</math>, denn <math>2 = -\mathrm i (1 + \mathrm i)^2</math> und <math>1 + 3\mathrm i = (1 + \mathrm i) (2 + \mathrm i)</math>. Genau genommen ist <math>1 + \mathrm i</math> ''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 ggT oder ein kgV. Wenn sie einen ggT haben, können sie mehrere ggT haben. Ist der Ring ein [[Integritätsring]], dann sind alle ggT zueinander [[Assoziierte Elemente|assoziiert]], in Zeichen <math>\sim</math>.

Ist <math>R</math> ein Integritätsring und haben die Elemente <math>a</math> und <math>b</math> ein kgV, dann haben sie auch einen ggT, und es gilt die Gleichung
:<math>a \cdot b \sim \operatorname{ggT}(a, b) \cdot \operatorname{kgV}(a, b)</math>

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

===== Integritätsring =====
Im Integritätsring <math>R = \mathbb{Z}[\sqrt{-3}]</math> haben die Elemente
:<math>a:= 4 = 2\cdot 2 = (1 + \sqrt{-3})(1 - \sqrt{-3}),\quad b:= (1 + \sqrt{-3})\cdot 2</math>

keinen ggT: Die Elemente <math>1 + \sqrt{-3}</math> und <math>2</math> sind zwei ''maximale gemeinsame Teiler'', denn beide haben den gleichen [[Betragsfunktion#Komplexe Betragsfunktion|Betrag]]. Jedoch sind diese zwei Elemente nicht zueinander assoziiert, also gibt es keinen ggT von <math>a</math> und <math>b</math>.

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

=== Bemerkungen ===
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 [[Faktorieller Ring|faktoriellen Ring]] haben je zwei Elemente einen ggT.

In einem [[Euklidischer Ring|euklidischen Ring]] lässt sich der ggT zweier Elemente mit dem euklidischen Algorithmus bestimmen.

== Weblinks ==
{{Wikibooks|Algorithmensammlung: Zahlentheorie: Euklidischer Algorithmus#Visual Basic for Applications|Algorithmensammlung - Euklidischer Algorithmus und kgV}}
{{Wiktionary|kleinster gemeinsamer Nenner}}
* [http://www.umrechnung.org/mathematik-kgv-ggt-berechnen/gemeinsames-vielfaches-teiler.htm Online-Tool] zur Berechnung des ggT und des kgV von zwei oder drei Zahlen
* [http://www.openwebschool.de/06/ma/ Verschiedene Online-Tools] zur Primfaktorzerlegung, ggT und kgV.
* {{TIBAV |19848 |Linktext=Gemeinsames und kleinstes gemeinsames Vielfaches (kgV) |Herausgeber=PHHD |Jahr=2012 |DOI=10.5446/19848}}

== Einzelnachweise ==
<references />

[[Kategorie:Arithmetik]]
[[Kategorie:Zahlentheorie]]

Kleinstes gemeinsames Vielfaches - Versionsgeschichte

2001:9E8:B567:C200:69B2:5A:C89D:2D77: /* Berechnung über den größten gemeinsamen Teiler (ggT) */ Bei uns unübliches Divisionszeichen ersetzt