An extension to the Brun-Titchmarsh theorem

Abstract

The Siegel-Walfisz theorem states that for any B > 0, we have ∑/p≤x/p≡a(mod k) 1 ∼ x/φ(k) lox x for k ≤ log B x and (k, a) = 1. This only gives an asymptotic formula for the number of primes over an arithmetic progression for quite small moduli k compared with x. However, if we are only concerned about upper bound, we have the Brun-Titchmarsh theorem, namely for any 1 ≤ k < x, ∑/p≤x/p≡a(mod k) 1 ≪ x/φ(k) lox (x/k) In this article, we prove an extension to the Brun-Titchmarsh theorem on the number of integers, with at most s prime factors, in an arithmetic progression, namely ∑/y<n≤x+y ≡ a (mod k)ω (n) < s for any x, y > 0, s ≥ 1 and 1 ≤ k < x.In particular, for s ≤ log log (x/k), we have ∑/y<n≤x+y ≡ a (mod k)ω (n) < s 1 ≪ x/φ (k) log (x/k) (log log (x/k) + K)s-1/(s-1)! √ log log (x/k) + K and for any ε∈(0, 1) and s ≤ (1-ε) log log (x/k), we have. ∑/y<n≤x+y ≡ a (mod k)ω (n) < s 1 ≪ ε-1x/φ (k) log (x/k) (log log (x/k) +K)s-1/(s-1) !. © 2010. Published by Oxford University Press. All rights reserved.