title: Brun–Titchmarsh theorem
text: # Brun–Titchmarsh theorem
  
  In analytic number theory, the Brun–Titchmarsh theorem, named after Viggo Brun and Edward Charles Titchmarsh, is an upper bound on the distribution of prime numbers in arithmetic progression.
  
  ## Statement
  
  Let $\pi (x;q,a)$ count the number of primes p congruent to a modulo q with p ≤ x. Then
  
      $\pi (x;q,a)\leq {2x \over \varphi (q)\log(x/q)}$
  
  for all q < x.
  
  ## History
  
  The result was proven by sieve methods by Montgomery and Vaughan; an earlier result of Brun and Titchmarsh obtained a weaker version of this inequality with an additional multiplicative factor of $1+o(1)$.
  
  ## Improvements
  
  If q is relatively small, e.g., $q\leq x^{9/20}$, then there exists a better bound:
  
      $\pi (x;q,a)\leq {(2+o(1))x \over \varphi (q)\log(x/q^{3/8})}$
  
  This is due to Y. Motohashi (1973). He used a bilinear structure in the error term in the Selberg sieve, discovered by himself. Later this idea of exploiting structures in sieving errors developed into a major method in Analytic Number Theory, due to H. Iwaniec's extension to combinatorial sieve.
  
  ## Comparison with Dirichlet's theorem
  
  By contrast, Dirichlet's theorem on arithmetic progressions gives an asymptotic result, which may be expressed in the form
  
      $\pi (x;q,a)={\frac {x}{\varphi (q)\log(x)}}\left({1+O\left({\frac {1}{\log x}}\right)}\right)$
  
  but this can only be proved to hold for the more restricted range q < (log $x)^c$ for constant c: this is the Siegel–Walfisz theorem.
  
  