= Solution
Write the progression <integers> as $n=a+qm$. Their $m$ values lie in an interval of length at most $N/q+1$. For every <prime> $p\nmid q$, primality forbids the unique residue $m\equiv-aq^{-1}\pmod p$; <primes> dividing $q$ impose no restriction because $(a,q)=1$.
Choose $Q=\max(2,\lfloor\sqrt{N/q}\rfloor)$. The selected <primes> exceed $M>N$, hence exceed these sieving <primes>. The uniform coprime-denominator estimate just proved yields
$$
|S|\ll\frac{N/q+Q^2+1}{(\varphi(q)/q)\log(2Q)}
\ll\frac{N}{\varphi(q)\log(N/q)}.
$$
The assumption $N\ge q^{2+\delta}$ implies $\log(N/q)\ge\frac{1+\delta}{2+\delta}\log N\ge\frac12\log N$. Therefore
$$
\boxed{\pi(M+N;q,a)-\pi(M;q,a)\ll\frac{N}{\varphi(q)\log N}.}
$$
Endpoint and bounded small-parameter corrections are again absorbed. The proof supplies the more informative short-interval progression bound before using the given size hypothesis.
Back to article page
