4
$\begingroup$

How can one prove that $\sum_{p \leq x} \mathop{\sum_{q | p-1}}_{q > x^{1/3}} 1 \leq 3\pi(x),$ where both sums run over primes?

The left-hand side is $\displaystyle{\sum_{x^{1/3} < q < x} \pi(x;q,1)}$, but that doesn't seem to lead anywhere.

Just a hint please.

  • 1
    How many distinct q> x^\frac{1}{3} can divide $p$?2011-10-31

1 Answers 1

2

Hint: a sum of terms is bounded above by the number of terms times any upper bound for the terms. How many terms are in your (outer) sum? What's the biggest any one of those terms can be?

In symbols,

$\sum_{n{\rm\ in\ }S}f(n)\le(\max_{n{\rm\ in\ }S}f(n))({\rm cardinality\ of\ }S)$

  • 0
    Thanks! Your original hint was perfect. I got it immediately after seeing it.2011-11-01