Die Primzahlen sind besondere Zahlen. Wie wir sehen werden, sind die daraus gebildeten Restklassenringe sogar Körper. Manchmal werden die Primzahlen, und das ist etwas irreführend, durch folgende Eigenschaft beschrieben:
Definition. Wir nennen eine natürliche Zahl $u$ unzerlegbar, wenn sie nur sich selbst und die $1$ als Teiler besitzt. Mit anderen Worten: Gilt die Gleichung $u=t\cdot t'$ mit $t,t'\in \mathbb{N}$ und ist $t\not= u$, so ist $t=1$.
Die offizielle Definition einer Primzahl ist eine andere. Sie lautet wie folgt:
Definition. Eine Zahl $p\in \mathbb{N}$ heißt prim, falls gilt: Teilt $p$ ein Produkt $a\cdot b$ mit $a,b\in \mathbb{N}$, und teilt $p$ nicht die Zahl $a$, so ist $p$ ein Teiler von $b$.
Man muss schon zweimal hinschauen, um zu bemerken, dass diese beiden Definitionen nicht das gleiche besagen. Beide Definitionen lassen sich auf allgemeine kommutative Ringe $R$ mit $1$ verallgemeinern. Eine Ringelement $e\in R$ heißt Einheit, falls es ein multiplikatives Inverses $e^{-1}\in R$ gibt. Wir nennen im Folgenden eine Nicht-Einheit $u\in R$ unzerlegbar, wenn gilt: Ist $u=t\cdot t'$ eine Zerlegung von $u$ als Produkt zweier Ringelemente $t$ und $t'$, so muß eines dieser Ringelemente Einheit sein. Eine Nicht-Einheit $p\in R$ heißt prim, wenn gilt: Teilt $p$ ein Produkt $a\cdot b$, so teilt $p$ zumindest einen der Faktoren $a$ oder $b$.
In allgemeinen kommutativen Ringen sind prim und unzerlegbar tatsächlich verschiedene Eigenschaften. Ein Beispiel wird in den Übungen behandelt. Im Ring der ganzen Zahlen charakterisieren diese zwei Eigenschaften allerdings dieselben Elemente. Dies zu beweisen, nehmen wir uns als Nächstes vor.
Satz. Das Produkt zweier natürlicher Zahlen, welche beide kleiner als eine gegebene unzerlegbare Zahl sind, läßt sich nicht durch diese teilen.
Wir können diesen Satz auch anders formulieren: Ist $u\in\mathbb{N}$ unzerlegbar und gilt $0 < a < u$ und $0 < b < u$, so gilt $\bar{a}\cdot\bar{b}\not=\bar{0}$ im Restklassenring $\mathbb{Z} / u \mathbb{Z}$.
Beweis. Es sei $u\in \mathbb{N}$ unzerlegbar und $0 < a < u$. Wir betrachten die Menge $$M:= \{m\in\mathbb{N}\;\vert\; a\cdot m \;\text { ist durch $u$ teilbar.}\}$$ Offensichtlich ist $u\in M$, also $M$ nicht leer. Zum Beweis des Satzes reicht es nachzuweisen, dass $u$ das kleinste Element in $M$ ist. Gäbe es ein kleinstes Element $c \lt u$ in $M$, so führte uns das in folgender Weise zu einem Widerspruch:
Zuerst einmal können wir $c=1$ ausschließen, denn sonst wäre ja $a\cdot c=a$ kleiner als $u$ und somit nicht durch $u$ teilbar.
Da $u$ unzerlegbar ist und $c$ keine Einheit, kann nach Definition $u$ nicht durch $c$ teilbar sein. Somit gibt es eine Zahl $n$ mit $n\cdot c \lt u \lt (n+1)\cdot c$. Setzen wir $c'=u-n\cdot c$, so ist $c'$ positiv und kleiner als $c$. Da $c\in M$ gilt, ist $a\cdot c$ durch $u$ teilbar, und folglich auch $n\cdot a\cdot c$, sowie die Zahl $a(u-nc)=ac'$. Also ist auch $c'\in M$ und $c' < c$. Dies widerspricht unserer Annahme, dass es sich bei $c$ um das kleinste Element in $M$ handelt.
qed
Korollar. Ist $u\in \mathbb{N}$ unzerlegbar, und sind $\bar{a},\bar{b}\in
\mathbb{Z}/u\mathbb{Z}$ nicht Null, so ist auch deren Produkt $\bar{a}\bar{b}$ nicht Null in $\mathbb{Z}/u\mathbb{Z}$.
Beweis. Sind $\bar{a},\bar{b}$ nicht Null im Restklassenring $\mathbb{Z}/u\mathbb{Z}$, so gibt es Elemente $a'\in\bar{a}$ und $b'\in \bar{b}$ in den jeweiligen Restklassen mit $0 < a' < u$ und $0 < b' < u$. Wegen des obigen Satzes ist dann das Produkt $a'\cdot b'$ nicht durch $u$ teilbar, also $\bar{a}\cdot\bar{b}\not=\bar{0}$.
qed
Korollar. Eine natürliche Zahl ist genau dann unzerlegbar, wenn sie prim ist.
Beweis. Sei $u\in \mathbb{N}$ unzerlegbar. Wenn $u$ nicht prim wäre, so gäbe es ganze Zahlen $a$ und $b$, beide nicht durch $u$ teilbar, deren Produkt $a\cdot b$ aber durch $u$ teilbar wäre. Das widerspräche aber dem soeben gezeigten Korollar.
Sei umgekehrt $p\in \mathbb{N}$ prim. Wir müssen zeigen, dass dann $p$ auch unzerlegbar ist. Sei also $p=t\cdot t'$ eine Darstellung als Produkt mit $t,t'\in \mathbb{Z}$. Da $p$ prim ist, teilt es einen der Faktoren, sagen wir $t'$. Es gilt also $t'= s\cdot p$ für ein $s\in \mathbb{Z}$ und somit $p=t\cdot s\cdot p$. Daraus folgern wir $(1-ts)p=0$. In den ganzen Zahlen gibt es aber keine Nullteiler. Also muß gelten $1-ts=0$ und folglich ist $s$ das multiplikative Inverse zu $t$, die Zahl $t$ mithin eine Einheit.
qed
Korollar. Der Restklassenring $\mathbb Z/n\mathbb Z$ ist genau dann ein Körper, wenn $n\in \mathbb N$ prim ist.
Beweis. Ist $n=a\cdot b$ mit $a,b\gt 1$, so gilt ${\overline a}\cdot{\overline b}=0$. Dies ist in einem Körper nicht möglich. Ist dagegen $n=p$ prim und $a\in \mathbb Z/p\mathbb Z\setminus {0}$, so definiert die Multiplikation mit $a$ eine Abbildung \begin{align*}\alpha:\mathbb Z/n\mathbb Z&\to \mathbb Z/n\mathbb Z\\ b&\mapsto a\cdot b.\end{align*} Diese ist injektiv, denn gilt $\alpha(b)=\alpha(b')$, also $ab=ab'$, so folgt $a(b-b')=0$ in $\mathbb Z/n\mathbb Z$ und nach obigem Korollar muss gelten $b=b'$. Eine injektive Abbildung einer endlichen Menge in sich ist aber auch subjektiv. Folglich gibt es ein Element, das unter $\alpha$ auf die $1$ abgebildet wird. Dies Element ist das multiplikative Inverse $a^{-1}$ von $a$.
qed
Satz. (Eindeutigkeit der Primfaktorzerlegung) Sehen wir von der Reihenfolge, in der die Faktoren hingeschrieben werden, ab, lässt sich jede natürliche Zahl nur auf eine einzige Weise in Primfaktoren zerlegen.
Beweis. Jede natürliche Zahl lässt sich als ein endliches Produkt von Primfaktoren zerlegen. Dies ist der einfache Teil des Satzes. Wir überlegen uns dies aber trotzdem: Angenommen, es gäbe natürliche Zahlen, die sich nicht als Produkt von Primfaktoren darstellen lassen. Dann gäbe es auch eine kleinste solche Zahl $n$, die sich nicht in Primfaktoren zerlegen ließe. Hat $n$ einen Teiler $a$ ungleich $1$, so ist $n=a\cdot b$ mit $a < n$ und $b < n$. Beide $a$ und $b$ lassen sich in Primfaktoren zerlegen, also auch $n$. Besitzt hingegen $n$ nur sich selbst und die $1$ als Teiler, dann ist $n$ unzerlegbar und damit prim, also ein Produkt von Primzahlen mit nur einem Faktor. Die Annahme, es gäbe natürliche Zahlen, die sich nicht in Primfaktoren zerlegen lassen, ist also unsinnig.
Es bleibt noch, die Eindeutigkeit nachzuweisen. Nehmen wir nun an, dass $n\in\mathbb{N}$ sich in Primfaktoren zerlegt $n=a^\alpha\cdot b^\beta\cdot c^\gamma\ldots$, wobei $a, b, c\ldots$ verschiedene Primzahlen sind und $\alpha, \beta, \delta\ldots \in\mathbb{N}$ Exponenten.
Sei eine zweite solche Zerlegung gegeben, dann tauchen in der zweiten Zerlegung dieselben Primfaktoren auf: Fehlte einer der Faktoren $a, b, c,\ldots$, so würde dieser Faktor ja die Zahl $n$ nicht teilen wegen des letzten Satzes. Die beiden Zerlegungen können sich also nur insoweit unterscheiden, dass in der einen eine Primzahl $p$ öfter enthalten ($\pi$-mal) als in der anderen ($\pi'$-mal). Hebt man den Faktor $p$ aus beiden Systemen $\pi'$-mal weg, so kommt er in der einen Darstellung nicht mehr vor, in der anderen aber($\pi - \pi'$)-mal, also hat $\frac{n}{p^{\pi'}}$ zwei Darstellungen, in deren einer die Primzahl $p$ vorkommt, in der anderen aber nicht, im Widerspruch zum eben gezeigten.
qed
Der erste der beiden Sätze ist von Euklid schon bewiesen worden. Von C.-F. Gauß stammt der Beweis des zweiten. Er war der erste Mathematiker, dem die Eindeutigkeit der Primfaktorzerlegung überhaupt erwähnens- geschweige denn beweisenswert erschien. Er hatte dazu gute Gründe. Davon werden Sie im Verlauf Ihres Studiums noch mehr erfahren. Nur eines will ich Ihnen schon jetzt verraten: Es hing zusammen mit den komplexen Zahlen.