Primzahlen modulo vier

Die Sätze von Euler und Fermat haben zahlreiche weitere Anwendungen, und wir wollen eine davon hier noch vorstellen. Eine Variation des Beweises der Unendlichkeit der Primzahlen zeigte, dass es unendlich viele Primzahlen p gibt mit p ≡ 3 mod(4). Mit Hilfe des Satzes von Fermat können wir nun zeigen:

Satz (Primzahlen kongruent 1 modulo 4)

Es gibt unendlich viele Primzahlen p mit p ≡ 1 mod(4).

Beweis

Sei n ≥ 1 beliebig, und seien p₁, …, p_n Primzahlen mit p_i ≡ 1 (4) für alle i ≤ n. Wir zeigen, dass es eine Primzahl p mit p ≡ 1 (4) gibt, die von allen Zahlen p₁, …, p_n verschieden ist. Hierzu setzen wir

a = 2p₁ … p_n und b = a² + 1 = 4p₁²…p_n² + 1.

Dann ist b ≡ 1 (4). Ist b prim, so sind wir fertig. Andernfalls sei p ein Primteiler von b. Wegen b ≡ 0 (p) und b ≡ 1 (p_i) für alle i ≤ n ist p von allen p₁, …, p_n verschieden. Wir zeigen, dass p ≡ 1 (4). Hierzu rechnen wir modulo p:

Da p ein Teiler von a² + 1 ist, gilt a² ≡ −1 (p). Hieraus folgt:

(+) a ≢ 1 (p), a ≢ −1 (p), a³ ≢ 1 (p), a⁴ ≡ 1 (p).

Die Zahl a ist kein Vielfaches von p, da sonst b ≡ 1 (p) gelten würde. Nach dem Satz von Fermat ist also a^p − 1 ≡ 1 (p). Eine Division durch 4 mit Rest liefert ganze Zahlen q und r mit

p − 1 = q 4 + r und 0 ≤ r < 3.

Wegen a⁴ ≡ 1 (p) ist

1 ≡ a^p − 1 ≡ a^q4 + r ≡ a^q4 a^r ≡ (a⁴)^q a^r ≡ a^r (p).

Da a, a² und a³ nicht kongruent 1 modulo p sind, ist r = 0 und damit p − 1 durch 4 teilbar. Dies zeigt, dass p ≡ 1 (4).

Das Ergebnis ist ein Spezialfall von:

Satz (Dirichletscher Primzahlsatz)

Seien a, m ≥ 1 relativ prim. Dann gibt es unendlich viele Primzahlen p mit p ≡ a mod(m).

Der Satz kann mit Methoden der analytischen Zahlentheorie bewiesen werden.