Bombieri–Vinogradov theorem

Let x and Q be any two positive real numbers with :x^{1/2}\log^{-A}x \leq Q \leq x^{1/2}. Then :\sum_{q\leq Q}\max_{y\le x}\max_{1\le a\le q\atop (a,q)=1}\left|\psi(y;q,a)-{y\over\varphi(q)}\right|=O\left(x^{1/2}Q(\log x)^5\right)\!. Here \varphi(q) is the Euler totient function, which is the number of summands for the modulus q, and :\psi(x;q,a)=\sum_{n\le x\atop n\equiv a\bmod q}\Lambda(n), where \Lambda denotes the von Mangoldt function. A verbal description of this result is that it addresses the error term in the prime number theorem for arithmetic progressions, averaged over the moduli q up to Q. For a certain range of Q, which are around \sqrt x if we neglect logarithmic factors, the error averaged is nearly as small as \sqrt x. This is not obvious, and without the averaging is about of the strength of the Generalized Riemann Hypothesis (GRH). ==See also==