Primzahlen/Auflistung/Unendlichkeit/Einführung/Textabschnitt

Das Sieb des Eratosthenes liefert eine einfache Methode, eine Liste von Primzahlen unterhalb einer bestimmten Größe ${}k$ zu erstellen. Man streicht einfach die echten Vielfachen der kleinen (kleiner als oder gleich ${}{\sqrt {k}}$) schon etablierten Primzahlen durch, die verbleibenden Zahlen sind prim.

Definition

Eine natürliche Zahl ${}n\geq 2$ heißt eine Primzahl, wenn die einzigen natürlichen Teiler von ihr ${}1$ und ${}n$ sind.

Eine Primzahl ist also eine natürliche Zahl, die genau zwei Teiler hat, nämlich ${}1$ und ${}n$, und die müssen verschieden sein. ${}1$ ist also keine Primzahl. Eine Zahl ${}\geq 2$, die keine Primzahl ist, heißt zusammengesetzt.

Die ersten Primzahlen sind ${}2,3,5,7,11,13,17,19,23,29,31,{\ldots }$. Für eine Primzahl ${}p$ und eine natürliche Zahl ${}n$ gilt folgende Alternative: Entweder teilt ${}p$ die Zahl ${}n$, oder aber ${}p$ und ${}n$ sind teilerfremd. Ein gemeinsamer Teiler muss ja ein Teiler von ${}p$ sein, und da kommen nur ${}1$ und ${}p$ in Frage.

Ein wichtiger Satz ist der Satz über die eindeutige Primfaktorzerlegung. Eine einfache Version davon ist der folgende Satz.

Satz

Jede natürliche Zahl ${}n\in \mathbb {N}$, ${}n\geq 2$, besitzt eine Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

${}n=p_{1}\cdot p_{2}{\cdots }p_{r}\,$

mit Primzahlen ${}p_{i}$.

Beweis

Wir beweisen die Existenz durch Induktion über ${}n$.  Für ${}n=2$ liegt eine Primzahl vor Bei ${}n\geq 3$ ist entweder ${}n$ eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ${}n$ ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung ${}n=ab$ mit kleineren Zahlen ${}a,b<n$. Für diese Zahlen gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für ${}n$ zusammen 

$\Box$

Für ${}105$ beispielsweise findet man den Primfaktor ${}3$ und kann daher ${}105=3\cdot 35$ schreiben. Für ${}35$ hat man die Zerlegung ${}35=5\cdot 7$ und man erhält

${}105=3\cdot 5\cdot 7\,.$

Wenn man mit dem Primfaktor ${}5$ startet, so ergibt sich ${}105=5\cdot 21=5\cdot 3\cdot 7$, insgesamt kommen also die gleichen Primfaktoren vor. Gelegentlich betrachten wir die Gleichung ${}1=1$ als die Primfaktorzerlegung der ${}1$, hier tritt jeder Primfaktor mit dem Exponenten ${}0$ auf, das leere Produkt ist ${}1$. Wir werden später in Fakt zeigen, dass die Primfaktorzerlegung bis auf die Reihenfolge eindeutig ist, was keineswegs selbstverständlich ist, einiger Vorbereitungen bedarf und am besten innerhalb der ganzen Zahlen bewiesen wird.

Der folgende Satz wird Euklid zugeschrieben.

Euklid (4. Jahrhundert v. C.)

Satz

Es gibt unendlich viele Primzahlen.

Beweis

Angenommen die Menge aller Primzahlen sei endlich, sagen wir ${}\{p_{1},p_{2},\ldots ,p_{r}\}$ sei eine vollständige Auflistung aller Primzahlen. Man betrachtet die natürliche Zahl

${}N=p_{1}\cdot p_{2}\cdot p_{3}{\cdots }p_{r}+1\,.$

Da bei Division von ${}N$ durch ${}p_{i}$ immer der Rest ${}1$ übrigbleibt  (bzw. nach Aufgabe) ist diese Zahl durch keine der Primzahlen ${}p_{i}$ teilbar. Andererseits besitzt ${}N$ nach Fakt eine Primfaktorzerlegung. Insbesondere gibt es eine Primzahl ${}p$, die ${}N$ teilt (dabei könnte ${}N=p$ sein). Doch damit muss ${}p$ gleich einem der ${}p_{i}$ aus der Liste sein, und diese sind keine Teiler von ${}N$. Dies ist ein Widerspruch, da ein ${}p_{i}$ nicht gleichzeitig ein Teiler und kein Teiler von ${}N$ sein kann. Also muss die Annahme (nämlich die Endlichkeit der Primzahlmenge) falsch gewesen sein.

$\Box$