Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
How many distinct $q> x^\frac{1}{3}$ can divide $p$? – N. S. Oct 31 '11 at 2:44
up vote 1 down vote accepted

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)$$

share|cite|improve this answer
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... – anon Oct 31 '11 at 4:15
@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$? – Gerry Myerson Oct 31 '11 at 5:45
Ah, of course. That was simple. – anon Oct 31 '11 at 5:47
Thanks! Your original hint was perfect. I got it immediately after seeing it. – maxpower Nov 1 '11 at 4:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.