# Primes in arithmetic progressions above a given threshold

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$$?

• As a guide to intuition: methods in analytic number theory rarely establish just that there exists one object with certain properties—they tend to establish the existence of a bunch of such objects. (Usually because they say the number of objects is (main term) + (error term), and ensuring that the main term is strictly larger than the error term is usually only possible by ensuring that the main term is way larger than the error term.) So statements like Linnik's theorem actually come from proofs that lots of primes are present past $cb^L$, which suggests that this extension isn't hard. May 22, 2020 at 16:35

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