Hans Walser, [20100524a]
Zwischen ggT und kgV
In der Schule lernte
man den Satz, dass das Produkt zweier Zahlen gleich dem Produkt ihres grš§ten
gemeinsamen Teilers (ggT) mit ihrem kleinsten gemeinsamen Vielfachen (kgV) ist:
Und dann kam der
erhobene Zeigefinger: Gilt aber nicht fźr drei Zahlen. — Mich hat das als
Schźler irritiert.
Rechnen wir mal mit , und .
Fźr ggT und kgV erhalten wir:
Andererseits ist:
Nun haben wir:
Auf der linken Seite
des Ungleichheitszeichens ăfehltŇ ein Faktor 6. Was hat es damit auf sich?
Wir rechnen paarweise
das kgV und anschlie§end den ggT der drei kgV:
Nun machen wir es
umgekehrt:
Wir kommen bei beiden
Verfahren auf die ăfehlendeŇ Zahl 6.
Wir arbeiten mit der
Primfaktorzerlegung:
Es ist:
Wir tabellieren die
Exponenten; falls eine Primzahl nicht als Primfaktor vorkommt, schreiben wir den Exponenten null.
Nach dem in der Schule
gelernten Verfahren ist:
Bei drei Zahlen gibt es
aber zwischen dem Minimum und dem Maximum noch die Zahl in der Mitte. Die
Statistiker nennen dies den Median. Nun rechnen wir damit:
Dies ist offensichtlich
die ăfehlendeŇ Zahl dazwischen.
Was soll dieses Bild?
Wir arbeiten mit , , und .
Es ist:
Andererseits ist:
Wir haben einen
ăfehlendenŇ Faktor:
Bei vier Zahlen gibt es
sechs mšgliche Paare. Wir rechnen paarweise das kgV:
Anschlie§end berechnen
wir den ggT der sechs kgV:
Nun gehen wir umgekehrt
vor. Wir berechnen zuerst paarweise den ggT:
Fźr das kgV der sechs
ggT ergibt sich:
Wir erhalten zwei
verschiedene Zahlen. Das Produkt der beiden Zahlen ist aber gerade der fehlende
Faktor.
Wir gehen aus von n Zahlen und nehmen deren
Primfaktorzerlegung. Dabei sei m
die Nummer der grš§ten źberhaupt vorkommenden Primzahl.
Wir erhalten die
Exponententablle :
Nun ordnen wir die
Spalten der Exponententabelle der Grš§e nach, die kleinen oben. Die Elemente
der so geordneten Tabelle nennen wir . Es ist also:
Damit definieren wir:
Die erste Zahl, also , enthŠlt jeweils das Minimum der bei einer Primzahl vorkommenden Exponenten. Somit ist .
Entsprechend ist .
Auf Grund des Anordnens der Exponenten der Primfaktoren erhalten wir die Teilerkette .
Da wir in den insgesamt dieselben Primfaktoren haben wie in den , gilt:
Damit ist das
zahlentheoretische Problem meiner Jugend gelšst.
Zur Illustration nochmals
das Beispiel mit den vier Zahlen:
Exponententabelle:
Spalten der Grš§e nach
geordnet:
Das ergibt die Zahlen :
Die Zahlen 6 und 252
erhielten wir oben auch bei den Turnźbungen.
Um von n Zahlen unter
ausschlie§licher Verwendung der beiden Funktionen min (Minimum) und max
(Maximum) zum Beispiel die drittkleinste zu finden, bestimmen wir zunŠchst von
allen Teilmengen mit genau drei Zahlen (es gibt solcher Teilmengen)
je das Maximum und anschlie§end das Minimum dieser Maxima. — Nun ja, das
ist ja wohl nicht die effizienteste Methode des Anordnens, aber lustig ist die
†berlegung allemal. — Allgemein gilt fźr die k-t-kleinste Zahl:
Daraus ergibt sich
sofort:
Analog gilt unter
Vertauschung der Operationen:
Und entsprechend:
Nun verstehen wir auch
die Ergebnisse der Turnźbungen.