# Brun-Titchmarsh theorem

For coprime integers $q$ and $a$, let $\pi(x;a,q)$ denote the number of primes not exceeding $x$ that are congruent to $a \pmod q$. Using analytic methods of the theory of $L$-functions [a8], one can show that the asymptotic formula (Dirichlet's theorem on arithmetic progressions) $$\pi(x;a,q) = \frac{x}{\phi(q)\log(x)} \left({1 + O\left(\frac{1}{\log x}\right)}\right)$$ holds uniformly for $q < \log^A x$, where $A$ is an arbitrary positive constant: this is the Siegel-Walfisz theorem. It is desirable to extend the validity range for $q$ of this formula, in view of its applications to classical problems. The generalized Riemann hypothesis (cf. Riemann hypotheses) is not capable of providing any information for $q > x^{1/2}$.
In contrast, a simple application of a sieve method [a8] leads to an upper bound which gives the correct order of magnitude of $\pi(x;a,q)$ for all $q < x^{1-\epsilon}$, where $\epsilon$ is an arbitrary positive constant. Because of its uniformity in $q$, an inequality of this type turns out to be very useful [a3], [a5], [a8]; it is known as the Brun–Titchmarsh theorem. By a sophisticated argument, [a6], one finds that $$\pi(x;a,q) \le \frac{2x}{\phi(q)\log(x/q)}$$ for all $q < x$. The constant $2$ possesses a significant meaning in the context of sieve methods [a2], [a7]. By adapting the Brun–Titchmarsh theorem [a1], [a4], if necessary, it is possible to sharpen the above bound in various ranges for $q$.