6. Polynome durch Primzahlen
Können die Primzahlen einfacher gewonnen werden als mit Hilfe eines Siebverfahrens? Gibt es eine einfache Funktion auf den positiven natürlichen Zahlen, die alle Primzahlen aufzählt? Gibt es wenigstens eine einfache Funktion, deren Wertebereich eine unendliche Menge von Primzahlen ist? Euler hatte 1772 entdeckt, dass das schlichte Polynom f : ℕ → ℕ zweiten Grades mit
f (n) = n2 + n + 41 für alle n ≥ 0
an allen Stellen n = 0, …, 39 Primzahlen als Werte besitzt. Diese Werte sind:
41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601.
Erst der Wert f (40) = 1681 = 412 ist keine Primzahl mehr. Auch danach folgen noch viele Primzahlen: Unter den ersten hundert Werten von f finden sich genau 86 Primzahlen. Vielleicht lässt sich das Euler-Polynom ja noch verbessern, sodass alle Werte Primzahlen sind? Der folgende Satz von Goldbach zeigt, dass dies nicht möglich ist:
Satz (zusammengesetzte Werte von Polynomen)
Sei k > 0, und seien a0, …, ak ∈ ℤ mit ak > 0. Weiter sei f : ℤ → ℤ mit
f (x) = ak xk + ak − 1 xk − 1 + … + a1 x + a0 für alle x ∈ ℤ.
Dann ist die Menge { f (n) | n ∈ ℕ, f (n) ist zusammengesetzt } unendlich. Insbesondere gibt es also kein nichtkonstantes Polynom mit ganzzahligen Koeffizienten, das nur Primzahlen als Werte annimmt.
Beweis
Es gilt limn → ∞ f (n) = ∞ (da k ≠ 0 und ak > 0). Folglich gibt es ein n0 mit f (n) ≥ 2 für alle n ≥ n0. Sei n ≥ n0 beliebig. Wir setzen q = f (n). Nun zeigen wir, dass es unendliche viele m ≥ n gibt, sodass f (m) durch q teilbar ist. Dies genügt, da q ≥ 2 und limm → ∞ f (m) = ∞. Sei hierzu c ≥ 1 beliebig. Dann gilt
f(n + cq) = ak (n + cq)k + ak − 1 (n + cq)k − 1 + … + a1 (n + cq) + a0.
Ausmultiplizieren der Potenzen zeigt, dass ein b existiert mit
f(n + cq) = f (n) + qb.
Dann gilt aber f(n + cq) = f (n) + qb = q + qb = q(1 + b), sodass f(n + cq) durch q teilbar ist.
Diesem negativen Ergebnis steht auf der positiven Seite der allgemeine Satz über die Polynominterpolation gegenüber, der es erlaubt, ein Polynom durch endlich viele vorgegebene Punkte zu legen:
Satz (Polynominterpolation)
Sei n ≥ 0, und seien (x0, y0), …, (xn, yn) ∈ ℝ2 mit x0 < … < xn. Dann gibt es ein Polynom f : ℝ → ℝ mit f (x0) = y0, …, f (xn) = yn. Unter den Polynomen vom Grad kleinergleich n ist dieses Polynom zudem eindeutig bestimmt.
Beweis
Für alle i ≤ n definieren wir das Polynom fi : ℝ → ℝ vom Grad n durch:
fi(x) = (x − x0) … (x − xi − 1) (x − xi + 1) … (x − xn) für alle x ∈ ℝ.
(Der Linearfaktor (x − xi) wird im Produkt ausgelassen, sodass zum Beispiel f0(x) = (x − x1) … (x − xn).) Es gilt fi(xi) ≠ 0 für alle i ≤ n. Wir setzen nun
f = y0f0(x0) f0 + … + ynfn(xn) fn.
Dann ist f ein Polynom vom Grad kleinergleich n wie gewünscht. Zur Eindeutigkeit: Stimmen zwei Polynome f, g an den Stellen x0, …, xn überein, so ist das Polynom h = f − g an diesen Stellen gleich 0. Da ein Polynom vom Grad kleinergleich n höchstens n Nullstellen besitzt, ist h das Nullpolynom und damit f = g, falls f und g Polynome vom Grad kleinergleich n sind.
Damit gibt es also ein Polynom f : ℝ → ℝ, das an den Stellen 1, …, 1000 die ersten tausend Primzahlen als Werte annimmt, d. h. es gilt
f (n) = „die n-te Primzahl“ für alle n ≤ 1000.
Der konstruktive Beweis des Interpolationssatzes erlaubt es, Polynome, die ein Anfangsstück der Primzahlen aufzählen, konkret zu berechnen. Die ersten derartigen Polynome sind:
| n = 1: | 2 |
| n = 2: | 1 + x |
| n = 3: | 1/2 (4 − x + x2) |
| n = 4: | 1/6 (18 − 14x + 9x2 − x3) |
| n = 5: | 1/24 (144 − 206x + 141x2 − 34x3 + 3x4) |
| n = 6: | 1/5! (1800 − 3496x + 2730x2 − 935x3 + 150x4 − 9x5) |
| n = 7: | 1/6! (27360 − 61548x + 53732x2 − 22515x3 + 4925x4 − 537x5 + 23x6) |
Die ersten sieben Primzahl-Interpolationspolynome
Das elfte Primzahl-Interpolationspolynom
Das Polynom in der zweiten Abbildung hat Grad 10 und ist definiert durch
1/10! (3265920000 − 9233344800 x + 10602193032 x2 − 6626433140 x3
+ 2531800010 x4 − 624137745 x5 + 101334261 x6 − 10767210 x7
+ 720240 x8 − 27505 x9 + 457 x10)