Kleinstes gemeinsames Vielfaches

In der Mathematik und genauer in der Arithmetik ist das am wenigsten verbreitete Vielfache - abgekürzt PPCM - (kann auch als PPMC oder " kleinstes gemeinsames Vielfaches " bezeichnet werden) von zwei Ganzzahlen ungleich Null a und b die kleinste streng positive Ganzzahl, die ein Vielfaches ist dieser beiden Zahlen. Wir bezeichnen es als a ∨ b oder PPCM ( a , b ) oder manchmal einfach [ a , b ].

Wir können das PPCM von a und b auch als ein gemeinsames Vielfaches von a und b definieren , das alle anderen teilt . Diese zweite Definition verallgemeinert sich auf jeden kommutativen Ring , aber wir verlieren im Allgemeinen Existenz und Einzigartigkeit; Dies wird gemäß einer PPCM von zwei Elementen. Die Existenz ist in integralen Fakultätsringen oder sogar nur in GCD gewährleistet .

Allgemeiner wird das PPCM für eine beliebige Anzahl von Elementen definiert: Das PPCM von n Ganzzahlen ungleich Null ist das kleinste streng positive ganzzahlige Vielfache dieser n Ganzzahlen gleichzeitig.

Definition

Sei a und b zwei relative ganze Zahlen :

wenn a oder b Null ist, ist PPCM ( a , b ) = 0;
Wenn a und b ungleich Null sind, betrachten Sie die Menge streng positiver Ganzzahlen, die ein Vielfaches von a und b sind . Diese Menge natürlicher Ganzzahlen ist nicht leer, da sie | enthält ab |. Es hat daher ein kleineres Element , und es ist diese Ganzzahl (streng positiv), die wir das PPCM von a und b nennen :

{\ displaystyle \ operatorname {PPCM} (a, b) = \ min \ left (\ left \ {m \ in \ mathbb {N} ^ {*} \ mid a | m ~ {\ rm {und}} ~ b | m \ right \} \ right)}

Berechnung

Primfaktorisierung verwenden

Die prime Faktorisierung der PPCM von n streng positiven ganzen Zahlen enthält alle Primzahlen, die in mindestens eine der Hauptfaktoren dieser erscheinen n ganzen Zahlen, die jeweils die größten zugewiesen Exponenten , das erscheint in ihnen . Mit anderen Worten, für jede Primzahl p ,

{\ displaystyle v_ {p} ({\ text {ppcm}} (a, b)) = \ max (v_ {p} (a), v_ {p} (b)),}

wo ist die p-adische Bewertung . $v_p$

Wir erhalten daher eine Methode zur Berechnung des PPCM, indem wir jede Zahl in ein Produkt von Primzahlen zerlegen .

Beispiel

Nehmen wir die Zahlen 60 und 168 und zerlegen sie in Produkte von Primfaktoren. Wir haben :

60 = 2 × 2 × 3 × 5 = 2 2 × 3 × 5;
168 = 2 × 2 × 2 × 3 × 7 = 2 3 × 3 × 7.

Für die Primzahl 2 ist der größte Exponent 3. Für die Primzahlen 3, 5 und 7 ist der größte Exponent 1. Wir haben also PPCM (60, 168) = 2 3 × 3 × 5 × 7 = 840 .

Verwenden der GCD

Sobald eine der beiden ganzen Zahlen a oder b ungleich Null ist, kann ihr kleinstes gemeinsames Vielfaches mit ihrem größten gemeinsamen Teiler (GCD) berechnet werden :

{\ displaystyle \ operatorname {PPCM} (a, b) = {\ dfrac {| ab |} {\ operatorname {PGCD} (a, b)}}}

Alternativ wird die Existenz einer GCD sowie die Formel von der einer PPCM im starken Sinne abgeleitet, das heißt - vgl. erste Eigenschaft unten - eines gemeinsamen Vielfachen, das alle anderen teilt:

Demonstration Methode 1: Definieren Sie die ganzen Zahlen m und d durch: m = PPCM ( a , b ) und d = | ab | / m . So,

\ forall n \ in \ mathbb {Z} \ quad n \ mid a, b \ iff nb, na \ mid ab \ iff n \ mid ab ~ {{\ rm {und}}} ~ b, a \ mid ab / n \ iff n \ mid md ~ {{\ rm {und}}} ~ m \ mid md / n \ iff n \ mid d

daher ist GCD ( a , b ) = d .

Methode 2: Wir bezeichnen die p-adische Bewertung . Verwenden Sie das und wir finden $v_p$ ${\ displaystyle v_ {p} ({\ text {pgcd}} (a, b)) = \ min (v_ {p} (a), v_ {p} (b))}$ ${\ displaystyle v_ {p} ({\ text {ppcm}} (a, b)) = \ max (v_ {p} (a), v_ {p} (b))}$

{\ displaystyle \ forall p \ in {\ mathcal {P}} \ quad v_ {p} ({\ text {pgcd}} (a, b) {\ text {ppcm}} (a, b)) = v_ { p} ({\ text {pgcd}} (a, b)) + v_ {p} ({\ text {ppcm}} (a, b)) = \ min (v_ {p} (a), v_ {p } (b)) + \ max (v_ {p} (a), v_ {p} (b)) = v_ {p} (a) + v_ {p} (b) = v_ {p} (ab)}

daher durch die Einzigartigkeit der Zersetzung in ein Produkt von Primfaktoren .

{\ displaystyle {\ text {pgcd}} (a, b) {\ text {ppcm}} (a, b) = ab}

Somit ermöglicht der Euklid-Algorithmus zur Berechnung der GCD auch die Berechnung der PPCM.

Beispiel Berechnen wir mit dem Euklid-Algorithmus die GCD (60, 168):
168 = 60 × 2 + 48
60 = 48 × 1 + 12
48 = 12 × 4 + 0. Also GCD (60, 168) = 12 und PPCM (60, 168) = (60 × 168) / 12 = 840.

Eigenschaften

Sei $a , b , c$ drei natürliche Zahlen ungleich Null.

Die Vielfachen, die a und b gemeinsam haben, sind die Vielfachen von PPCM ( a , b )
Bestimmtes, $\ operatorname {PPCM} (a, b) = a \ iff b \ mid a$
$\ operatorname {PPCM} (a, b, c) = \ operatorname {PPCM} (\ operatorname {PPCM} (a, b), c) = \ operatorname {PPCM} (a, \ operatorname {PPCM} (b, c) ))$ (Wir können uns auf eine beliebige Anzahl von Elementen erstrecken)
$\ operatorname {PPCM} (ac, bc) = c \ operatorname {PPCM} (a, b)$
$\ operatorname {PGCD} (a, \ operatorname {PPCM} (a, b)) = \ operatorname {PPCM} (a, \ operatorname {PGCD} (a, b)) = a$
$\ operatorname {PGCD} (a, \ operatorname {PPCM} (b, c)) = \ operatorname {PPCM} (\ operatorname {PGCD} (a, b), \ operatorname {PGCD} (a, c))$
$\ operatorname {PPCM} (a, \ operatorname {PGCD} (b, c)) = \ operatorname {PGCD} (\ operatorname {PPCM} (a, b), \ operatorname {PPCM} (a, c))$
${\ displaystyle \ operatorname {PGCD} (\ operatorname {PPCM} (a, b), \ operatorname {PPCM} (b, c), \ operatorname {PPCM} (a, c)) = \ operatorname {PPCM} (\ Operatorname {PGCD} (a, b), \ Operatorname {PGCD} (b, c), \ Operatorname {PGCD} (a, c))}$ .

Anmerkungen und Referenzen

Diese Notation, die allgemeiner für die Obergrenze der Gitter hier verwendet wird, die der Teilbarkeit, wird auch für die logische Disjunktion verwendet .
Die entsprechende Notation für GCD lautet ( a , b ).
Eine Demonstration finden Sie beispielsweise unter " PPCM " in Wikiversity .

Siehe auch

Zum Thema passende Artikel

Externer Link

Online-Tool zur Berechnung des PPCM aus zwei Zahlen