Siegel–Walfisz theorem

For fixed $A,C>0$,uniformly for $q\le {\log }^{C}x$ and $(a,q)=1$. The implied constant may be ineffective. This small-modulus input complements the large sieve in the proof of the Bombieri–Vinogradov theorem.

For $(a,q)=1$ and $q\le {\log }^{A}N$, apply the Siegel–Walfisz theorem to every reduced residue class with error exponent $A+B+2$. The main terms sum to $N{c}_q(a)/\phi (q)$, where the Ramanujan sum satisfies $c_q(a)=\mu (q)$ for coprime $a,q$. Nonunits with nonzero Von Mangoldt function are powers of primes dividing $q$ and contribute at most $\omega (q)\log N$, which is absorbed by the error. For arbitrary $a$, the correct main term is $N{c}_q(a)/\phi (q)$; the reduced numerator hypothesis cannot be omitted.