number.wiki

Primzahlen

Published · By NumberWiki

Category Concepts

Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind. Die Primzahlen — 2, 3, 5, 7, 11, 13, 17, 19, 23, … — sind die Atome der Arithmetik: jede andere ganze Zahl entsteht, indem man sie miteinander multipliziert, und zwar auf genau eine Weise. Diese eine Tatsache macht Primzahlen zu den wichtigsten Objekten der gesamten Zahlentheorie.

Die Definition und warum 1 keine Primzahl ist

Formal ist eine ganze Zahl p > 1 eine Primzahl, wenn ihre einzigen positiven Teiler 1 und p sind. Eine Zahl größer als 1, die keine Primzahl ist, heißt zusammengesetzt — sie lässt sich als Produkt zweier kleinerer positiver ganzer Zahlen schreiben. So ist 12 zusammengesetzt (sie ist gleich 3 × 4), während 13 eine Primzahl ist (nichts außer 1 und 13 teilt sie).

Die Zahl 1 wird bewusst aus den Primzahlen ausgeschlossen. Das ist keine willkürliche Entscheidung — es ist das, was die übrige Arithmetik ordentlich hält. Wenn 1 als Primzahl zählte, dann hätte eine Zahl wie 12 unendlich viele „Primfaktor- zerlegungen“ (2 × 2 × 3, aber auch 1 × 2 × 2 × 3, und 1 × 1 × 2 × 2 × 3, …), und die Eindeutigkeit, von der das ganze Fachgebiet abhängt, würde zusammenbrechen. 1 als Einheit statt als Primzahl zu behandeln, hält die Zerlegungen eindeutig. Aus demselben Grund ist 0 weder prim noch zusammengesetzt.

Der Fundamentalsatz der Arithmetik

Der Grund, warum Primzahlen so wichtig sind, ist ein Ergebnis, das so zentral ist, dass man es den Fundamentalsatz der Arithmetik nennt: jede ganze Zahl größer als 1 ist entweder eine Primzahl oder lässt sich als Produkt von Primzahlen schreiben, und dieses Produkt ist eindeutig bis auf die Reihenfolge der Faktoren. Es gibt genau eine einzige Möglichkeit, eine Zahl in Primzahlen zu zerlegen.

So ist 60 immer 2² × 3 × 5 — keine andere Kombination von Primzahlen ergibt durch Multiplikation 60. Diese Eindeutigkeit ist es, die uns überhaupt erlaubt, über Teilbarkeit, größte gemeinsame Teiler, vollständig gekürzte Brüche und modulare Arithmetik nachzudenken. Jede Zahlenseite auf dieser Website zeigt diese Primfaktorzerlegung nahe am oberen Rand; sie ist in einem ganz realen Sinne die DNA der Zahl.

Es gibt unendlich viele Primzahlen

Um 300 v. Chr. bewies Euklid in seinen Elementen, dass die Primzahlen niemals ausgehen — einer der ältesten Sätze, die noch im Wesentlichen unverändert gelehrt werden. Sein Argument ist ein Muster an Eleganz. Angenommen, Sie hätten eine vollständige endliche Liste aller Primzahlen. Multiplizieren Sie sie alle miteinander und addieren Sie 1. Die so erhaltene Zahl lässt bei der Division durch jede Primzahl Ihrer Liste den Rest 1, also teilt keine von ihnen sie — was bedeutet, dass sie entweder selbst eine neue Primzahl ist oder einen Primfaktor besitzt, den Sie übersehen haben. So oder so war Ihre „vollständige“ Liste unvollständig. Keine endliche Liste kann sie alle enthalten, also gibt es unendlich viele Primzahlen.

Obwohl es unendlich viele Primzahlen gibt, werden sie mit zunehmender Größe seltener. Der Primzahlsatz, 1896 bewiesen, präzisiert dies: die Anzahl der Primzahlen unterhalb von n beträgt ungefähr n ⁄ ln n. Nahe einer Million ist etwa 1 von 14 Zahlen prim; nahe einer Billion nur noch etwa 1 von 27. Die Primzahlen werden dünner gesät, hören aber nie auf.

Wie prüft man, ob eine Zahl prim ist?

Die Schulbuchmethode ist die Probedivision: um zu prüfen, ob n prim ist, versuchen Sie, sie durch jede ganze Zahl von 2 bis √n zu teilen. Teilt keine davon ohne Rest, so ist n prim. Sie müssen nur bis zur Quadratwurzel gehen, denn hätte n einen Faktor größer als √n, so müsste es auch einen zugehörigen Faktor kleiner als √n haben, den Sie bereits gefunden hätten. Die Probedivision ist einfach und funktioniert gut für kleine Zahlen, wird aber hoffnungslos langsam für die großen Zahlen, die in der Kryptographie verwendet werden.

Für größere Zahlen verwenden Mathematiker probabilistische und deterministische Primzahltests, die enorm viel schneller sind. Der Miller–Rabin-Test kann Primalität mit überwältigender Sicherheit in einem winzigen Bruchteil der Zeit bescheinigen, und mit einem festen Satz von Zeugenwerten wird er zu einem garantiert korrekten Test für jede 64-Bit-Ganzzahl — und genau so entscheidet NumberWiki die Primalität auf jeder Seite. 2002 bewies der AKS-Algorithmus, dass sich Primalität allgemein in polynomieller Zeit testen lässt, womit eine lange offene theoretische Frage geklärt wurde, auch wenn Miller–Rabin in der Praxis das Arbeitspferd bleibt.

Das Sieb des Eratosthenes

Um alle Primzahlen bis zu einer Grenze auf einmal zu finden, ist das klassische Werkzeug das Sieb des Eratosthenes, benannt nach dem griechischen Mathematiker, der im dritten Jahrhundert v. Chr. die Bibliothek von Alexandria leitete. Schreiben Sie jede Zahl von 2 bis zu Ihrer Grenze auf. Kreisen Sie die 2 ein, dann streichen Sie alle ihre Vielfachen. Kreisen Sie die nächste nicht gestrichene Zahl (3) ein und streichen Sie alle ihre Vielfachen. Wiederholen Sie das. Die Zahlen, die ungestrichen übrig bleiben, sind genau die Primzahlen. Es ist über zweitausend Jahre alt und im Wesentlichen noch immer die Art, wie Primzahlen heute in großer Menge aufgezählt werden.

Familien von Primzahlen

Zahlentheoretiker verfolgen viele besondere Familien von Primzahlen, von denen NumberWiki mehrere automatisch kennzeichnet:

Die Goldbachsche Vermutung und andere offene Probleme

Trotz ihrer einfachen Definition verbergen Primzahlen einige der schwierigsten ungelösten Probleme der Mathematik. Die Goldbachsche Vermutung (1742) behauptet, dass jede gerade Zahl größer als 2 die Summe zweier Primzahlen ist — per Computer für jede gerade Zahl bis in die Hunderte von Trillionen überprüft, doch im Allgemeinen noch immer unbewiesen. Jede Seite einer geraden Zahl auf dieser Website zeigt eine Goldbach-Zerlegung. Die Riemannsche Vermutung, über die tiefe Verteilung der Primzahlen, ist mit einem Preis von einer Million Dollar verbunden und gilt weithin als das wichtigste offene Problem der gesamten Mathematik. Die Primzahlzwillings- vermutung, oben erwähnt, ist ein drittes. Dass solche elementaren Fragen nach Jahrhunderten offen bleiben, macht einen großen Teil der bleibenden Faszination der Primzahlen aus.

Warum Primzahlen außerhalb der Mathematik wichtig sind

Primzahlen sind nicht bloß eine Kuriosität. Die moderne Public-Key-Kryptographie — der RSA-Algorithmus, der hilft, Webverkehr, Bankwesen und Nachrichtenversand zu sichern — beruht unmittelbar auf einer auffälligen Asymmetrie: es ist leicht, zwei große Primzahlen miteinander zu multiplizieren, aber außerordentlich schwer, vom Produkt auszugehen und die ursprünglichen Primzahlen zurückzugewinnen. Multiplizieren Sie zwei 300-stellige Primzahlen, und das Ergebnis ist trivial zu berechnen; zerlegen Sie dieses 600-stellige Produkt wieder in seine Primzahlen, und die schnellsten bekannten Computer würden länger brauchen als das Alter des Universums. Die Sicherheit eines großen Teils der digitalen Welt beruht auf der Schwierigkeit, Primzahlen wieder zu „entmultiplizieren“.

Primzahlen auf NumberWiki

Jede Zahlenseite auf dieser Website berechnet die Primalität deterministisch und zeigt für zusammengesetzte Zahlen die eindeutige Primfaktorzerlegung, die vollständige Liste der Teiler und die Faktorpaare. Primzahlseiten sind mit prim gekennzeichnet, und besondere Familien erhalten eigene Tags, die Sie durchstöbern können — zum Beispiel Mersenne-Primzahlen, Primzahlzwillinge und Palindrome. Ein paar Primzahlen zum Erkunden: 2 (die einzige gerade Primzahl), die Umgebung von 1729, die Mersenne-Primzahl 8191 und die größte Primzahl unterhalb von zehntausend, 9973.

Weiterführende Literatur

Siehe auch