# How constructive is Dirichlet on primes in progressions?

Is there a known elementary function bound in terms of $a,b,n$ for the $n$-th prime equal to $b$ modulo $a$ (coprime to $b$)?

Bounds on Linnik's constant answer this for the first prime in each progression. Is there a known analogue for an $n$-th prime in a progression? And I found some references on an error term for the prime number theorem for arithmetic progressions. But I don't see how to turn these into a construction for arbitrary $a,b,n$.

• One "construction" is simply to check all the numbers to see if they're prime. Is there even a better way to find the $n$th prime among all the primes? – Will Sawin Jul 29 '13 at 3:34
• The error term should give an explicit $x_0$ and an explicit positive constant $C \lt 1/\varphi(a)$ such that $|\{p \leq x : p \equiv b \pmod{a}\}| \geq Cx/\log x$ for all $x \geq x_0$. Then the first $x \geq x_0$ such that $Cx/\log x \geq n$ gives an upper bound on the $n$-th prime $b \pmod{a}$. – François G. Dorais Jul 29 '13 at 6:33
• Actually Will Sawin's comment is incorrect, though it led to improving the question. Brute force will find the $n$-th prime only if there is one! In other words, it is not a constructive technique unless you can bound how long the search needs to be. It seems you can bound it. – Colin McLarty Jul 29 '13 at 9:05
• @François G. Dorais: The versions of Dirichlet's theorem before Linnik's theorem did not give an explicit $C$, because the $C$ furnished by the proof depended on a possible Siegel zero for the modulus $a$. See also my response below. – GH from MO Jul 29 '13 at 9:19
• The case of primes $1 \pmod{n}$ is provable (with a much worse bound) in PA using the argument from mathoverflow.net/a/15221/2000 – François G. Dorais Jul 29 '13 at 13:23

Corollary 18.8 in Iwaniec-Kowalski's Analytic number theory shows the existence of an explicitly computable $L>3/2$ such that for $x>a^L$ and $(a,b)=1$, the number of primes less than $x$ and congruent to $b$ modulo $a$ is at least a constant times $\frac{x}{\varphi(a)\sqrt{a}\log x}$. So the $n$-th prime congruent to $b$ modulo $a$ is less than a constant times $a^L n\log (2n)$.
• I doubt you can find a constant multiple of $x$; surely it's $x/\log(x)$? – user25199 Jul 29 '13 at 8:16
• @Carl: You are right, I had the Chebyshev function $\psi(x,a,b)$ in mind rather than the prime counting function $\pi(x,a,b)$. I updated my response accordingly. – GH from MO Jul 29 '13 at 9:08