Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 23 / 5 / d / ii / 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 -a{q}^{-1}(\mathrm{mod}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 yieldsThe assumption $N\ge q^{2+\delta }$ implies $\log (N/q)\ge \frac{1+\delta }{2+\delta }\log N\ge \frac{1}{2}\log N$. ThereforeEndpoint and bounded small-parameter corrections are again absorbed. The proof supplies the more informative short-interval progression bound before using the given size hypothesis.