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}

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}

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}

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

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}

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.