Das kleinste gemeinsame Vielfache (kgV) ist ein mathematischer Begriff. Sein Pendant ist der größte gemeinsame Teiler (ggT). Beide spielen unter anderem in der Arithmetik und der Zahlentheorie eine Rolle.
Das kleinste gemeinsame Vielfache zweier ganzer Zahlen
m
{\displaystyle m}
und
n
{\displaystyle n}
ist die kleinste positive natürliche Zahl, die sowohl Vielfaches von
m
{\displaystyle m}
als auch Vielfaches von
n
{\displaystyle n}
ist.[1] Zusätzlich wird für den Fall
m
=
0
{\displaystyle m=0}
oder
n
=
0
{\displaystyle n=0}
das kgV definiert als
kgV
(
m
,
n
)
:=
0
{\displaystyle \operatorname {kgV} (m,\,n):=0}
.[2] Die englische Bezeichnung für das kleinste gemeinsame Vielfache ist least common multiple, oder kurz lcm und findet in mathematischen Texten ebenfalls Verwendung.[3] ggT und kgV kann man über die Primfaktorzerlegung der beiden gegebenen Zahlen bestimmen. Beispiel:
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:
Es gilt die folgende Gleichung:
Sind beide Zahlen positiv oder negativ, so entfallen die Betragsstriche. Damit lässt sich das kgV berechnen, falls der ggT z. B. mit dem 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:
Beispiel: Der ggT von 18 und 24 ist 6. Zur Berechnung des ggT mittels euklidischem Algorithmus siehe den Artikel zum ggT. Das kgV ist folglich (da beide Zahlen positiv sind, entfällt der Betrag)
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. Sei k = kgV ( m , n ) {\displaystyle k=\operatorname {kgV} (m,n)} , dann ist k {\displaystyle k} auch Teiler des Produkts m ⋅ n {\displaystyle m\cdot n} . Die Zahl g {\displaystyle g} enthalte dagegen alle Primfaktoren des Produkts m ⋅ n {\displaystyle m\cdot n} , die k {\displaystyle k} nicht enthält. Betrachtet man, wie der ggT ( m , n ) {\displaystyle \operatorname {ggT} (m,n)} aus der Primfaktordarstellung des Produkts aus m {\displaystyle m} und n {\displaystyle n} berechnet wird, dann folgt g = ggT ( m , n ) {\displaystyle g=\operatorname {ggT} (m,n)} . Daraus ergibt sich die obige Gleichung.[7] Man verwendet alle Primfaktoren, die in mindestens einer der Zahlen vorkommen, mit der jeweils höchsten vorkommenden Potenz, zum Beispiel: 144 = 2 4 ⋅ 3 2 {\displaystyle 144=2^{\color {Red}4}\cdot 3^{\color {Red}2}} 160 = 2 5 ⋅ 5 1 {\displaystyle 160=2^{\color {OliveGreen}5}\cdot 5^{\color {OliveGreen}1}} 175 = 5 2 ⋅ 7 1 , {\displaystyle 175=5^{\color {Blue}2}\cdot 7^{\color {Blue}1},}also: kgV ( 144 , 160 , 175 ) = 2 5 ⋅ 3 2 ⋅ 5 2 ⋅ 7 1 = 50.400. {\displaystyle \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.}Man könnte auch zunächst kgV ( 144 , 160 ) = 1440 {\displaystyle \operatorname {kgV} (144,160)=1440} berechnen und danach kgV ( 1440 , 175 ) = 50.400 , {\displaystyle \operatorname {kgV} (1440,175)=50.400,} denn als eine zweistellige Verknüpfung auf den ganzen Zahlen ist das kgV assoziativ: kgV ( m , kgV ( n , p ) ) = kgV ( kgV ( m , n ) , p ) . {\displaystyle \operatorname {kgV} (m,\operatorname {kgV} (n,p))=\operatorname {kgV} (\operatorname {kgV} (m,n),\,p).}Dies rechtfertigt die Schreibweise kgV ( m , n , p ) {\displaystyle \operatorname {kgV} (m,n,p)} .[8] Angenommen, man möchte die Brüche 17 21 {\displaystyle {\tfrac {17}{21}}} und 44 35 {\displaystyle {\tfrac {44}{35}}} addieren. Dazu müssen diese durch Erweitern auf einen gemeinsamen Nenner gebracht werden. Man könnte 21 {\displaystyle 21} mit 35 {\displaystyle 35} multiplizieren, was 735 {\displaystyle 735} ergibt. Der kleinstmögliche gemeinsame Nenner (der sog. Hauptnenner) ist aber kgV ( 21 , 35 ) = 105 {\displaystyle \operatorname {kgV} (21,35)=105} .[9] Die beiden Brüche werden auf diesen Nenner erweitert und dann addiert. Das Ergebnis wird gekürzt: 17 21 + 44 35 = 5 ⋅ 17 5 ⋅ 21 + 3 ⋅ 44 3 ⋅ 35 = 85 105 + 132 105 = 217 105 = 31 15 {\displaystyle {\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}}} [10]
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Quellenangaben mangels Einzelnachweisen ungenau Analog zum ggT ist das kgV in Ringen definiert: Ein Ringelement v {\displaystyle v} heißt kleinstes gemeinsames Vielfaches zweier Ringelemente a {\displaystyle a} und b {\displaystyle b} , wenn v {\displaystyle v} ein gemeinsames Vielfaches von a {\displaystyle a} und b {\displaystyle b} ist und seinerseits jedes andere gemeinsame Vielfache von a {\displaystyle a} und b {\displaystyle b} ein Vielfaches von v {\displaystyle v} ist. Formal schreibt man diese Definition für einen Ring R {\displaystyle R} so: v = kgV ( a , b ) :⟺ a ∣ v , b ∣ v , ∀ e ∈ R : ( a ∣ e , b ∣ e ) ⇒ v ∣ e {\displaystyle 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}Diese allgemeinere Definition lässt sich auf mehrere Zahlen ausweiten (sogar auf unendlich viele). BeispieleDas kgV von PolynomenDas kgV lässt sich nicht nur für natürliche (und ganze) Zahlen definieren. Man kann es z. B. auch für Polynome bilden. Statt der Primfaktorzerlegung nimmt man hier die Zerlegung in irreduzible Faktoren: f ( x ) = x 2 + 2 x y + y 2 = ( x + y ) 2 g ( x ) = x 2 − y 2 = ( x + y ) ( x − y ) {\displaystyle {\begin{aligned}f(x)&=x^{2}+2xy+y^{2}=(x+y)^{2}\\g(x)&=x^{2}-y^{2}=(x+y)(x-y)\end{aligned}}}Dann ist Die Division mit Rest, die auch für Polynome existiert, erleichtert das Auffinden von gemeinsamen Teilern. Gaußscher ZahlenringIm gaußschen Zahlenring Z + i Z {\displaystyle \mathbb {Z} +\mathrm {i} \mathbb {Z} } ist der größte gemeinsame Teiler von 2 {\displaystyle 2} und 1 + 3 i {\displaystyle 1+3\mathrm {i} } gerade 1 + i {\displaystyle 1+\mathrm {i} } , denn 2 = − i ( 1 + i ) 2 {\displaystyle 2=-\mathrm {i} (1+\mathrm {i} )^{2}} und 1 + 3 i = ( 1 + i ) ( 2 + i ) {\displaystyle 1+3\mathrm {i} =(1+\mathrm {i} )(2+\mathrm {i} )} . Genau genommen ist 1 + i {\displaystyle 1+\mathrm {i} } 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 assoziiert, in Zeichen ∼ {\displaystyle \sim } . Ist R {\displaystyle R} ein Integritätsring und haben die Elemente a {\displaystyle a} und b {\displaystyle b} ein kgV, dann haben sie auch einen ggT, und es gilt die Gleichung a ⋅ b ∼ ggT ( a , b ) ⋅ kgV ( a , b ) {\displaystyle a\cdot b\sim \operatorname {ggT} (a,b)\cdot \operatorname {kgV} (a,b)}Ist jedoch nur bekannt, dass ein ggT von a {\displaystyle a} und b {\displaystyle b} existiert, dann muss nicht unbedingt auch ein kgV existieren. IntegritätsringIm Integritätsring R = Z [ − 3 ] {\displaystyle R=\mathbb {Z} [{\sqrt {-3}}]} haben die Elemente a := 4 = 2 ⋅ 2 = ( 1 + − 3 ) ( 1 − − 3 ) , b := ( 1 + − 3 ) ⋅ 2 {\displaystyle a:=4=2\cdot 2=(1+{\sqrt {-3}})(1-{\sqrt {-3}}),\quad b:=(1+{\sqrt {-3}})\cdot 2}keinen ggT: Die Elemente 1 + − 3 {\displaystyle 1+{\sqrt {-3}}} und 2 {\displaystyle 2} sind zwei maximale gemeinsame Teiler, denn beide haben den gleichen Betrag. Jedoch sind diese zwei Elemente nicht zueinander assoziiert, also gibt es keinen ggT von a {\displaystyle a} und b {\displaystyle b} . Die genannten Elemente 1 + − 3 {\displaystyle 1+{\sqrt {-3}}} und 2 {\displaystyle 2} haben aber ihrerseits einen ggT, nämlich 1 {\displaystyle 1} . Dagegen haben sie kein kgV, denn wenn v {\displaystyle v} ein kgV wäre, dann folgt aus der „ggT-kgV-Gleichung“, dass v {\displaystyle v} assoziiert zu k := ( 1 + − 3 ) ⋅ 2 {\displaystyle k:=(1+{\sqrt {-3}})\cdot 2} sein muss. Das gemeinsame Vielfache 4 {\displaystyle 4} ist jedoch kein Vielfaches von k {\displaystyle k} , also ist k {\displaystyle k} kein kgV und die beiden Elemente haben gar kein kgV. BemerkungenEin 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. Wikibooks: Algorithmensammlung - Euklidischer Algorithmus und kgV – Lern- und Lehrmaterialien
|