Primzahlen
In diesem Kapitel schauen wir uns an, was Primzahlen sind.
Erforderliches Vorwissen
Einordnung
Nachdem wir in der Schule besprochen hatten, was Teiler sind, fragte mein Lehrer in die Runde: Welche Zahl hat mehr Teiler? Die Zahl
Während Strebermann & Friends begannen, irgendetwas in ihr Schulheft zu kritzeln, meldete ich mich selbstsicher: $4$ oder die Zahl $401$? Na, was meint ihr?Natürlich hat die
Dem Gekichere aus der ersten Reihe nach zu urteilen, wusste ich schon, dass meine Intuition mich mal wieder im Stich gelassen hat. In der damaligen Unterrichtsstunde lernte ich, dass es natürliche Zahlen gibt, die nur genau zwei Teiler haben – nämlich die $401$ mehr Teiler. Die Zahl ist doch viel größer.$1$ und sich selbst. Mich hat das überrascht.
Betrachten wir die Teilermengen der Zahlen von $0$ bis $20$,
| Teilermenge | Anzahl der Elemente |
|---|---|
$T_0 = \{1\}$ | $1$ |
$T_1 = \{1\}$ | $1$ |
$T_2 = \{1, 2\}$ | $2$ |
$T_3 = \{1, 3\}$ | $2$ |
$T_4 = \{1, 2, 4\}$ | $3$ |
$T_5 = \{1, 5\}$ | $2$ |
$T_6 = \{1, 2, 3, 6\}$ | $4$ |
$T_7 = \{1, 7\}$ | $2$ |
$T_8 = \{1, 2, 4, 8\}$ | $4$ |
$T_9 = \{1, 3, 9\}$ | $3$ |
$T_{10} = \{1, 2, 5, 10\}$ | $4$ |
$T_{11} = \{1, 11\}$ | $2$ |
$T_{12} = \{1, 2, 3, 4, 6, 12\}$ | $6$ |
$T_{13} = \{1, 13\}$ | $2$ |
$T_{14} = \{1, 2, 7, 14\}$ | $4$ |
$T_{15} = \{1, 3, 5, 15\}$ | $4$ |
$T_{16} = \{1, 2, 4, 8, 16\}$ | $5$ |
$T_{17} = \{1, 17\}$ | $2$ |
$T_{18} = \{1, 2, 3, 6, 9, 18\}$ | $6$ |
$T_{19} = \{1, 19\}$ | $2$ |
$T_{20} = \{1, 2, 5, 10, 20\}$ | $5$ |
so können wir feststellen, dass $2$, $3$, $5$, $7$, $11$, $13$, $17$ und $19$ genau zwei Teiler haben. Diese Zahlen sind von einer so herausragenden Bedeutung, dass wir ihnen einen Namen geben.
Definition
Eine natürliche Zahl größer als $1$, die nur durch $1$ und durch sich selbst teilbar ist, heißt Primzahl.
Häufig gestellte Fragen
Im Zusammenhang mit den Primzahlen, gibt es einige häufig gestellte Fragen:
Ist 0 eine Primzahl?
Nein. Die $0$ ist zwar durch $1$, aber nicht durch sich selbst teilbar.
Zur Erinnerung: Eine Division durch $0$ ist nicht erlaubt!
Ist 1 eine Primzahl?
Nein. Aber warum ist das so? Immerhin ist doch die $1$ durch $1$ und sich selbst teilbar!
Es gibt eine Reihe von Gründen, warum die $1$ keine Primzahl ist. Der wohl einfachste Grund lautet: Eine Primzahl hat zwei (verschiedene) Teiler. Die $1$ hat jedoch nur einen Teiler.
Ist 2 die einzige gerade Primzahl?
Ja, denn jede andere gerade Zahl ist ebenfalls durch $2$ teilbar und damit keine Primzahl.
Wie viele Primzahlen gibt es?
Es gibt unendlich viele Primzahlen.
Wie viele Stellen hat die derzeit größte bekannte Primzahl?
Über 24,8 Millionen Stellen! (Quelle: mersenne.org)
Kann ich dabei mithelfen, eine noch größere Primzahl zu finden?
Ja. Es gibt ein Programm namens Prime95, das jeder auf seinem Computer installieren kann, um bei der Berechnung der nächsten Rekord-Primzahlen mitzumachen.
Gibt es eine Formel, mit der alle Primzahlen berechnet werden können?
Nein, bislang ist keine Formel bekannt. Wenn dir zufällig eine einfällt, sag mir Bescheid!
Primzahlen und zusammengesetzte Zahlen
Jede natürliche Zahl $> 1$ ist entweder eine Primzahl oder eine zusammengesetzte Zahl.
Primzahlen und zusammengesetzte Zahlen von $0$ bis $100$
${\color{red}0}$ | ${\color{red}1}$ | ${\color{green}2}$ | ${\color{green}3}$ | $4$ | ${\color{green}5}$ | $6$ | ${\color{green}7}$ | $8$ | $9$ | $10$ |
${\color{green}11}$ | $12$ | ${\color{green}13}$ | $14$ | $15$ | $16$ | ${\color{green}17}$ | $18$ | ${\color{green}19}$ | $20$ | |
$21$ | $22$ | ${\color{green}23}$ | $24$ | $25$ | $26$ | $27$ | $28$ | ${\color{green}29}$ | $30$ | |
${\color{green}31}$ | $32$ | $33$ | $34$ | $35$ | $36$ | ${\color{green}37}$ | $38$ | $39$ | $40$ | |
${\color{green}41}$ | $42$ | ${\color{green}43}$ | $44$ | $45$ | $46$ | ${\color{green}47}$ | $48$ | $49$ | $50$ | |
$51$ | $52$ | ${\color{green}53}$ | $54$ | $55$ | $56$ | $57$ | $58$ | ${\color{green}59}$ | $60$ | |
${\color{green}61}$ | $62$ | $63$ | $64$ | $65$ | $66$ | ${\color{green}67}$ | $68$ | $69$ | $70$ | |
${\color{green}71}$ | $72$ | ${\color{green}73}$ | $74$ | $75$ | $76$ | $77$ | $78$ | ${\color{green}79}$ | $80$ | |
$81$ | $82$ | ${\color{green}83}$ | $84$ | $85$ | $86$ | $87$ | $88$ | ${\color{green}89}$ | $90$ | |
$91$ | $92$ | $93$ | $94$ | $95$ | $96$ | ${\color{green}97}$ | $98$ | $99$ | $100$ |
Legende
- Primzahlen sind in grün dargestellt (z. B.
${\color{green}2}$,${\color{green}3}$,${\color{green}5}$). - Zusammengesetzte Zahlen sind in schwarz dargestellt (z. B.
$4$,$6$,$8$). ${\color{red}0}$und${\color{red}1}$sind weder Primzahlen noch zusammengesetzte Zahlen und deshalb rot.
Anmerkung
- Die zusammengesetzten Zahlen heißen so, weil sie sich in Produkte aus Primzahlen (genauer: Primfaktoren) zerlegen lassen. Für die ersten drei zusammengesetzten Zahlen gilt bespielsweise
$4 = 2 \cdot 2$,$\; 6 = 2 \cdot 3$und$\; 8 = 2 \cdot 2 \cdot 2$. - Die Zerlegung zusammengesetzter Zahlen in Primfaktoren heißt Primfaktorzerlegung.
- Im Gegensatz zu den zusammengesetzten Zahlen lassen sich die Primzahlen nicht weiter zerlegen. Sie sind quasi die Atome im Reich der Zahlen.
Handelt es sich um eine Primzahl?
Um herauszufinden, ob eine gegebene Zahl $a$ eine Primzahl $p$ ist, prüfen wir die Zahl $a$ systematisch auf ihre Teilbarkeit durch alle Primzahlen von $2$ bis $p^2 \leq a$.
Ist $47$ eine Primzahl?
$47$ ist durch keine der Primzahlen $2$, $3$ und $5$ teilbar.
Die $7$ müssen wir nicht mehr prüfen, denn $7^2$ ist schon größer als $47$.
Daraus folgt, dass $47$ eine Primzahl ist.
Ist $139$ eine Primzahl?
$139$ ist durch keine der Primzahlen $2$, $3$, $5$, $7$ und $11$ teilbar.
Die $13$ müssen wir nicht mehr prüfen, denn $13^2$ ist schon größer als $139$.
Daraus folgt, dass $139$ eine Primzahl ist.
Ausblick
Um alle Primzahlen bis 100, alle Primzahlen bis 1000 oder alle Primzahlen bis 10000 (oder was auch immer) zu bestimmen, müssen wir nicht jede Zahl einzeln untersuchen. Zur Lösung dieses Problems hilft uns das jahrtausendealte Sieb des Eratosthenes.
