Primzahl

Eine Primzahl (von lateinisch numerus primus ‚erste Zahl‘) ist eine natürliche Zahl, die genau zwei Teiler hat (und somit größer als 1 ist). Diese zwei Teiler sind 1 und die Zahl selber. Dabei bedeutet primus speziell „Anfang, das Erste (der Dinge)“,^[1] sodass eine „Anfangszahl“ gemeint ist, die aus keiner anderen natürlichen Zahl multiplikativ konstruiert werden kann.^[2]

Die Menge der Primzahlen wird in der Regel mit dem Symbol ${\displaystyle \mathbb {P} }$ bezeichnet. Man weiß durch den Satz des Euklid seit der Antike, dass es unendlich viele Primzahlen gibt. Mit ${\displaystyle \mathbb {P} }$ verknüpft ist die Folge ${\displaystyle \left(p_{n}\right)_{n\in \mathbb {N} }}$ der nach ihrer Größe geordneten Primzahlen, die man auch Primzahlfolge nennt.

Die Primzahlen lassen sich unter anderem mit Hilfe der Teileranzahlfunktion ${\displaystyle d(n)}$ definieren:

${\displaystyle \mathbb {P} =\{n\in \mathbb {N} \mid d(n)=2\}.}$

Es ist demnach

${\displaystyle \mathbb {P} =\{p_{n}\mid n\in \mathbb {N} \}\subset \mathbb {N} }$

mit

${\displaystyle \left(p_{n}\right)_{n\in \mathbb {N} }=\left(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97\dotsc \right)}$ (Folge A000040 in OEIS).

Die Bedeutung der Primzahlen für viele Bereiche der Mathematik beruht auf drei Folgerungen aus ihrer Definition:

• Existenz und Eindeutigkeit der Primfaktorzerlegung: Jede natürliche Zahl, die größer als 1 und selbst keine Primzahl ist, lässt sich als Produkt von mindestens zwei Primzahlen schreiben. Diese Produktdarstellung ist bis auf die Reihenfolge der Faktoren eindeutig. Zum Beweis dient das
• Lemma von Euklid: Ist ein Produkt zweier natürlicher Zahlen durch eine Primzahl teilbar, so ist mindestens einer der Faktoren durch sie teilbar.
• Primzahlen lassen sich nicht als Produkt zweier natürlicher Zahlen, die beide größer als 1 sind, darstellen.

Diese Eigenschaften werden in der Algebra für Verallgemeinerungen des Primzahlbegriffs genutzt.

Eine Zahl, die das Produkt von zwei oder mehr Primfaktoren ist, nennt man zusammengesetzt. Die Zahl 1 ist weder prim noch zusammengesetzt. Alle anderen natürlichen Zahlen sind eines von beiden, entweder prim (also Primzahl) oder zusammengesetzt.

Schon im antiken Griechenland interessierte man sich für die Primzahlen und entdeckte einige ihrer Eigenschaften. Obwohl Primzahlen seit damals stets einen großen Reiz auf die Menschen ausübten, sind viele die Primzahlen betreffenden Fragen bis heute ungeklärt, darunter solche, die mehr als hundert Jahre alt und leicht verständlich formulierbar sind. Dazu gehören die Goldbachsche Vermutung, wonach außer 2 jede gerade Zahl als Summe zweier Primzahlen darstellbar ist, und die Vermutung, dass es unendlich viele Primzahlzwillinge gibt (das sind Paare von Primzahlen, deren Differenz gleich 2 ist).

Primzahlen und ihre Eigenschaften spielen in der Kryptographie eine große Rolle, weil Primfaktoren auch mit dem Aufkommen elektronischer Rechenmaschinen nicht effizient gefunden werden können. Andererseits ermöglichen diese Maschinen eine effiziente Verschlüsselung sowie, wenn man den Schlüssel kennt, Entschlüsselung auch langer Texte.

1. ↑ Karl Ernst Georges: prior. In: Ausführliches lateinisch-deutsches Handwörterbuch. 8., verbesserte und vermehrte Auflage. Band 2. Hahnsche Buchhandlung, Hannover 1918, Sp. 1925–1927 (Digitalisat. zeno.org). 
2. ↑ Christlieb von Clausberg: Demonstrative Rechenkunst, oder Wissenschaft gründlich und kurz zu rechnen. Worinnen sowol gemeine als andere Kaufmännische Rechnungsarten, Proben und Wechsel-Arbitragen auf besondere kurze Manier gründlich gelehret werden, und eine Beschreibung Europäischer Münzen, Wechselarten und Usanzen, eine Vergleichung der Gewichte und Ellenmaße, die wahre Berechnung des Interusurii, eine neue Logarithmische Tabelle, auch mehr andere Mathematische und curiose Rechnungen beygefüget sind. Bernhard Christoph Breitkopf und Sohn, Leipzig 1762, S. 86 (eingeschränkte Vorschau in der Google-Buchsuche).