Primzahlen

Primzahlen sind natürliche Zahlen mit einer besonderen Eigenschaft. Sie spielen in vielen Bereichen der Mathematik und Informatik eine wichtige Rolle. So sind sie beispielsweise für viele Verfahren, die in der Kryptografie Anwendung finden, unentbehrlich. Auch für viele Bereiche der Mathematik sind Primzahlen überaus nützlich, wie wir im Folgenden sehen werden.

Definition und Eigenschaften von Primzahlen

Definition: Primzahl

Eine natürliche Zahl \(p \in \mathbb{N}\) heißt Primzahl, wenn \(p \not = 1\), und wenn aus \(a|p\) für \(a \in \mathbb{N}\) folgt, dass \(a = 1\) oder \(a = p\) ist.

Mit anderen Worten: Eine Primzahl ist eine natürliche Zahl \(\not = 1\), die nur durch 1 und sich selber teilbar ist.

Alle anderen Zahlen, also solche Zahlen, die keine Primzahlen sind, nennen wir zusammengesetzte Zahlen oder zusammengesetzt.

Satz: Fundamentalsatz der Arithmetik

Jede natürliche Zahl \(x \in \mathbb{N}\) lässt sich in eindeutiger Weise als Produkt von endlich vielen Primzahlen \(p_1, \dots, p_n\), also in der Form \(x = p_1 \cdot ... \cdot p_n\), schreiben. Wir nennen das Produkt \(p_1 \cdot ... \cdot p_n\) die Primfaktorzerlegung von \(x\).

Beispiel: Primfaktorzerlegung

1. Die Primfaktorzerlegung von 92 ist \(92 = 2 \cdot 2 \cdot 23\).
2. Die Primfaktorzerlegung von 7 ist 7, denn es handelt sich um eine Primzahl.
3. Die Primfaktorzerlegung von 16 ist \(16 = 2 \cdot 2 \cdot 2 \cdot 2\).
4. Die Primfaktorzerlegung von 123456 ist \(123456 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 643\).

Der folgende Satz über Primzahlen geht auf den berühmten griechischen Mathematiker Euklid zurück, der im dritten Jahrhundert vor Christus in Alexandria lebte. Er besagt, dass es unendlich viele Primzahlen gibt.

Satz: Der Satz von Euklid

"Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen."

Beweis:

Euklid bewies die Aussage dieses Satzes mit einem Widerspruchsbeweis: Angenommen, es gäbe nur endlich viele Primzahlen \(p_1, \dots, p_n\). Sei \(m := p_1 \cdot p_2 \cdot ... \cdot p_{n-1} \cdot p_n\) das Produkt all dieser Primzahlen. Dann gibt es zwei Möglichkeiten für \(m + 1\):

1. Möglichkeit: \(m + 1\) ist eine Primzahl. Da \(m + 1\) aber größer als alle \(p_1, \dots, p_n\) ist, wäre \(m + 1\) eine weitere Primzahl. Dies steht im Widerspruch zur Annahme.


2. Möglichkeit: \(m + 1\) ist keine Primzahl. Dann muss sie durch eine Primzahl \(q\) teilbar sein. Nach Annahme muss \(q\) dann eine der Primzahlen \(p_1, \dots, p_n\) sein. Damit ist \(q\) aber auch ein Teiler von \(m\). Da \(q\) sowohl ein Teiler von \(m\) als auch von \(m + 1\) ist, muss \(q\) auch die Differenz, also 1, teilen. Dies ist jedoch nicht möglich, da 1 keinen Primteiler besitzt. Somit ergibt sich ein Widerspruch zur Annahme.

Da es keine weiteren Möglichkeiten gibt, ist die Annahme, es gäbe nur endlich viele Primzahlen, offensichtlich falsch. \(\square\)

Definition: Teilerfremd

Seien \(m, n \in \mathbb{N}\). Wir nennen \(m\) und \(n\) teilerfremd, wenn die Primfaktorzerlegung von \(m\) und \(n\) keinen gemeinsamen Faktor haben.

Beispiel: Teilerfremd

1. Die Primfaktorzerlegung von 6 ist \(6 = 2 \cdot 3\). Die Primfaktorzerlegung von 9 ist \(9 = 3 \cdot 3\). Die Zahlen 6 und 9 sind demnach nicht teilerfremd, denn sie besitzen die 3 als gemeinsamen Primfaktor.
2. Die Primfaktorzerlegung von 8 ist \(8 = 2 \cdot 2 \cdot 2\). Die Primfaktorzerlegung von 15 ist \(15 = 3 \cdot 5\). Die Zahlen 8 und 15 sind demnach teilerfremd, denn sie besitzen keinen gemeinsamen Primfaktor.

Die Eigenschaft, dass sich jede natürliche Zahl eindeutig als Produkt von endlich vielen Primzahlen darstellen lässt, macht Primzahlen für die Mathematik äußerst wichtig. Auch in der Kryptografie spielen Primzahlen eine entscheidende Rolle. In vielen Kryptoverfahren werden zufällig gewählte Primzahlen benötigt. Aber wie kann man eine solche zufällige Primzahl bestimmen? In der Praxis wird hierfür häufig zunächst eine "zufällige" ungerade Zahl gewählt und dann geprüft, ob es sich bei dieser Zahl um eine Primzahl handelt. Hierbei gibt es zwei Probleme: Zum einen ist die gewählte Zahl natürlich nicht wirklich zufällig, da man mit einem Computer keinen echten Zufall nachbilden kann. Es handelt sich vielmehr um Pseudozufallszahlen, die nach bestimmten Verfahren berechnet werden. Zum anderen steht man vor dem Problem, entscheiden zu müssen, ob die gewählte Zahl tatsächlich eine Primzahl ist. Eine Antwort auf diese Frage zu finden, ist schwieriger, als es zunächst den Anschein haben mag. Man könnte versuchen, durch sukzessives methodisches Ausprobieren mögliche Teiler dieser Zahl zu finden. Das mag für kleinere Zahlen noch funktionieren, ist allerdings für größere Zahlen nicht mehr effizient leistbar. Da man in der Kryptografie insbesondere mit sehr großen Primzahlen arbeitet, benötigt man also andere Möglichkeiten, um effizient zu entscheiden, ob eine gegebene Zahl eine Primzahl ist. Hierzu gibt es verschiedene Testverfahren - sogenannte Primzahltests - von denen wir zwei im Folgenden vorstellen wollen. Wir werden hierbei jedoch größtenteils auf Beweise verzichten, weil deren Komplexität zu groß ist.