Linnik's theorem

Statement

There exist constants $C,L$ such that the following holds:

For any natural number $D$ and any integer $a$ that is relatively prime to $D$, there exists a prime $p\leq CD^{L}$ such that $p\equiv a{\pmod {D}}$.

In other words, the first Dirichlet prime for any congruence class relatively prime to the modulus is bounded by a polynomial in the modulus.

Heath-Brown has shown that we can take $L\leq 5.5$.

Relation with other facts

Stronger facts and conjectures

• The generalized Riemann hypothesis implies that any value of $L>2$ (with suitably chosen $C$) works. In other words, the first Dirichlet prime in any congruence class is $O(D^{2+\epsilon })$.
• Chowla's conjecture on the first Dirichlet prime states that we can use any $L>1$, i.e., the first Dirichlet prime is $O(D^{1+\epsilon })$.
• Heath-Brown's conjecture on the first Dirichlet prime states that the first prime is $O(D(\log D)^{2})$.