Es gibt unendlich viele Primzahlen der Form $4k+3$

$\newcommand{\set}[1]{\left\{{#1}\right\}}$Unter einer Primzahl verstehen wir eine natürliche Zahl, die genau zwei natürliche Zahlen als Teiler hat.

Dass es unendlich viele Primzahlen gibt, ist spätestens seit Euklid bekannt. Sein Beweis, dessen Idee wir verwenden werden, um die Aussage im Titel zu zeigen, lautet (in moderner Sprache):

Die Menge der Primzahlen ist nicht leer, denn $2$ ist offenbar eine Primzahl. Wenn wir annehmen, dass es nur endlich viele, sagen wir $n\in\mathbb N_{\geq 1}$, Primzahlen gibt, die mit ${p_1,\ p_2,\,\ldots,\ p_n}$ bezeichnet seien, dann können wir alle diese Zahlen miteinander multiplizieren und $1$ addieren, d.h. die Zahl $N:=1+\displaystyle\prod_{i=1}^{n} p_i$ betrachten. Diese ist durch keine der Primzahlen $p_i$ teilbar, denn aus $p_i \mid 1+\displaystyle\prod_{i=1}^{n} p_i$ folgt sofort $p_i\mid 1$, ein offensichtlicher Widerspruch.
Da $N$ eine natürliche Zahl größer als 1 ist, besitzt $N$ einen Primteiler (der kleinste Teiler $t$ von $N$, der größer als 1 ist, ist etwa ein solcher). Jedoch kann $t$ nicht in der Menge ${\set{p_1,\ p_2,\,\ldots,\ p_n}}$ enthalten sein, wie wir eben gesehen haben. Damit ist $t$ eine weitere Primzahl.

(Der Leser überlege sich, ob der Beweis gültig bleibt, wenn anfangs die Existenz wenigstens einer Primzahl nicht sichergestellt wird!)

Nun zum Beweis der eigentlichen Aussage. Zunächst ist die Primzahl $3$ von der verlangten Form. Nun sei $n\in\mathbb N$, und es seien ${p_1,\ p_2,\,\ldots,\ p_n}$ Primzahlen, die bei Division durch 4 alle den Rest 3 lassen. Jetzt betrachten wir die Zahl
\[
   N:=(-1)+4\cdot\displaystyle\prod_{i=1}^{n} p_i\quad{,}
\] die offenbar ebenfalls bei Division durch 4 den Rest 3 lässt, also insbesondere ungerade ist. Damit ist jeder Teiler von $N$ entweder von der Form $4k+1$ oder von der Form $4k+3$. Also ist insbesondere jeder Primteiler von $N$ von einer der beiden Formen.

Nehmen wir an, jeder Primteiler von $N$ hätte die Form $4k+1$. Dann nehmen wir uns doch mal zwei davon her (es muss mindestens zwei (mit Vielfachheit gezählt) geben, denn gäbe es nur einen, dann wäre er gleich $N$, und $N$ wäre dann entgegen Konstruktion nicht von der Form $4k+3$), nennen wir sie $4a+1$ und $4b+1$, und berechnen ihr Produkt:
\[
\begin{array}{rcl}
(4a+1)\cdot(4b+1) &=& 4a\cdot4b+4a+4b+1\\[2mm]
&=& 16ab+4(a+b)+1\\[2mm]
&=& 4\cdot4ab+4(a+b)+1\\[2mm]
&=& 4\cdot(4ab+a+b) + 1
\end{array}
\] Wir sehen also, dass ihr Produkt wieder von der Form $4k+1$ ist. Per Induktion folgt sofort, dass dann auch $N$ von der Form $4k+1$ wäre, was erneut einen Widerspruch zur Konstruktion von $N$ darstellen würde. Also hat $N$ mindestens einen Primteiler $t$ der Form $4k+3$.

Wäre $t$ eine der Zahlen $p_i$, so folgte
\[
t \mid (-1) + 4\cdot\prod_{i=1}^{n} p_i - 4\cdot\prod_{i=1}^{n} p_i = -1\quad{,}
\] also $t\mid -1$ und damit auch $t\mid 1$, was nicht möglich ist. Also ist $t$ von allen Primzahlen ${p_1,\ p_2,\,\ldots,\ p_n}$ verschieden und damit eine weitere Primzahl der Form $4k+3$. Also gibt es unendlich viele Primzahlen dieser Form.