# Primes in arithmetic progressions

Denote by $\pi(x,a,q)$ the number of primes $p\le x$ of the form $p=qk+a$ and $E(x,a,q)=\phi(q)^{-1}\mathrm{Li}(x)-\pi(x,a,q)$. What is the strongest conjectured bound on $E(x,a,q)$ in terms of $x,q$?

-
$x/\log x$ is the wrong approximation. You need to replace it with $Li(x) = \int_2^x dt/\log t$. Then the dependence on $x$ on the error term will be $x^{1/2}\log x$ by GRH. I am sure what dependence on $q$ will be, but an expert will probably answer you. –  Felipe Voloch Jan 5 '11 at 22:46
I meant to say "I'm not sure"... –  Felipe Voloch Jan 5 '11 at 22:47
Related: mathoverflow.net/questions/834/… –  David Speyer Jan 5 '11 at 23:13

As Felipe notes, the main term should be li(x)/\phi(q). Replacing this in your definition of $E(x,a,q)$ above we have that, the best that is know even on the GRH is that $E(x,a,q) = O(x^{1/2}\log x)$. This estimate doesn't get better when $q$ is large (compared to $x$) and a lot more is believed to be true. For instance Montgomery conjectures that $E(x,a,q) = O_{\epsilon}( x^{1/2+\epsilon}/ q^{1/2})$ (see Conjecture 13.9 in his book on Multiplicative Number Theory).
Edit: This is really is the best one can hope for, as Friedlander and Granville have shown (using Maier's Matrix Method) that the $O_{\epsilon}(x^{1/2+\epsilon})$ cannot be replaced with a term of the form $O_{A}(x^{1/2} \log^{A}(x))$.