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\le C{D}^L$ such that $p\equiv a(\mathrm{mod}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\le 5.5$.

Relation with other facts

Stronger facts

• 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+ϵ})$.
• 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+ϵ})$.
• Heath-Brown's conjecture on the first Dirichlet prime states that the first prime is $O(D(\log D{)}^2)$.