7. Ein Beweis mit Hilfe der Möbius-Funktion
Unsere Untersuchung des Siebs des Eratosthenes hat die folgende Summen-Darstellung einer natürlichen Zahl ergeben:
Satz (Einschluss-Ausschluss-Darstellung einer Zahl)
Sei n ≥ 1. Dann gilt
n = 1 + ∑p1 < … < pk ≤ n (−1)k − 1 ⌊np1 … pk⌋.
Äquivalent mit Hilfe der Möbius-Funktion formuliert:
Satz (Darstellung der 1 mit Hilfe der Möbius-Funktion)
Sei n ≥ 1. Dann gilt
1 = ∑1 ≤ m ≤ n μ(m) ⌊nm⌋.
Diese Ergebnisse können wir verwenden, um neu zu beweisen, dass es unendlich viele Primzahlen gibt. Hierzu beobachten wir:
Satz (Sprungverhalten der Floor-Funktion)
Sei n ≥ 1, und sei 1 ≤ m ≤ n. Weiter sei r ∈ { 0, …, m − 1 } der Rest der Division von n durch m. Dann gilt:
(a) | Ist r < m − 1, so gilt ⌊(n + 1)/m⌋ = ⌊n/m⌋. |
(b) | Ist r = m − 1, so gilt ⌊(n + 1)/m⌋ = ⌊n/m⌋ + 1. |
Speziell gilt ⌊(n + 1)/m⌋ = ⌊n/m⌋, falls n + 1 prim ist.
Beweis
Die Zahl a = ⌊n/m⌋ ist die Anzahl der Vielfachen von m in { 1, …, n }. Analoges gilt für b = ⌊(n + 1)/m⌋. Damit gilt b = a oder b = a + 1. Letzteres ist genau dann der Fall, wenn n + 1 durch m teilbar ist. Dies ist wiederum äquivalent zu r = m − 1.
Ist n ≥ 1 beliebig, so gilt nach der Einschluss-Ausschluss-Darstellung:
n = 1 + ∑p1 < … < pk ≤ n (−1)k − 1 ⌊np1 … pk⌋,
n + 1 = 1 + ∑p1 < … < pk ≤ n + 1 (−1)k − 1 ⌊n + 1p1 … pk⌋.
Folglich ist
∑p1 < … < pk ≤ n (−1)k − 1 ⌊np1 … pk⌋ + 1 = ∑p1 < … < pk ≤ n + 1 (−1)k − 1 ⌊n + 1p1 … pk⌋.
Gehen wir von n nach n + 1, so gibt es zwei mögliche (sich ausschließende) Gründe für eine Änderung der Summanden unserer Einschluss-Ausschluss-Darstellung:
(1) | n + 1 ist eine Primzahl. In diesem Fall wird eine neue Primzahl p* = n + 1 in die Summation aufgenommen. Diese Primzahl vergrößert die Summe um 1: Sie trägt den neuen Wert ⌊p*/p*⌋ = ⌊(n + 1)/(n + 1)⌋ = 1 bei, alle anderen Summanden bleiben gleich. |
(2) | n hat bei der Division durch ein Primzahlprodukt p1 … pk den Rest p1 … pk − 1, sodass n + 1 durch p1 … pk teilbar (und folglich nicht prim) ist. In diesem Fall springt die Floor-Funktion für p1, …, pk um 1. Der Beitrag zur Summe ist 1 für ungerade k und −1 für gerade k. Die Zahl der ungeraden k ist um genau 1 größer als die Zahl der geraden k. |
Der zweite Fall kann nicht eintreten, wenn n durch alle Primzahlen kleinergleich n teilbar ist. Damit können wir neu beweisen:
Satz (Unendlichkeit der Primzahlen)
Es gibt unendlich viele Primzahlen.
Beweis
Annahme: p1 < … < pk sind alle Primzahlen. Sei n = p1 … pk. Dann gilt
⌊np1 … pk⌋ = ⌊n + 1p1 … pk⌋ für alle Primzahlen p1 < … < pk.
Nach unserer Einschluss-Ausschluss-Darstellung wäre also n = n + 1, Widerspruch.
Der Beweis fällt erneut in die Klasse „Produkt plus 1“ und die kombinatorische Argumentation ist wesentlich komplizierter als das Argument von Euklid. Aber dennoch wirft der Beweis ein neues Licht auf die Primzahlen: Für jedes n summieren sich die signierten Änderungen der Floor-Funktion beim Schritt von n nach n + 1 zum Wert 1.
Beispiel
Wir verfolgen die Veränderungen der Einschluss-Ausschluss-Darstellung für die Zahlen n = 10, …, 49. Dabei unterdrücken wir 0-Beiträge.
| n = 10 | 12 − 2 | n = 30 | 44 − 15 + 1 |
| n = 11 | 13 − 2 | n = 31 | 45 − 15 + 1 |
| n = 12 | 15 − 3 | n = 32 | 46 − 15 + 1 |
| n = 13 | 16 − 3 | n = 33 | 48 − 16 + 1 |
| n = 14 | 18 − 4 | n = 34 | 50 − 17 + 1 |
| n = 15 | 20 − 5 | n = 35 | 52 − 18 + 1 |
| n = 16 | 21 − 5 | n = 36 | 54 − 19 + 1 |
| n = 17 | 22 − 5 | n = 37 | 55 − 19 + 1 |
| n = 18 | 24 − 6 | n = 38 | 57 − 20 + 1 |
| n = 19 | 25 − 6 | n = 39 | 59 − 21 + 1 |
| n = 20 | 27 − 7 | n = 40 | 61 − 22 + 1 |
| n = 21 | 29 − 8 | n = 41 | 62 − 22 + 1 |
| n = 22 | 31 − 9 | n = 42 | 65 − 25 + 2 |
| n = 23 | 32 − 9 | n = 43 | 66 − 25 + 2 |
| n = 24 | 34 − 10 | n = 44 | 68 − 26 + 2 |
| n = 25 | 35 − 10 | n = 45 | 70 − 27 + 2 |
| n = 26 | 37 − 11 | n = 46 | 72 − 28 + 2 |
| n = 27 | 38 − 11 | n = 47 | 73 − 28 + 2 |
| n = 28 | 40 − 12 | n = 48 | 75 − 29 + 2 |
| n = 29 | 41 − 12 | n = 49 | 76 − 29 + 2 |
Um die Eigenarten dieser Tabelle zu erklären, betrachten wir zunächst exemplarisch den Übergang von 41 zu 42. Es gilt
42 = 2 · 3 · 7.
Jeder der drei Primfaktoren erhöht die Summe der Einschluss-Ausschluss-Darstellung um 1 (für k = 1). Je zwei der drei Primfaktoren führen zu −1 in der Summe und die drei Primfaktoren führen zu +1 in der Summe. Damit ergibt sich beim Übergang von 41 zu 42 insgesamt eine Summenänderung von 3 − 3 + 1, was genau dem Unterschied von 62 − 22 + 1 und 65 − 25 + 2 entspricht. Allgemein lässt sich die Summenänderung beim Schritt von n − 1 nach n anhand der Primfaktorzerlegung von n berechnen, und genauer ist sie bereits durch die Anzahl der Primteiler von n bestimmt. Denn ist
n = p1e1 … prer mit p1 < … < pr und e1, …, er ≥ 1,
so ändern sich die Summen der Einschluss-Ausschluss-Darstellung beim Übergang von n − 1 nach n um
− + … + (−1)r − 1 + 0 + … + 0.
Der Leser verfolge dies konkret an einigen Beispielen, etwa von 29 nach 30 mit 30 = 2 · 3 · 5. Die Überlegung zeigt auch, dass sich genau bei den Primzahlpotenzen wie 24, 33 oder 171 nur der erste Summand um 1 ändert.
Verwendung der Möbius-Funktion
Wir notieren das Argument noch einmal explizit mit Hilfe der Möbius-Darstellung der 1.
Satz (Unendlichkeit der Primzahlen)
Es gibt unendlich viele Primzahlen.
Beweis: Produkt plus 1
Annahme: p1 < … < pk sind alle Primzahlen. Sei n = p1 … pk. Dann gilt μ(n + 1) = 0, da alle Produkte von paarweise verschiedenen Primzahlen kleinergleich n sind. Damit ist
| 1 | = ∑1 ≤ m ≤ n + 1 μ(m) ⌊n + 1m⌋ |
| = n + 1 + ∑2 ≤ m ≤ n μ(m) ⌊n + 1m⌋ | |
| = 1 + n + ∑2 ≤ m ≤ n μ(m) ⌊nm⌋ | |
| = 1 + ∑1 ≤ m ≤ n μ(m) ⌊nm⌋ | |
| = 1 + 1, |
Widerspruch.
Eine Variante, die 2n statt n + 1 verwendet, ist:
Beweis: Produkt mal 2
Annahme: p1 < … < pk sind alle Primzahlen. Sei n = p1 … pk. Dann gilt μ(m) = 0 für alle m > n, da alle Produkte von paarweise verschiedenen Primzahlen kleinergleich n sind. Weiter ist ⌊n/m⌋ = n/m für alle m mit μ(m) ≠ 0. Damit ist
| 1 | = ∑1 ≤ m ≤ 2n μ(m) ⌊2nm⌋ |
| = 2 ∑1 ≤ m ≤ n μ(m) ⌊nm⌋ | |
| = 2, |
Widerspruch.
Die „Produkt mal 2“-Variante lässt sich auch für die Einschluss-Ausschluss-Darstellung durchführen. Hier ergibt sich der Widerspruch
n = 1 + ∑p1 < … < pk ≤ n (−1)k − 1 ⌊np1 … pk⌋,
2n = 1 + 2 ∑p1 < … < pk ≤ n (−1)k − 1 ⌊np1 … pk⌋.
Mit Hilfe der μ-Funktion lassen sich viele Argumentationen sehr elegant notieren. Und viele ihrer Eigenschaften spiegeln Eigenschaften der Primzahlen. Als ein einfaches Beispiel hierfür halten wir fest:
Satz (Unendlichkeit der Primzahlen und Werte der Möbius-Funktion)
Die folgenden Aussagen sind äquivalent:
(a) | Es gibt unendlich viele Primzahlen. |
(b) | Die μ-Funktion nimmt den Wert −1 unendlich oft an. |
(c) | Die μ-Funktion nimmt den Wert 1 unendlich oft an. |
(d) | Die μ-Funktion ist nicht schließlich konstant gleich 0, d. h.: Für alle n0 gibt es ein n > n0 mit μ(n) ≠ 0. |
Beweis
(a) impliziert (b): Ist p prim, so gilt μ(p) = −1. Gibt es also unendlich viele Primzahlen, so gibt es unendlich viele Stellen, an denen die μ-Funktion den Wert −1 annimmt.
(b) impliziert (d): Nimmt die μ-Funktion unendlich oft den Wert −1 an, so ist sie offenbar nicht schließlich konstant gleich 0.
(c) impliziert (d): Analog zur letzten Implikation.
(d) impliziert (a): Seien p1 < … < pk Primzahlen und sei n0 = p1 … pk. Nach Voraussetzung gibt es n > n0 mit μ(n) ≠ 0. Dann ist n quadratfrei, also von der Form q1 …qm mit Primzahlen q1 < … < qm. Da n ≥ n0 ist, gibt es ein qi mit qi ≠ p1, …, pk. Dies zeigt, dass es unendlich viele Primzahlen gibt.
(a) impliziert (c): Nach Voraussetzung gibt es unendlich viele Primzahlen p mit p ≥ 3. Für jede solche Primzahl p gilt μ(2p) = (−1)2 = 1.