ist selbst ein Quadratrest modulo , sodass wir im Folgenden annehmen, dass teilerfremd zu ist.
Wir benutzen das quadratische Reziprozitätsgesetz und zwar zunächst für den Fall . Dann ist
-
Die Nichtquadrate modulo sind . Wir müssen also eine Bedingung dafür finden, dass und gleichzeitig ist. Mit dem Chinesischen Restsatz ergibt sich die Kongruenzbedingung
-
Für den Fall ist
-
Die Quadrate modulo , die zugleich Einheiten sind
( ist ausgeschlossen),
sind . Wir müssen also eine Bedingung finden, dass und zugleich ist. Mit dem Chinesischen Restsatz ergibt sich die Kongruenzbedingung
-
Insgesamt hat man also die sieben Möglichkeiten
-
Da diese Zahlen
(bis auf )
teilerfremd zu
sind, folgt aus dem Satz von Dirichlet über arithmetische Progressionen, dass es unendlich viele solche Primzahlen gibt.