Primzahlen leicht erklärt
Eine Primzahl ist eine natürliche Zahl größer als 1, die genau zwei Teiler hat: 1 und sich selbst. 7 ist prim, weil nur 1 und 7 aufgehen. 8 ist es nicht, weil auch 2 und 4 passen. Primzahlen sind die Bausteine, aus denen sich jede andere Zahl zusammensetzt — deshalb tauchen sie in fast jedem mathematischen Gebiet wieder auf.
Teiler — eine Zahl, die ohne Rest aufgeht.
Primzahl — genau zwei Teiler.
Zusammengesetzte Zahl — mehr als zwei Teiler, z. B. 12.
Primfaktorzerlegung — die Darstellung einer Zahl als Produkt von Primzahlen.
Sieb des Eratosthenes — Verfahren, um alle Primzahlen bis zu einer Grenze zu finden.
Primzahlzwilling — zwei Primzahlen mit Abstand 2, etwa 11 und 13.
Warum die 1 nicht dazugehört
Das wirkt willkürlich, hat aber einen handfesten Grund. Der Hauptsatz der Arithmetik sagt: Jede Zahl über 1 lässt sich eindeutig in Primfaktoren zerlegen. Wäre die 1 eine Primzahl, gäbe es unendlich viele Zerlegungen — 12 = 2 · 2 · 3 = 1 · 2 · 2 · 3 = 1 · 1 · 2 · 2 · 3 und so weiter. Die Eindeutigkeit wäre dahin. Man schließt die 1 also aus, damit der wichtigste Satz über Zahlen sauber bleibt.
Primfaktorzerlegung
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1
360 = 23 · 32 · 5
Das Verfahren ist stumpf und funktioniert immer: durch die kleinste Primzahl teilen, die aufgeht, und mit dem Ergebnis weitermachen, bis 1 übrig bleibt. Aus der Zerlegung liest man anschließend Dinge ab, für die man sonst raten müsste — etwa das kleinste gemeinsame Vielfache oder den größten gemeinsamen Teiler zweier Zahlen.
Das Sieb des Eratosthenes
| Schritt | Was passiert | Gestrichen |
|---|---|---|
| 1 | 2 bleibt, alle Vielfachen streichen | 4, 6, 8, 10 … |
| 2 | 3 bleibt, alle Vielfachen streichen | 9, 15, 21, 27 |
| 3 | 5 bleibt, alle Vielfachen streichen | 25 |
| 4 | fertig, denn 7 · 7 = 49 > 30 | — |
Übrig bleiben 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Der letzte Schritt ist der nützlichste: Man muss nur bis zur Wurzel der Obergrenze sieben. Wer prüfen will, ob 97 prim ist, testet die Teiler 2, 3, 5 und 7 — mehr nicht, denn 11 · 11 = 121 liegt schon über 97.
1 als Primzahl gezählt. Sie ist keine.
2 vergessen. 2 ist die einzige gerade Primzahl und wird beim
schnellen Aufzählen oft übersprungen.
Alle Zahlen als Teiler getestet. Es genügt, bis zur Wurzel zu
prüfen — das spart bei dreistelligen Zahlen fast die gesamte Arbeit.
„Alle ungeraden Zahlen sind prim." 9, 15, 21 und 25 sagen etwas
anderes.
Es gibt unendlich viele
Euklid hat das vor über zweitausend Jahren bewiesen, und der Beweis passt in vier Zeilen. Angenommen, es gäbe nur endlich viele Primzahlen. Dann multipliziert man sie alle miteinander und addiert 1. Die neue Zahl lässt bei der Division durch jede der angenommenen Primzahlen den Rest 1 — keine von ihnen geht auf. Also ist die neue Zahl entweder selbst prim oder hat einen Primfaktor, der nicht in der Liste stand. Beides widerspricht der Annahme. Damit kann die Liste nie vollständig sein.
Prüfe, ob 143 eine Primzahl ist. Begründe, welche Teiler du testen musst und warum du nicht weiter suchen brauchst.
Lösung anzeigen
Die Wurzel aus 143 liegt zwischen 11 und 12, denn 11 · 11 = 121 und
12 · 12 = 144. Zu testen sind also nur die Primzahlen bis 11: 2, 3, 5, 7 und 11.
2 scheidet aus (143 ist ungerade), 3 ebenfalls (Quersumme 8), 5 auch (letzte Ziffer
ist keine 0 oder 5), 7 geht nicht auf (7 · 20 = 140, Rest 3). Aber
11 · 13 = 143.
143 ist also keine Primzahl. Hätte auch die 11 nicht gepasst, wäre
143 prim gewesen — ein größerer Teiler bräuchte einen kleineren Partner, und alle
kleineren wurden geprüft.
Primzahlen sind nicht nur Schulstoff. Die Verschlüsselung, mit der dein Browser Bankdaten überträgt, beruht darauf, dass sich zwei sehr große Primzahlen mühelos multiplizieren, das Produkt aber praktisch nicht wieder zerlegen lässt.
← Zurück zur Übersicht