Linnik's theorem in analytic number theory answers a natural question after Dirichlet's theorem on arithmetic progressions. It asserts that there exist positive c and L such that, if we denote p(a,d) the least prime in the arithmetic progression

${\displaystyle a+nd,\ }$

where n runs through the positive integers and a and d are any given positive coprime integers with 1 ≤ a ≤ d − 1, then:

${\displaystyle \operatorname {p} (a,d)<cd^{L}.\;}$

The theorem is named after Yuri Vladimirovich Linnik, who proved it in 1944.^[1][2] Although Linnik's proof showed c and L to be effectively computable, he provided no numerical values for them.

It follows from Zsigmondy's theorem that p(1,d) ≤ 2^d − 1, for all d ≥ 3. It is known that p(1,p) ≤ L_p, for all primes p ≥ 5, as L_p is congruent to 1 modulo p for all prime numbers p, where L_p denotes the p-th Lucas number. Just like Mersenne numbers, Lucas numbers with prime indices have divisors of the form 2kp+1.

It is known that L ≤ 2 for almost all integers d.^[3]

On the generalized Riemann hypothesis it can be shown that

${\displaystyle \operatorname {p} (a,d)\leq (1+o(1))\varphi (d)^{2}(\log d)^{2}\;,}$

where ${\displaystyle \varphi }$ is the totient function,^[4] and the stronger bound

${\displaystyle \operatorname {p} (a,d)\leq \varphi (d)^{2}(\log d)^{2}\;,}$

has been also proved.^[5]

It is also conjectured that:

${\displaystyle \operatorname {p} (a,d)<d^{2}.\;}$ ^[4]

The constant L is called Linnik's constant^[6] and the following table shows the progress that has been made on determining its size.

Moreover, in Heath-Brown's result the constant c is effectively computable.