Kleinstes gemeinsames Vielfaches - Least common multiple

Ein Venn-Diagramm, das die kleinsten gemeinsamen Vielfachen von Kombinationen von 2, 3, 4, 5 und 7 zeigt (6 wird übersprungen, da es 2 × 3 ist, die beide bereits dargestellt sind).
Zum Beispiel erfordert ein Kartenspiel, bei dem die Karten gleichmäßig auf bis zu 5 Spieler aufgeteilt werden müssen, mindestens 60 Karten, die Zahl am Schnittpunkt der 2er, 3er, 4er und 5er Sätze, aber nicht die 7er.

In der Arithmetik und Zahlentheorie ist das kleinste gemeinsame Vielfache , das kleinste gemeinsame Vielfache oder das kleinste gemeinsame Vielfache von zwei ganzen Zahlen a und b , normalerweise bezeichnet mit lcm( a ,  b ) , die kleinste positive ganze Zahl, die durch a und b teilbar ist . Da die Division von ganzen Zahlen durch Null nicht definiert ist, hat diese Definition nur dann Bedeutung, wenn a und b von Null verschieden sind. Jedoch definieren einige Autoren LCM ( eine , 0) als 0 für alle a , die das Ergebnis des Nehmens des LCM ist zu sein dest Obergrenze im Gitter der Teilbarkeit.

Der lcm ist der „ kleinste gemeinsame Nenner “ (lcd), der verwendet werden kann, bevor Brüche addiert, subtrahiert oder verglichen werden können. Der lcm von mehr als zwei ganzen Zahlen ist ebenfalls wohldefiniert: Es ist die kleinste positive ganze Zahl, die durch jede von ihnen teilbar ist.

Überblick

Ein Vielfaches einer Zahl ist das Produkt dieser Zahl und einer ganzen Zahl. Zum Beispiel ist 10 ein Vielfaches von 5, weil 5 × 2 = 10, also ist 10 durch 5 und 2 teilbar. Da 10 die kleinste positive ganze Zahl ist, die sowohl durch 5 als auch durch 2 teilbar ist, ist es das kleinste gemeinsame Vielfache von 5 und 2. Nach dem gleichen Prinzip ist 10 auch das kleinste gemeinsame Vielfache von −5 und −2.

Notation

Das kleinste gemeinsame Vielfache von zwei ganzen Zahlen a und b wird als lcm( a , b ) bezeichnet. Einige ältere Lehrbücher verwenden [ a , b ], während die Programmiersprache J verwendet a*.b.

Beispiel

${\displaystyle \operatorname {lcm} (4,6)}$

Vielfache von 4 sind:

${\displaystyle 4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,...}$

Vielfache von 6 sind:

${\displaystyle 6,12,18,24,30,36,42,48,54,60,66,72,...}$

Gemeinsame Vielfache von 4 und 6 sind die Zahlen, die in beiden Listen enthalten sind:

${\displaystyle 12,24,36,48,60,72,...}$

In dieser Liste ist die kleinste Zahl 12. Das kleinste gemeinsame Vielfache ist also 12.

Anwendungen

Beim Addieren, Subtrahieren oder Vergleichen einfacher Brüche wird das kleinste gemeinsame Vielfache der Nenner (oft auch kleinster gemeinsamer Nenner genannt ) verwendet, da jeder der Brüche mit diesem Nenner als Bruch ausgedrückt werden kann. Zum Beispiel,

${\displaystyle {2 \over 21}+{1 \over 6}={4 \over 42}+{7 \over 42}={11 \over 42}}$

wobei der Nenner 42 verwendet wurde, da er das kleinste gemeinsame Vielfache von 21 und 6 ist.

Getriebeproblem

Angenommen, es gibt zwei kämmende Zahnräder in einer Maschine mit m bzw. n Zähnen, und die Zahnräder sind durch ein Liniensegment gekennzeichnet, das von der Mitte des ersten Zahnrads zur Mitte des zweiten Zahnrads gezogen wird. Wenn sich die Zahnräder zu drehen beginnen, kann die Anzahl der Umdrehungen, die das erste Zahnrad ausführen muss, um das Liniensegment neu auszurichten, mit berechnet werden . Das erste Zahnrad muss für die Neuausrichtung Umdrehungen vollziehen. Zu diesem Zeitpunkt hat sich das zweite Zahnrad gedreht . ${\displaystyle \operatorname {lcm} (m,n)}$${\displaystyle \operatorname {lcm} (m,n) \over m}$${\displaystyle \operatorname {lcm} (m,n) \over n}$

Planetenausrichtung

Angenommen , es gibt revolvierenden drei Planeten einen Stern um die nehmen l , m und n Zeiteinheiten, die jeweils mit ihren Umlaufbahnen zu vervollständigen. Angenommen, l , m und n sind ganze Zahlen. Angenommen, die Planeten beginnen sich nach einer anfänglichen linearen Ausrichtung um den Stern zu bewegen, erreichen alle Planeten nach Zeiteinheiten wieder eine lineare Ausrichtung . Zu diesem Zeitpunkt wird die erste, zweite und dritte Planet abgeschlossen , und Bahnen jeweils um den Stern. ${\displaystyle \operatorname {lcm} (l,m,n)}$${\displaystyle \operatorname {lcm} (l,m,n) \over l}$${\displaystyle \operatorname {lcm} (l,m,n) \over m}$${\displaystyle \operatorname {lcm} (l,m,n) \over n}$

Berechnung

Den größten gemeinsamen Teiler verwenden

Die folgende Formel reduziert das Problem der Berechnung des kleinsten gemeinsamen Vielfachen auf das Problem der Berechnung des größten gemeinsamen Teilers (gcd), auch bekannt als größter gemeinsamer Faktor:

${\displaystyle \operatorname {lcm} (a,b)={\frac {|ab|}{\gcd(a,b)}}.}$

Diese Formel ist auch gültig, wenn genau eines von a und b 0 ist, da gcd( a , 0) = | ein |. Wenn jedoch sowohl a als auch b 0 sind, würde diese Formel eine Division durch Null verursachen ; lcm(0, 0) = 0 ist ein Sonderfall.

Es gibt schnelle Algorithmen zur Berechnung des ggT , die werden nicht die Zahlen erfordern , berücksichtigt , wie der euklidische Algorithmus . Um zum obigen Beispiel zurückzukehren,

${\displaystyle \operatorname {lcm} (21,6)={21\cdot 6 \over \gcd(21,6)}={21\cdot 6 \over \gcd(3,6)}={21\cdot 6 \over 3}={\frac {126}{3}}=42.}$

Da gcd( a , b ) ein Teiler von a und b ist , ist es effizienter, den lcm durch Division vor der Multiplikation zu berechnen :

${\displaystyle \operatorname {lcm} (a,b)=\left({|a| \over \gcd(a,b)}\right)\cdot |b|=\left({|b| \over\ gcd(a,b)}\right)\cdot |a|.}$

Dies verringert die Größe einer Eingabe sowohl für die Division als auch für die Multiplikation und verringert den erforderlichen Speicherbedarf für Zwischenergebnisse (d. h. Überlauf bei der a × b- Berechnung). Da gcd( a , b ) ein Teiler von a und b ist , ergibt die Division garantiert eine ganze Zahl, sodass das Zwischenergebnis in einer ganzen Zahl gespeichert werden kann. Auf diese Weise implementiert, wird das vorherige Beispiel zu:

${\displaystyle \operatorname {lcm} (21,6)={21 \over \gcd(21,6)}\cdot 6={21 \over \gcd(3,6)}\cdot 6={21 \over 3}\cdot 6=7\cdot 6=42.}$

Primfaktorzerlegung verwenden

Der Eindeutige Faktorisierungssatz besagt , dass jede positive ganze Zahl größer als 1 nur auf eine Weise als Produkt von Primzahlen geschrieben werden kann . Die Primzahlen können als die atomaren Elemente betrachtet werden, die zusammen eine zusammengesetzte Zahl bilden .

Zum Beispiel:

${\displaystyle 90=2^{1}\cdot 3^{2}\cdot 5^{1}=2\cdot 3\cdot 3\cdot 5.}$

Die zusammengesetzte Zahl 90 besteht hier aus einem Atom der Primzahl 2, zwei Atomen der Primzahl 3 und einem Atom der Primzahl 5.

Diese Tatsache kann verwendet werden, um den lcm einer Reihe von Zahlen zu ermitteln.

Beispiel: lcm(8,9,21)

Faktorisiere jede Zahl und drücke sie als Produkt von Potenzen der Primzahlen aus .

${\displaystyle {\begin{aligned}8&=2^{3}\\9&=3^{2}\\21&=3^{1}\cdot 7^{1}\end{aligned}}}$

Der lcm ist das Produkt der Multiplikation der höchsten Potenz jeder Primzahl zusammen. Die höchste Potenz der drei Primzahlen 2, 3 und 7 ist 2 ³ , 3 ² bzw. 7 ¹ . Daher,

${\displaystyle \operatorname {lcm} (8,9,21)=2^{3}\cdot 3^{2}\cdot 7^{1}=8\cdot 9\cdot 7=504.}$

Diese Methode ist nicht so effizient wie die Reduktion auf den größten gemeinsamen Teiler, da kein allgemeiner effizienter Algorithmus für die ganzzahlige Faktorisierung bekannt ist .

Die gleiche Methode kann auch mit einem Venn-Diagramm wie folgt veranschaulicht werden, wobei die Primfaktorzerlegung jeder der beiden Zahlen in jedem Kreis gezeigt wird und alle Faktoren, die sie im Schnitt teilen, gemeinsam sind. Der lcm kann dann durch Multiplikation aller Primzahlen im Diagramm ermittelt werden.

Hier ist ein Beispiel:

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5,

teilen sich zwei „2“ und eine „3“ gemeinsam:

Kleinstes gemeinsames Vielfaches = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

Größter gemeinsamer Teiler = 2 × 2 × 3 = 12

Dies funktioniert auch für den größten gemeinsamen Teiler (gcd), außer dass man, anstatt alle Zahlen im Venn-Diagramm zu multiplizieren, nur die Primfaktoren multipliziert, die sich im Schnittpunkt befinden. Somit ist die gcd von 48 und 180 2 × 2 × 3 = 12.

Mit einem einfachen Algorithmus

Diese Methode funktioniert leicht, um den lcm von mehreren ganzen Zahlen zu finden.

Es gebe eine endliche Folge von positiven ganzen Zahlen X = ( x ₁ , x ₂ , ..., x _n ), n > 1. Der Algorithmus geht in Schritten wie folgt vor: Auf jedem Schritt m untersucht und aktualisiert er die Folge X ^{( m )} = ( x ₁ ^{( m )} , x ₂ ^{( m )} , ..., x _n ^{( m )} ), X ⁽¹⁾ = X , wobei X ^{( m )} die m- te Iteration von X ist , d. X im Schritt m des Algorithmus usw. Der Zweck der Untersuchung besteht darin, das kleinste (vielleicht eines von vielen) Element der Folge X ^{( m )} auszuwählen . Angenommen, x _{k 0} ^{( m )} ist das ausgewählte Element, die Folge X ^{( m +1)} ist definiert als

x _k ^{( m + 1)} = x _k ^{( m )} , k ≠ k ₀

x _{k 0} ^{( m + 1)} = x _{k 0} ^{( m )} + x _{k 0} ⁽¹⁾ .

Mit anderen Worten, das kleinste Element wird um das entsprechende x erhöht, während der Rest der Elemente unverändert von X ^{( m )} nach X ^{( m +1)} übergeht.

Der Algorithmus stoppt, wenn alle Elemente in der Sequenz X ^{( m )} gleich sind. Ihr gemeinsamer Wert L ist genau lcm( X ).

Wenn beispielsweise X = X ⁽¹⁾ = (3, 4, 6) ist, erzeugen die Schritte im Algorithmus:

X ⁽²⁾ = (6, 4, 6)

X ⁽³⁾ = (6, 8, 6)

X ⁽⁴⁾ = (6, 8, 12) - durch Auswahl der zweiten 6

X ⁽⁵⁾ = (9, 8, 12)

X ⁽⁶⁾ = (9, 12, 12)

X ⁽⁷⁾ = (12, 12, 12) also lcm = 12.

Mit der Tabellenmethode

Diese Methode funktioniert für eine beliebige Anzahl von Zahlen. Man beginnt damit, alle Zahlen vertikal in einer Tabelle aufzulisten (in diesem Beispiel 4, 7, 12, 21 und 42):

Der Vorgang beginnt damit, dass alle Zahlen durch 2 geteilt werden. Wenn 2 eine von ihnen gleichmäßig teilt, schreibe 2 in eine neue Spalte oben in der Tabelle und das Ergebnis der Division durch 2 jeder Zahl in das Feld rechts davon in diese neue Spalte. Wenn eine Zahl nicht gleichmäßig teilbar ist, schreiben Sie die Zahl einfach neu. Wenn sich 2 nicht gleichmäßig in eine der Zahlen teilt, wiederholen Sie diesen Vorgang mit der nächstgrößeren Primzahl 3 (siehe unten).

Angenommen, 2 hat mindestens eine Zahl geteilt (wie in diesem Beispiel), überprüfen Sie, ob 2 erneut dividiert:

Sobald 2 keine Zahl in der aktuellen Spalte mehr teilt, wiederholen Sie den Vorgang, indem Sie durch die nächst größere Primzahl dividieren, 3. Sobald 3 nicht mehr dividiert, versuchen Sie es mit den nächstgrößeren Primzahlen, 5 dann 7, usw. Der Vorgang endet, wenn alle Zahlen wurden auf 1 reduziert (die Spalte unter dem letzten Primteiler besteht nur aus Einsen).

Multiplizieren Sie nun die Zahlen in der oberen Reihe, um den lcm zu erhalten. In diesem Fall ist es 2 × 2 × 3 × 7 = 84 .

Als allgemeiner Rechenalgorithmus ist das Obige ziemlich ineffizient. In Software würde man es nie umsetzen wollen: Es braucht zu viele Schritte und benötigt zu viel Speicherplatz. Ein weitaus effizienterer numerischer Algorithmus kann erhalten werden, indem der Algorithmus von Euklid verwendet wird , um zuerst die gcd zu berechnen und dann die lcm durch Division zu erhalten.

Formeln

Grundsatz der Arithmetik

Nach dem Fundamentalsatz der Arithmetik ist eine positive ganze Zahl das Produkt von Primzahlen , und diese Darstellung ist bis auf die Ordnung der Primzahlen eindeutig:

${\displaystyle n=2^{n_{2}}3^{n_{3}}5^{n_{5}}7^{n_{7}}\cdots =\prod_{p}p^{n_ {P}},}$

wobei die Exponenten n ₂ , n ₃ , ... nicht negative ganze Zahlen sind; zum Beispiel 84 = 2 ² 3 ¹ 5 ⁰ 7 ¹ 11 ⁰ 13 ⁰ ...

Gegeben zwei positive ganze Zahlen und sind ihr kleinstes gemeinsames Vielfaches und ihr größter gemeinsamer Teiler durch die Formeln ${\textstyle a=\prod_{p}p^{a_{p}}}$${\textstyle b=\prod_{p}p^{b_{p}}}$

${\displaystyle \gcd(a,b)=\prod_{p}p^{\min(a_{p},b_{p})}}$

und

${\displaystyle \operatorname {lcm} (a,b)=\prod_{p}p^{\max(a_{p},b_{p})}.}$

Schon seit

${\displaystyle \min(x,y)+\max(x,y)=x+y,}$

das gibt

${\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=ab.}$

Tatsächlich kann jede rationale Zahl eindeutig als Produkt von Primzahlen geschrieben werden, wenn negative Exponenten zulässig sind. Dabei bleiben die obigen Formeln gültig. Zum Beispiel:

${\displaystyle {\begin{aligned}4&=2^{2}3^{0},&6&=2^{1}3^{1},&\gcd(4,6)&=2^{1} 3^{0}=2,&\operatorname {lcm} (4,6)&=2^{2}3^{1}=12.\\[8pt]{\tfrac {1}{3}}& =2^{0}3^{-1}5^{0},&{\tfrac {2}{5}}&=2^{1}3^{0}5^{-1},&\ gcd \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{0}3^{-1}5^{-1}={\ tfrac {1}{15}},&\operatorname {lcm} \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{1}3 ^{0}5^{0}=2,\\[8pt]{\tfrac {1}{6}}&=2^{-1}3^{-1},&{\tfrac {3}{ 4}}&=2^{-2}3^{1},&\gcd\left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2 ^{-2}3^{-1}={\tfrac {1}{12}},&\operatorname {lcm} \left({\tfrac {1}{6}},{\tfrac {3}{ 4}}\right)&=2^{-1}3^{1}={\tfrac {3}{2}}.\end{aligned}}}$

Gittertheorie

Die positive ganze Zahlen sein können teilweise geordnet durch Teilbarkeit: wenn ein dividieren b (das heißt, wenn b ein ganzzahliges Vielfaches von a ) Schreiben eines ≤ b (oder äquivalent, b ≥ a ). (Beachten Sie, dass die übliche größenbasierte Definition von ≤ hier nicht verwendet wird.)

Unter dieser Ordnung werden die positiven ganzen Zahlen zu einem Gitter , wobei meet durch die gcd und Join durch die lcm gegeben wird. Der Beweis ist einfach, wenn auch etwas mühsam; es läuft darauf hinaus, zu überprüfen, ob lcm und gcd die Axiome für meet and join erfüllen. Wenn man lcm und gcd in diesen allgemeineren Kontext einfügt, entsteht eine Dualität zwischen ihnen:

Wenn eine Formel mit ganzzahligen Variablen gcd, lcm, ≤ und ≥ wahr ist, dann ist auch die Formel wahr, die durch Vertauschen von gcd mit lcm und Vertauschen von mit ≤ erhalten wird. (Denken Sie daran, dass ≤ als Divisionen definiert ist).

Die folgenden Paare dualer Formeln sind Spezialfälle allgemeiner gittertheoretischer Identitäten.

Es kann auch gezeigt werden, dass dieses Gitter distributiv ist ; das heißt, lcm verteilt über gcd und gcd verteilt über lcm:

${\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c)),}$

${\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c)).}$

Diese Identität ist selbst-dual:

${\displaystyle \gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (b,c),\operatorname {lcm} (a,c))=\operatorname {lcm} (\gcd(a ,b),\gcd(b,c),\gcd(a,c)).}$

Sonstiges

• Sei D das Produkt von ω ( D ) verschiedenen Primzahlen ( dh D ist quadratfrei ).

Dann

${\displaystyle |\{(x,y)\;:\;\operatorname {lcm} (x,y)=D\}|=3^{\omega (D)},}$

wobei die absoluten Balken || bezeichnet die Kardinalität einer Menge.

• Wenn keines von Null ist, dann${\displaystyle a_{1},a_{2},\ldots ,a_{r}}$

${\displaystyle \operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2}, \ldots ,a_{r-1}),a_{r}).}$

In kommutativen Ringen

Das kleinste gemeinsame Vielfache lässt sich allgemein über kommutativen Ringen wie folgt definieren: Seien a und b Elemente eines kommutativen Rings R . Eine gemeinsame Vielfache von a und b ist ein Element , m von R , so dass sowohl a und b divide m (das heißt, es existiert Elemente x und y von R , so dass ax = m und durch = m ). Eine kleinste gemeinsame Vielfache von a und b ist ein gemeinsames Vielfaches, der minimal ist, in dem Sinne , dass für alle anderen gemeinsamen Vielfachen n von a und b , m dividieren  n .

Im Allgemeinen können zwei Elemente in einem kommutativen Ring kein kleinstes gemeinsames Vielfaches oder mehr als eins haben. Jedoch sind zwei beliebige kleinste gemeinsame Vielfache desselben Paars von Elementen assoziiert . In einer eindeutigen Faktorisierungsdomäne haben zwei beliebige Elemente ein kleinstes gemeinsames Vielfaches. In einem Hauptidealbereich kann das kleinste gemeinsame Vielfache von a und b als Generator der Schnittmenge der von a und b erzeugten Ideale charakterisiert werden (der Schnittpunkt einer Sammlung von Idealen ist immer ein Ideal).

Siehe auch

• Abnormale Stornierung
• Koprime ganze Zahlen
• Chebyshev-Funktion

Anmerkungen

Verweise

• Crandall, Richard; Pomerance, Carl (2001), Primzahlen: Eine rechnerische Perspektive , New York: Springer , ISBN 0-387-94777-9
• Hardy, GH; Wright, EM (1979), An Introduction to the Theory of Numbers (Fünfte Auflage) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Landau, Edmund (1966), Elementare Zahlentheorie , New York: Chelsea
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2. Aufl.), Lexington: DC Heath and Company , LCCN  77-171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elemente der Zahlentheorie , Englewood Cliffs: Prentice Hall , LCCN  77-81766