Given co-prime $a,b$, Dirichlet's theorem states that there are infinitely many primes in the arithmetic progression $M = \{ a + bn : n \in \mathbb N\}$. Linnik's theorem asserts that the first such prime is bounded by $cb^L$ for positive constants $c,L$.


Let $M\_t = M \cap \{ n > t : n\in \mathbb N\}$ for some positive threshold $t$. Is there an analogue of Linnik's theorem giving bounds for the first prime in $M\_t$, preferably polynomial in $b$ and $t$?



Primes in arithmetic progressions above a given threshold
If $1 ≤ t ≤ c\_1 b^{L\_1}$ for some positive, absolute, and effectively computable constants $c\_1,L$, then Linnik's theorem implies that the least prime in $M\_t$ is less than $c\_2 b^{L\_2}$ for some constants $c\_2,L\_2$.


If $t$ is larger than a polynomial in $b$, then we use a stronger quantitative form of Linnik's theorem: There exist positive constants $c\_2,c\_3,L\_2$ (each absolute and effectively computable) such that if $t>c\_2 b^{L\_2}$, then


$\displaystyle\#\{t<p≤ 2t\colon p\equiv a\pmod{b}\}\geq c\_3 \frac{t}{\sqrt{b}~\varphi(b)\log t}$,


where $\varphi(b)$ is Euler's totient function. (This is proved in Chapter 18 of Iwaniec and Kowalski, for instance.) Thus there would exist a prime in between $t$ and $2t$. We combine both cases and conclude that the least prime in $M\_t$ is bounded by $\max\{c\_2 b^{L\_2},2t\}$.


