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$?
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\}$.
