 Brun–Titchmarsh theorem

For $x>q$ and $(a,q)=1$, the prime-counting function in an arithmetic progression satisfiesThe denominator involves the Euler totient function and the length-to-modulus ratio. In particular, for $q\le x^{1-\eta }$ with fixed $\eta >0$, this is $O_{\eta }(x/(\varphi (q)\log x))$.

The Brun–Titchmarsh theorem is a result in analytic number theory that provides an asymptotic estimate for the number of primes in an arithmetic progression. More specifically, it addresses the distribution of prime numbers in the form \( a + nd \), where \( a \) and \( d \) are coprime integers, and \( n \) ranges over the natural numbers.