Mathematik - Zahlentheorie

Primzahlen leicht erklärt

Verfasst von Viktor Jonas · Lesezeit etwa 9 Minuten

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.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 … die 1 ist keine Primzahl — sie hat nur einen Teiler, nicht zwei
Fachbegriffe

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

360 ÷ 2 = 180
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

Alle Primzahlen bis 30 finden
SchrittWas passiertGestrichen
12 bleibt, alle Vielfachen streichen4, 6, 8, 10 …
23 bleibt, alle Vielfachen streichen9, 15, 21, 27
35 bleibt, alle Vielfachen streichen25
4fertig, 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.

Typische Fehler

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.

Übungsaufgabe

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.

Primzahlzwillinge und Rekordprimzahlen

Je weiter man in der Zahlenreihe nach oben geht, desto seltener werden Primzahlen — aber sie verschwinden nie. Manchmal stehen zwei von ihnen dicht beieinander: 3 und 5, 11 und 13, 17 und 19, 29 und 31, 41 und 43. Solche Paare mit dem Abstand 2 heißen Primzahlzwillinge. Ein kleiner Trick zeigt, wo man sie suchen muss: Jede Primzahl über 3 liegt direkt neben einem Vielfachen von 6, denn alle anderen Reste ergeben gerade Zahlen oder Vielfache von 3. Bis auf das Paar 3 und 5 hat deshalb jeder Zwilling die Form 6k − 1 und 6k + 1, zum Beispiel 5 und 7 oder 17 und 19.

Ob es unendlich viele Primzahlzwillinge gibt, ist bis heute unbewiesen. Immerhin gelang 2013 dem Mathematiker Yitang Zhang ein Durchbruch: Er zeigte, dass es unendlich viele Primzahlpaare gibt, deren Abstand höchstens 70 Millionen beträgt. Andere Forscher drückten diese Schranke danach auf 246. Bis zur 2 ist es also noch ein weiter Weg.

Mersenne-Primzahlen und die Jagd nach Rekorden

Die größten bekannten Primzahlen haben fast immer die Form 2p − 1, wobei der Exponent p selbst eine Primzahl ist. Man nennt sie Mersenne-Primzahlen. Die ersten sind 2² − 1 = 3, 2³ − 1 = 7, 2⁵ − 1 = 31 und 2⁷ − 1 = 127. Ein Automatismus ist das aber nicht: Schon 2¹¹ − 1 = 2.047 ist keine Primzahl, denn 23 · 89 = 2.047. Für Zahlen dieser Bauart gibt es einen besonders schnellen Test, den Lucas-Lehmer-Test. Deshalb lassen sich hier Rekorde viel weiter treiben als bei beliebigen Zahlen. Gesucht wird im Gemeinschaftsprojekt GIMPS (Great Internet Mersenne Prime Search), bei dem Freiwillige die Rechenzeit ihrer Computer zur Verfügung stellen. Die Rekordzahlen haben viele Millionen Dezimalstellen — ausgeschrieben würden sie viele tausend Buchseiten füllen.

Übungsaufgabe

Finde alle Primzahlzwillinge unter 50 und prüfe, ob jedes Paar außer 3 und 5 die Form 6k − 1 und 6k + 1 hat.

Lösung anzeigen

Die Primzahlen bis 50 sind 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Mit Abstand 2 stehen nebeneinander: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) und (41, 43).
Zur Probe: 5 und 7 liegen um die 6 (k = 1), 11 und 13 um die 12 (k = 2), 17 und 19 um die 18 (k = 3), 29 und 31 um die 30 (k = 5), 41 und 43 um die 42 (k = 7). Nur (3, 5) fällt aus der Reihe, weil die 3 selbst ein Teiler von 6 ist. Die 47 hat keinen Zwilling, denn 45 und 49 sind beide zusammengesetzt.

Wie die RSA-Verschlüsselung Primzahlen nutzt

Das Verfahren RSA, benannt nach seinen Erfindern Rivest, Shamir und Adleman, schützt seit den 1970er Jahren Daten im Internet. Die Grundidee: Man wählt zwei sehr große Primzahlen p und q und multipliziert sie zu n = p · q. Das Produkt n wird veröffentlicht, die beiden Faktoren bleiben geheim. Wer eine Nachricht verschlüsseln will, braucht nur n und eine zweite öffentliche Zahl e. Wer sie lesen will, braucht zusätzlich einen geheimen Exponenten d, und den kann man nur ausrechnen, wenn man p und q kennt.

Schlüsselerzeugung im Spielzeugformat

p = 61 und q = 53, also n = 61 · 53 = 3.233
(p − 1) · (q − 1) = 60 · 52 = 3.120
öffentlich: e = 17, geheim: d = 2.753
Probe: 17 · 2.753 = 46.801 = 15 · 3.120 + 1

Nachricht 65 verschlüsseln: 6517 ergibt bei Division durch 3.233 den Rest 2.790
Entschlüsseln: 2.7902753 ergibt bei Division durch 3.233 wieder den Rest 65

Dass hier wirklich die Nachricht wiederkehrt, folgt aus einem Satz von Euler über Reste bei der Division. Entscheidend ist der Blick auf die Sicherheit: Die kleine Zahl 3.233 zerlegt jeder in Sekunden. Echte Schlüssel arbeiten mit einem n von 2.048 Bit, das sind über 600 Dezimalstellen. Die Probedivision müsste bis zur Wurzel von n laufen, also bis zu einer Zahl mit rund 300 Stellen, und das ist unmöglich. Auch die schnellsten bekannten Verfahren zum Zerlegen brauchen für solche Zahlen mit heutigen Rechnern unvorstellbar lange. Bewiesen ist allerdings nicht, dass es keinen schnellen Weg gibt. Quantencomputer könnten ihn nach heutigem Wissen theoretisch liefern, wenn sie einmal groß genug gebaut werden können. Die Sicherheit von RSA beruht also auf einer Erfahrung, nicht auf einem Beweis.

Zwillinge, Lücken und Rekorde

Primzahlen verteilen sich unregelmäßig, und genau das macht sie interessant. Mal liegen zwei dicht beieinander wie 11 und 13 oder 41 und 43 — solche Paare heißen Primzahlzwillinge. Mal klaffen große Lücken: Zwischen 113 und 127 liegt keine einzige. Solche Lücken lassen sich sogar auf Bestellung erzeugen. Nimmt man 101! und addiert nacheinander 2, 3, 4 und so weiter bis 101, ist jede dieser hundert Zahlen durch den jeweils addierten Wert teilbar und damit keine Primzahl. Beliebig lange primzahlfreie Strecken gibt es also mit Sicherheit — und trotzdem hören die Primzahlen nie auf.

Ob es unendlich viele Zwillinge gibt, weiß bis heute niemand. Die Frage ist eines der bekanntesten offenen Probleme der Mathematik. Bekannt ist dagegen, dass die Primzahlen mit wachsender Größe seltener werden: In der Nähe einer Zahl n liegt ungefähr jede ln(n)-te Zahl im Schnitt noch prim. Bei dreistelligen Zahlen ist das etwa jede siebte, bei Zahlen um eine Million nur noch jede vierzehnte.

Warum Banken Primzahlen brauchen

Das RSA-Verfahren, mit dem Browser und Banken Daten verschlüsseln, benutzt zwei sehr große Primzahlen, jede mit mehreren hundert Stellen. Multipliziert werden sie in Sekundenbruchteilen. Der öffentliche Schlüssel enthält nur das Produkt — und daraus die beiden Faktoren zurückzugewinnen, ist mit allen bekannten Verfahren praktisch unmöglich. Genau dieses Ungleichgewicht zwischen leichtem Hinweg und schwerem Rückweg ist die gesamte Sicherheit des Systems. Würde morgen jemand ein schnelles Verfahren zum Faktorisieren finden, müsste die halbe Internetverschlüsselung ausgetauscht werden.

← Zurück zur Übersicht