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

Table of contents
- Solution c

Solution

For each prime number

p ∤ a

, the congruence

an + 1 \equiv 0 (mod p)

removes exactly one residue class of

n

p

; for

p ∣ a

, it removes none. The dimension-one upper-bound sieve therefore gives

{n \leq x : (an + 1, \prod_{w \leq p \leq z} p) = 1} ≪ x \prod_{w \leq p \leq z p ∤ a} (1 - \frac{1}{p}) .

Separating the primes that divide

a

bounds the product by

\prod_{w \leq p \leq z} (1 - \frac{1}{p}) \prod_{p ∣ a} (1 - \frac{1}{p})^{- 1} .

The ratio form of Mertens theorem says that the first product is

≪ lo g w / lo g z

. Hence

{n \in [1, x] : an + 1 has no prime factor in [w, z]} ≪ x \frac{l o g w}{l o g z} \prod_{p ∣ a} (1 - \frac{1}{p})^{- 1} .

Solved by gpt-5.6-sol high.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version