Im Übungsblatt sollst du entscheiden, ob 91 eine Primzahl ist, und beim ersten Blick wirkt die Zahl ziemlich undurchsichtig. Eine Primzahl hat genau zwei positive Teiler, doch ob eine Zahl dazugehört, erkennst du oft schon mit wenigen gezielten Prüfungen.
Mit wenigen Regeln erkennst du Primzahlen sicher
- Definition: Eine Primzahl ist größer als 1 und hat genau zwei positive Teiler.
- Ausnahme: 2 ist die einzige gerade Primzahl.
- Prüfgrenze: Für einen einzelnen Primzahltest genügt es, Primteiler bis zur Quadratwurzel der Zahl zu prüfen.
- Verfahren: Das Sieb des Eratosthenes findet alle Primzahlen in einem Zahlenbereich.
Eine Primzahl hat genau zwei positive Teiler
Ob eine Zahl prim ist, entscheidet sich an ihrer Teilbarkeit ohne Rest. 7 ist prim, denn nur 1 und 7 teilen sie; 9 ist es nicht, weil auch 3 ein Teiler ist.
Die 1 wirkt wie ein Grenzfall, zählt aber nicht als Primzahl: Sie hat nur einen positiven Teiler. Das ist mehr als eine Festlegung für den Unterricht. Wie das Skript der Universität Freiburg zur Algebra und Zahlentheorie erläutert, würde die eindeutige Primfaktorzerlegung ihre klare Form verlieren, wenn 1 als Primzahl gälte: Aus 6 = 2 · 3 würde dann ebenso 6 = 1 · 2 · 3.
Auch 0 ist keine Primzahl. Für die Prüfung reicht die knappe Regel: Primzahlen beginnen bei 2. Und von dort an ist 2 selbst die einzige gerade Primzahl, denn jede andere gerade Zahl lässt sich durch 2 teilen.
Für den Primzahltest reicht die Wurzel als Grenze
Beim Prüfen einer einzelnen Zahl musst du nicht alle kleineren Zahlen als mögliche Teiler durchgehen. Es genügt, Primzahlen bis zur Quadratwurzel der Zahl zu testen.
Der Grund steckt in den Teilerpaaren: Hat eine Zahl einen Teiler größer als ihre Wurzel, gehört ein passender Teiler kleiner als die Wurzel dazu. Die folgende Tabelle hilft, den nächsten Schritt festzulegen.
| Situation | Was folgt daraus? | Was tust du? |
|---|---|---|
| Die Zahl ist kleiner als 2 | Sie ist keine Primzahl. | Beende den Test. |
| Die Zahl ist gerade und größer als 2 | Sie hat den Teiler 2. | Ordne sie als zusammengesetzt ein. |
| Kein Primteiler bis zur Wurzel teilt die Zahl | Ein weiterer Teiler müsste mit einem kleineren Teiler gepaart sein. | Ordne sie als Primzahl ein. |
Ich halte diese Wurzelgrenze für die nützlichste Prüfungsregel, weil sie eine lange Teilersuche auf wenige Kandidaten reduziert. Sie ist auch der Grund, warum nicht jede ungerade Zahl prim ist: Ungerade Zahlen können etwa durch 3, 5 oder 7 teilbar sein.
Bei 221 endet die Suche schon bei 13
Die Zahl 221 zeigt, warum die Wurzelregel in Aufgaben Zeit spart. Ihre Quadratwurzel liegt zwischen 14 und 15, also prüfst du nur die Primzahlen bis 13: 2, 3, 5, 7, 11 und 13.
221 ist ungerade und ihre Ziffernsumme ist 5, also fällt sie weder durch 2 noch durch 3. Sie endet nicht auf 0 oder 5. Die übrigen Kandidaten 7 und 11 teilen sie ebenfalls nicht; bei 13 geht die Rechnung jedoch auf: 221 = 13 · 17. Damit ist 221 zusammengesetzt, und du musst 17 nicht mehr als möglichen Teiler prüfen.
Genau hier passieren in Klassenarbeiten zwei typische Fehler: Manche prüfen nur gerade Teiler, andere testen nach der Wurzel weiter. Mit der Grenze und der Liste der Primzahlen bleibt der Test überschaubar.
Das Sieb des Eratosthenes findet viele Primzahlen auf einmal
Stehen statt einer Zahl gleich alle Primzahlen bis 100 auf dem Plan, ist der Einzeltest umständlich. Dafür eignet sich das Sieb des Eratosthenes, ein Verfahren, das zusammengesetzte Zahlen Schritt für Schritt anhand ihrer Vielfachen aussortiert.
Schreibe die Zahlen ab 2 auf. Die erste noch nicht gestrichene Zahl ist prim; streiche dann ihre Vielfachen. So gehst du mit der nächsten ungestrichenen Zahl weiter, bis die übrigen Zahlen Primzahlen sind. Beim Sieb bis 100 genügt es, die Vielfachen von 2, 3, 5 und 7 zu streichen, denn die nächste Primzahl, 11, liegt bereits über der Wurzel von 100.
Die Unterscheidung ist simpel: Einzelzahl prüfen heißt, mögliche Teiler bis zur Wurzel testen; eine Liste erstellen heißt, mit dem Sieb viele zusammengesetzte Zahlen auf einmal entfernen. Für die Prüfung passt das Sieb besonders gut, wenn eine Aufgabe eine ganze Tabelle verlangt.
Primfaktoren machen zusammengesetzte Zahlen lesbar
Wenn ein Primzahltest scheitert, ist die gefundene Teilbarkeit oft erst der Anfang. Zerlegst du eine zusammengesetzte Zahl weiter, erhältst du ihre Primfaktorzerlegung: Bei 60 lautet sie 2 · 2 · 3 · 5.
Diese Zerlegung hilft etwa beim Kürzen von Brüchen oder beim Bestimmen des größten gemeinsamen Teilers. Für die Zahlentheorie ist sie noch grundlegender: Jede natürliche Zahl größer als 1 lässt sich eindeutig als Produkt von Primzahlen darstellen, wenn man die Reihenfolge der Faktoren außer Acht lässt.
Euklids Beweis zeigt, dass Primzahlen nie ausgehen
Eine Primzahltabelle hat immer einen Rand, die Folge der Primzahlen nicht. In Buch IX, Proposition 20 seiner Elemente zeigt Euklid, dass es mehr Primzahlen gibt als jede zuvor festgelegte endliche Liste.
Die Grundidee: Multipliziere alle Primzahlen einer angenommenen vollständigen Liste und addiere 1. Keine Zahl aus der Liste teilt das Ergebnis ohne Rest; es muss also eine weitere Primzahl geben, die in der Liste fehlt. So wird aus der Definition eine überraschend große Aussage: Es gibt unendlich viele Primzahlen.
