Aussage über die Existenz unendlich vieler Primzahlen in arithmetischen Progressionen:

Sind a, m ∈ ℕ teilerfremd, so gibt es unendlich viele Primzahlen der Form

\begin{eqnarray}p=mk+a\end{eqnarray}

mit einer ganzen Zahl k ≥ 0.

Manche Spezialfälle dieses Satzes sind nicht schwer zu beweisen. Beispielsweise sind alle Primzahlen ≠ 2 ungerade, befinden sich also in der Restklasse 1 mod 2, d.i. in der arithmetischen Progression

\begin{eqnarray}\{2k+1:k\in {\mathbb{N}}\}.\end{eqnarray}

Der Beweis des Satzes von Euklid über Primzahlen läßt sich leicht so modifizieren, daß man daraus folgenden Satz erhält:

Jede der Restklassen

\begin{eqnarray}-1\,\,\mathrm{mod}\,3,\,\,-1\,\,\mathrm{mod}\,4,\,\,\,-1\,\,\mathrm{mod}\,6\end{eqnarray}

enthält unendlich viele Primzahlen.

Auch für verschiedene andere arithmetische Progressionen gibt es (verhältnismäßig) einfache Beweise, z. B. 5k ± 2, 12k − 1, und viele andere.

Euler vermutete den Spezialfall a = 1 (und beliebiges m > 1) des Dirichletschen Primzahlsatzes. Den allgemeinen Fall versuchte Legendre 1785 zu beweisen. Dirichlet gab 1837 den ersten vollständigen Beweis, der einige Hilfsmittel aus der Analysis benutzt.

Eine Hauptschwierigkeit im Dirichletschen Zugang ist der Beweis von

\begin{eqnarray}\displaystyle \sum _{n=1}^{\infty }\frac{\chi (n)}{n}\ne 0,\end{eqnarray}

wobei χ ein Charakter modulo m ist; diese Aussage nennt man das Nichtverschwinden der Dirichletschen L-Reihen L(s, χ) für s = 1. Aus (1) folgt schließlich die Divergenz der Reihe

\begin{eqnarray}\displaystyle \sum _{p\equiv a\,\mathrm{mod}\,m}\frac{1}{p},\end{eqnarray}

was sogar eine stärkere Aussage ist als der oben formulierte Dirichletsche Primzahlsatz.

Mit Hilfe des Primzahlsatzes kann man noch etwas mehr über die Verteilung der Primzahlen in einer Restklasse a mod m beweisen:

Seien a, m teilerfremde ganze Zahlen, m > 1, und bezeichne π_m(x) die Anzahl der Primzahlen p ≤ x mit der Eigenschaft p ≡ a mod m.

Dann sind die Funktionen π_m(x) und

\begin{eqnarray}{f}_{m}(x) := \frac{1}{\phi (m)}\cdot \frac{x}{\mathrm{log} x}\end{eqnarray}

für x → ∞ asymptotisch gleich. Hierbei bezeichnet φ die Eulersche φ-Funktion.

Die Tatsache, daß die Funktion f_m nicht von a abhängt, bedeutet, daß die Primzahlen innerhalb der primen Restklassen modulo m in gewissem Sinne gleichverteilt sind.