7. Der Satz von Legendre
Wir haben gesehen, dass sich die Primzahlexponenten eines Produkts nm zweier natürlicher Zahlen n, m ≥ 1 durch die Addition der entsprechenden Exponenten von n und m ergeben. Allgemeiner gilt für alle natürlichen Zahlen n1, …, nk ≥ 1 und alle Primzahlen p, dass
(+) exp(∏1 ≤ i ≤ k ni) = ∑1 ≤ i ≤ k exp(ni).
Diese vielleicht etwas technisch anmutende Identität lässt sich mit der Anschauung, dass die Primzahlen die Atome der natürlichen Zahlen sind, leicht einsehen: Bei der Produktbildung fügen wir die Zahlen zusammen, sodass sich ihre Atome addieren.
In diesem Essay betrachten wir die Primzahlexponenten spezieller, aber in der Mathematik sehr wichtiger Produkte, nämlich die der Fakultäten
n! = 1 · 2 · … · n.
Es ergibt sich eine überraschend einfache Möglichkeit, die Primfaktorzerlegung einer Fakultät zu berechnen. Der Floor-Funktion kommt dabei eine Schlüsselrolle zu:
Satz (Satz von Legendre)
Seien n ≥ 1 und p prim. Dann gilt
exp(n!) = ⌊np⌋ + ⌊np2⌋ + ⌊np3 ⌋ + …
Die in diesem Satz auftretende Summe ist endlich: Denn ist pk > n, so sind alle Summanden ab der Stelle k gleich 0. Genauer genügt es, bis k = ⌊log(n)/log(p)⌋ zu summieren. Denn dann gilt pk ≤ n und pk + 1 > n.
Beweis
Sei k ≥ 1. Wir erinnern uns, dass ⌊n/pk⌋ die Anzahl der durch pk teilbaren Zahlen des Intervalls { 1, …, n } ist (denn dies sind genau die Vielfachen
pk, 2pk, …, dpk
von pk mit dpk ≤ n und (d + 1)pk > n, d. h. d = ⌊n/pk⌋). Folglich gilt
| ⌊np⌋ + ⌊np2⌋ + … | = ∑k ≥ 1 |{ m | 1 ≤ m ≤ n, pk teilt m }| |
| = |{ (m, k) | k ≥ 1, 1 ≤ m ≤ n, pk teilt m }| | |
| = ∑1 ≤ m ≤ n |{ k | k ≥ 1, pk teilt m }| | |
| = ∑1 ≤ m ≤ n exp(m) | |
| = exp(n!). |
Das Argument lässt sich sehr anschaulich darstellen. Ist m ∈ { 1, …, n } und e = exp(m), so ist m genau durch die Potenzen
p, p2, …, pe
der Primzahl p teilbar. Nach der Formel (+) trägt m genau den Wert exp(m) zum p-Exponenten exp(n!) der Fakultät von n bei. Um den Übergang zur Floor-Summe zu visualisieren, betrachten wir exemplarisch n = 64 und p = 2:
Die Punkte (m, 2e) mit m ∈ { 1, …, 64 } und 2e|m
Der 2-Exponent von n! ist die Anzahl der Punkte dieses Diagramms. In den Spalten gibt es genau
ex2(1), ex2(2), ex2(3), …, ex2(n)
Punkte (ungerade Spalten sind leer). Für die Zeilen verwenden wir die Floor-Funktion zur Zählung: In den Zeilen gibt es, von unten nach oben gelesen, genau
⌊n2⌋, ⌊n22⌋, ⌊n23 ⌋, …, ⌊n26⌋
Punkte. Damit gilt
ex2(n!) = ∑1 ≤ m ≤ n ex2(m) = ∑k ≥ 1 ⌊n2k⌋.
Analoges gilt für jede andere Primzahl p und jedes n ≥ 1: Der p-Exponent von n! ist die Mächtigkeit der Menge
Ap, n = { (m, pe) | 1 ≤ m ≤ n, 1 ≤ e ≤ exp(n) }.
Unser Beweis verwendet ein allgemeines kombinatorischen Prinzip: Eine zweidimensionale Punktmenge lässt sich sowohl spalten- als auch zeilenweise zählen. Damit ist der Beweis des Satzes von Legendre beinahe trivial.
Analog für p = 3 und n = 37 = 729.
Der Satz von Legendre erlaubt es, die Primfaktorzerlegung von n! anzugeben, ohne n! auszurechnen und ohne die Zerlegungen von 2, …, n zu bestimmen. Die Primzahlen bis n müssen natürlich bekannt sein. Für jede Primzahl p ≤ n liefert dann die Berechnung einer einfachen Summe den p-Exponenten von n!
Beispiel
Sei n = 999. Dann berechnen sich der 7- und der 11-Exponent von n! zu
ex7(999!) = ⌊9997⌋ + ⌊99949⌋ + ⌊999343⌋ = 142 + 20 + 2 = 164
ex11(999!) = ⌊99911⌋ + ⌊999121⌋ = 90 + 8 = 98
Der Leser findet vielleicht ein Vergnügen daran, weitere Werte wie
ex2(999!) = 991, ex3(999!) = 498, ex5(999!) = 246
zu berechnen. Der letzte von 1 verschiedene Wert ist
ex499(999!) = 2.
Zum Vergleich: In Dezimaldarstellung hat 999! genau 2565 Stellen.
Eine Zählung mit Hilfe von Geraden
Der Satz von Legendre ergab sich durch den Wechsel zwischen der zeilen- und spaltenweisen Zählung der Punktmenge
A = Ap, n = { (m, pe) | 1 ≤ m ≤ n, 1 ≤ e ≤ exp(n) }.
Ein Blick auf unsere Diagramme suggeriert eine weitere Zählung mit Hilfe von Geraden:
Geradenzerlegung von Ap, n für n = 32 und p = 2 mit Hilfe der Geraden g1, …, g16 mit den Steigungen 1, 1/2, 1/3, …, 1/16.
Um diesen visuellen Eindruck in die Sprache der Mathematik zu übersetzen, beobachten wir: Ist (m, pe) ∈ A, so gibt es ein d ≥ 1 mit m = d pe. Ist gd : ℝ → ℝ die Gerade durch 0 mit der Steigung 1/d, so gilt
gd(m) = m/d = pe.
Damit liegt jeder Punkt von A auf genau einer Geraden gd. Es gilt 1 ≤ d ≤ ⌊n/p⌋, denn m = ⌊n/p⌋ p ist die größte durch p teilbare Zahl kleinergleich n und der Punkt (m, p) liegt auf gd mit d = ⌊n/p⌋.
Ist nun d ∈ { 1, …, ⌊n/p⌋ } fest gewählt, so ist
Gd = Gd, p, n = { (m, pe) ∈ A | m = d pe } = { (m, pe) ∈ A | gd(m) = pe }
die Menge der Punkte der Menge A, die auf der Geraden gd liegen. Die Mengen Gd sind paarweise disjunkt und ihre Vereinigung ist A. Es gilt
| |Gd| | = |{ (m, pe) ∈ A | m = d pe }| |
| = |{ pe | e ≥ 1 und es gibt ein m ≤ n mit m = d pe }| | |
| = |{ e ≥ 1 | d pe ≤ n }| = |{ e ≥ 1 | pe ≤ n/d }|. |
Die reelle Zahl x mit px = n/d ist gegeben durch x = log(n/d)/log(p). Damit ist
|Gd| = ⌊log(n/d)log(p)⌋ = ⌊log(n) − log(d)log(p)⌋.
Die Mächtigkeiten von Gd sind also schwach monoton fallend in d. Es gilt
|G1| = ⌊log(n)log(p)⌋ ≥ … ≥ 1 = |G⌊n/p⌋|.
Damit haben wir gezeigt:
Satz (Geradenzählung der Primfaktoren einer Fakultät)
Seien n ≥ 1 und p prim. Dann gilt mit den obigen Bezeichnungen
exp(n!) = ∑1 ≤ d ≤ n/p |Gd| = ∑1 ≤ d ≤ n/p ⌊log(n/d)log(p)⌋.
In den Summen können wir hier auch „d ≤ n“ schreiben, da die zusätzlichen Summanden gleich 0 sind.
Wir fassen unsere Formeln und die ihnen zugrunde liegenden Zählverfahren noch einmal zusammen:
| exp(n!) | = ∑1 ≤ m ≤ n exp(m) | spaltenweise Summation |
| exp(n!) | = ∑1 ≤ e ≤ n ⌊n/pe⌋ | zeilenweise Summation |
| exp(n!) | = ∑1 ≤ d ≤ n ⌊log(n/d)log(p)⌋ | Geradensummation |
Beispiel
Für n = 32 und p = 2 erhalten wir die drei Summen:
ex2(32!) = 1 + 2 + 1 + 3 + 1 + 2 + 1 + 4 + 1 + 2 + 1 + 3 + 1 + 2 + 1 + 5 = 31
ex2(32!) = 16 + 8 + 4 + 2 + 1 = 31
ex2(32!) = 5 + 4 + 3 + 3 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 31
Abschnitte der Hauptdiagonalen
Die Geradenzählung besitzt noch eine weitere bemerkenswerte Eigenschaft: Mit Hilfe der Hauptdiagonalen können wir alle anderen Mächtigkeiten berechnen. Denn für alle d, p, n gilt
| |Gd, p, n| | = |{ e ≥ 1 | pe ≤ n/d }| |
| = |{ e ≥ 1 | pe ≤ ⌊n/d⌋/1 }| | |
| = |G1, p, ⌊n/p⌋|. |
Die Anzahl der Punkte von Ap, n auf g2 ist also die Anzahl der Punkte von Ap, n auf g1 bis einschließlich der Stelle n/2. Analoges gilt für g3, g4 und die Abschnitte der Hauptdiagonalen bis n/3, n/4, …
Auch diese Eigenschaft können wir visualisieren:
Projektionseigenschaft: Die Punkte auf den Abschnitten der Hauptdiagonalen bis n/2, n/3, … entsprechen den Punkten auf den Geraden g2, g3, …
Auf der gelben Geraden g2 des Diagramms liegen genau vier Punkte. Ebenso liegen genau vier Punkte auf der blauen Hauptdiagonalen g1 bis n/2. Die Punkte auf der gelben Geraden und auf der Hauptdiagonalen links der gestrichelten Linie gehen durch eine Verschiebung parallel zur x-Achse ineinander über. Analoges gilt für die grüne, rote und alle weiteren Geraden des Diagramms.