3
$\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
    I'm having trouble seeing why $\max_{p\le x} \#\{q:q|(p-1),\; q>x^{1/3}\}\le3$, and based on the lack of votes I'd say I'm not alone...2011-10-31
  • 0
    @anon, remember, $q$ is running over primes. If primes $q_1,q_2,q_3$ all exceed $x^{1/3}$, can they all divide a number which is less than $x$?2011-10-31
  • 0
    Ah, of course. That was simple.2011-10-31
  • 0
    Thanks! Your original hint was perfect. I got it immediately after seeing it.2011-11-01