Primzahlen
wuerg, 22.04.2005 00:08
Es gibt deutlich einfachere Zahlen als die primen, doch sind sie von fundamentaler Bedeutung und gewiß würdig vor den Quadraten betrachtet zu werden, gleichwohl dies in keiner Weise auch nur annähernd erschöpfend möglich ist, zumal es über sie viele Bücher gibt und sich ein ganzer Zweig der Mathematik, nämlich die Zahlentheorie, großenteils und gerne mit Primzahlen beschäftigt.
Eine natürliche Zahl n=1,2,3,… heißt prim, wenn die Anzahl ihrer Teiler d(n)=2 ist. [1] Dabei heißt eine natürliche Zahl a Teiler von n, wenn es eine natürliche Zahl b mit ab=n gibt. Die beiden Teiler einer Primzahl n sind natürlich 1 und n selbst. Damit ist auch klar, daß 1 keine Primzahl ist, weil sie nur einen einzigen Teiler hat, also d(1)=1 ist. Alle Nicht‐Primzahlen außer 1 heißen zusammengesetzt. Für sie ist d(n)>2, womit sie einen echten Teiler a haben. Das ist einer mit 1<a<n.
Die Definition sondert aus der Menge ℕ der natürlichen Zahlen die Teilmenge ℙ der Primzahlen aus. Die Primzahlfolge [2] ergibt sich in kanonischer Weise durch die Anordnung der Primzahlen nach ihrer Größe. Dies führt zu einer mit Position 1 beginnenden Numerierung der Primzahlen. Die erste ist p₁=2, die zweite p₂=3, die dritte p₃=5 usw. Ein kurzes Anfangsstück der gerne bis zum Qualmen der CPU berechneten Primzahlen lautet:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 …
Das alles mag einem einfach und selbstverständlich erscheinen, doch selbst mit den Primzahlen verbundene simple Fragen können schon sehr schwer zu beantworten sein. Das wohl berühmteste Beispiel ist die Goldbach‐Vermutung, daß sich jede gerade Zahl größer als 4 als Summe zweier (ungerader) Primzahlen schreiben läßt:
[1] Das ist im Bereich der natürlichen Zahlen äquivalent zu einer in weiteren Bereichen gültigen Definition: p ist prim, wenn sie weder 0 noch eine Einheit ist und für alle durch p teilbaren Produkte ab bereits einer der Faktoren durch p geteilt wird, wenn man p also nicht auf mehrere Faktoren verteilen kann. Da 1 eine Einheit in den natürlichen Zahlen ist, scheidet sie als Primzahl aus. Man kann also nicht d(n)=2 durch d(n)≤2 ersetzen.
[2] The On-Line Encyclopedia of Integer Sequences. Primzahlen A000040, nicht zusammengesetzt A008578.
Sieb des Eratosthenes
Eine natürliche Zahl n=1,2,3,… heißt prim, wenn die Anzahl ihrer Teiler d(n)=2 ist. [1] Dabei heißt eine natürliche Zahl a Teiler von n, wenn es eine natürliche Zahl b mit ab=n gibt. Die beiden Teiler einer Primzahl n sind natürlich 1 und n selbst. Damit ist auch klar, daß 1 keine Primzahl ist, weil sie nur einen einzigen Teiler hat, also d(1)=1 ist. Alle Nicht‐Primzahlen außer 1 heißen zusammengesetzt. Für sie ist d(n)>2, womit sie einen echten Teiler a haben. Das ist einer mit 1<a<n.
Die Definition sondert aus der Menge ℕ der natürlichen Zahlen die Teilmenge ℙ der Primzahlen aus. Die Primzahlfolge [2] ergibt sich in kanonischer Weise durch die Anordnung der Primzahlen nach ihrer Größe. Dies führt zu einer mit Position 1 beginnenden Numerierung der Primzahlen. Die erste ist p₁=2, die zweite p₂=3, die dritte p₃=5 usw. Ein kurzes Anfangsstück der gerne bis zum Qualmen der CPU berechneten Primzahlen lautet:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 …
Das alles mag einem einfach und selbstverständlich erscheinen, doch selbst mit den Primzahlen verbundene simple Fragen können schon sehr schwer zu beantworten sein. Das wohl berühmteste Beispiel ist die Goldbach‐Vermutung, daß sich jede gerade Zahl größer als 4 als Summe zweier (ungerader) Primzahlen schreiben läßt:
6 = 3 + 3 14 = 3 + 11 22 = 3 + 19 30 = 7 + 23 38 = 7 + 31 8 = 3 + 5 16 = 3 + 13 24 = 5 + 19 32 = 3 + 29 40 = 3 + 37 10 = 3 + 7 18 = 5 + 13 26 = 3 + 23 34 = 3 + 31 42 = 5 + 37 12 = 5 + 7 20 = 3 + 17 28 = 5 + 23 36 = 5 + 31 usw.Bis heute ist diese Behauptung unbewiesen und auch nicht widerlegt, obwohl sie sehr plausibel erscheint, weil man zumeist wie hier bis zur Zahl 42 mit recht kleinen Summanden hinkommt. Deshalb möge der geneigte Leser die 98 versuchen, um zu erahnen, daß es bei sehr großen Zahlen doch recht unangenehm werden könnte.
[1] Das ist im Bereich der natürlichen Zahlen äquivalent zu einer in weiteren Bereichen gültigen Definition: p ist prim, wenn sie weder 0 noch eine Einheit ist und für alle durch p teilbaren Produkte ab bereits einer der Faktoren durch p geteilt wird, wenn man p also nicht auf mehrere Faktoren verteilen kann. Da 1 eine Einheit in den natürlichen Zahlen ist, scheidet sie als Primzahl aus. Man kann also nicht d(n)=2 durch d(n)≤2 ersetzen.
[2] The On-Line Encyclopedia of Integer Sequences. Primzahlen A000040, nicht zusammengesetzt A008578.
Sieb des Eratosthenes
... comment
