Teilbarkeit und PrimzahlenKleinstes gemeinsames Vielfaches

Auf einer Rundstrecke trainieren zwei Läufer. Der erste Läufer benötigt 60 Sekunden für eine Runde. Der zweite Läufer benötigt nur 40 Sekunden für eine Runde. Wenn beide gleichzeitig von der Startlinie losstarten, wann werden sie sich am Start wieder treffen?

Bei dieser Frage geht es in Wirklichkeit nicht um die Geometrie der Rennstrecke oder um Geschwindigkeit und Schnelligkeit - es geht um Vielfache und Teilbarkeit.

Der erste Läufer überquert die Startlinie nach 60s, 120s, 180s, 240s usw. Dies sind einfach die VielfachenTeiler von 60. Der zweite Läufer überquert die Startlinie nach 40s, 80s, 120s, 160s und so weiter. Das erste Mal, dass beide Läufer wieder an der Startlinie sind, ist nach Sekunden.

Was wir gerade gefunden haben, ist die kleinste Zahl , die sowohl ein Vielfaches von 40 als auch ein Vielfaches von 60 ist, was als das kleinste gemeinsame Vielfache oder kgV bezeichnet wird.

Um das kgV von zwei beliebigen Zahlen zu finden, ist es wichtig zu erkennen, dass, wenn b durch a teilbar ist, b alle Primfaktoren von a (und dann noch einige zusätzlich) beinhalten muss:

Das ist leicht zu überprüfen: Wenn ein Primfaktor a teilt und a wiederum b teilt, dann muss dieser Primfaktor auch b teilen.

Um den kgV von 40 und 60 zu finden, müssen wir zuerst die Primfaktorzerlegung von beiden finden:

Angenommen, X ist das kgV von 40 und 60. 40 teilt dann X, also müssen 2, 2, 2 und 5 Primfaktoren von X sein. Außerdem teilt 60 X, weshalb 2, 2, 3 und 5 Primfaktoren von X sein müssen.

Um X zu finden, kombinieren wir einfach alle Primfaktoren von 40 und 60, aber alle Duplikate benötigen wir nur einmal:

X  =  2 × 2 × 2 × 3 × 5

Das ergibt X = 120, genau wie wir es oben gesehen haben. Beachte, dass, wenn der gleiche Primfaktor mehrfach vorkommt, wie oben 2, wir die maximalen Vorkommen in einer der beiden Zahlen behalten müssen (3 mal in 40 ist mehr als 2 mal in 60).

Jetzt haben wir eine einfache Methode, um das kgV von zwei Zahlen zu finden:

1. Mache die Primfaktorzerlegung für jede Zahl.
2. Fasse die Primfaktoren zusammen, nimm aber jeden doppelt vorkommenden Wert nur einmal.

Wir können die gleiche Methode verwenden, um das kgV von drei oder mehr Zahlen auf einmal zu finden, zB von 12, 30 und 45:

Jetzt ist das kgV von 12, 30 und 45 gleich 2 × × 3 × 3 × = 180.

Ein Sonderfall sind Primzahlen: Das kgV von zwei verschiedenen Primzahlen ist einfach ihr Produktihre Summeihre Differenz, da sie keine gemeinsamen Primfaktoren haben, die “gestrichen” werden würden.

Zikaden

Sowohl 13 als auch 17 sind Primzahlen - und das hat einen sehr guten Grund. Stell dir vor, es gibt Raubtiere im Wald, die Zikaden töten. Diese Raubtiere treten auch in regelmäßigen Abständen auf, zB alle 6 Jahre.

Stell dir nun vor, dass die Zikaden alle ${n} Jahre ausbrüten würden (${isPrime(n) ? 'Primzahl' : 'keine Primzahl'}). Die beiden Tiere würden alle ${lcm(n,6)} Jahre, was dem kgVggTProdukt von 6 und ${n} entspricht, aufeinandertreffen.

Diese Zahl scheint viel größer zu sein, wenn der Zikadenzyklus eine Primzahl wie 13 und 17 ist. Das liegt daran, dass Primzahlen keine Teiler mit 6 gemeinsam haben, so dass wir bei der Berechnung des kgV keine doppelten Teiler zu löschen haben.

Natürlich haben die Zikaden keine Ahnung, was Primzahlen sind - aber in Millionen von Jahren hat die Evolution herausgefunden, dass Primzahlen für sie am sichersten sind. Das Raubtier scheint im Laufe der Zeit ausgestorben zu sein, aber die Primzahlzyklen wurden beibehalten.