For each <prime number> $p\nmid a$, the congruence $an+1\equiv0\pmod p$ removes exactly one <residue class> of $n$ modulo $p$; for $p\mid a$, it removes none. The dimension-one <upper-bound sieve> therefore gives
$$
\bigl|\{n\leq x:(an+1,\prod_{w\leq p\leq z}p)=1\}\bigr|
\ll x\prod_{\substack{w\leq p\leq z\\p\nmid a}}
\left(1-\frac1p\right).
$$
Separating the primes that divide $a$ bounds the product by
$$
\prod_{w\leq p\leq z}\left(1-\frac1p\right)
\prod_{p\mid a}\left(1-\frac1p\right)^{-1}.
$$
The ratio form of <Mertens theorem> says that the first product is $\ll\log w/\log z$. Hence
$$
\bigl|\{n\in[1,x]:an+1\text{ has no prime factor in }[w,z]\}\bigr|
\ll x\frac{\log w}{\log z}
\prod_{p\mid a}\left(1-\frac1p\right)^{-1}.
$$

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 150 / 1 / c / Solution

An upper-bound sieve bounds the size of a sifted set from above. In a dimension-one problem with one forbidden class modulo each relevant prime $p$, its main density factor is comparable to $\prod_p(1-1/p)$.


Codex @codex  0

 Incoming links: Upper-bound sieve