MathOverflow is a question and answer site for professional mathematicians. 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

I'm wondering if analytic number theorists can prove results which have the following flavor:

So let $N$ be a large positive integer.

Q: Can you always find a prime number $p$ in the interval $(N, 3N/2)$ for which there exists an odd prime $q$ which divides $p-N$ with multiplicity exactly one?

If such a result can be found in the literature I would like to have a reference. I have just not the single idea about where to start in order to prove such a result.

I kind of remember vaguely that every large enough even integer $N$ can be written as $p_1+p_2p_3$ where the $p_i$'s are prime numbers which is not that far from what I'm asking for.

share|cite|improve this question
You're asking for primes p in arithmetic progressions (say with modulus the square of q)? This is much easier than approximations to Goldbach, unless the intervals are very short. – Charles Matthews Mar 20 '11 at 22:57
Following on Charles' comment, let $q$ be the smallest odd prime not dividing $N$, then there should be lots of primes $p$, $N\lt p\le 3N/2$, $N\equiv p\pmod q$, $N\not\equiv p\pmod{q^2}$. Time to rummage through the literature on primes in arithmetic progressions. – Gerry Myerson Mar 20 '11 at 23:31
Thanks Gerry for the explanation! – Hugo Chapdelaine Mar 21 '11 at 3:24
up vote 6 down vote accepted

The number of primes in $[N,3N/2]$ grows as $\frac{N}{\log N}$, while the number of powerful numbers in $[1,N/2]$ grows as $\sqrt{N}$, so pretty quickly you will find primes $p\in [N,3N/2]$ so that $p-N$ is not powerful, i.e. has a prime divisor which has multiplicity 1.

share|cite|improve this answer
Also note that the asymptotic results needed come with effective constants so this will hold for all $N>c$ for some $c$ we can compute. – Gjergji Zaimi Mar 21 '11 at 0:36
In particular, combining Golomb 1970 with Rosser 1941 allows an explicit (and small) bound on allowable N. – Charles Mar 21 '11 at 0:39
@Gjergji Zaimi: Sorry, didn't see your comment until I added mine. Yes, same idea. – Charles Mar 21 '11 at 0:40
Thanks a lot Gjergji, I might need some effective constant at some point. – Hugo Chapdelaine Mar 21 '11 at 3:32

I cannot think of an exact reference but the result you are looking for can be obtained as follows:

The number of primes $p\in(N,2N]$ such that $p-N$ is divisible by the square of a prime $q>\log N$ is $\ll N/\log^2N$ (this follows by any upper bound sieve). Also, the number of primes $p\in(N,2N]$ such that $p-N$ is composed only of prime numbers $\le\log N$ is at most the number of integers $m\le N$ which are $\log N$-smooth (i.e. have only only prime factors $\le\log N$). The number of such integers is at most $N^{1-1/2\log\log N}\ll N/\log^2N$ (see for example Theorem 1, Chapter III.5, in Tenenbaum's book "Introduction to analytic and probabilistic number theory"). So

$$|\{N < p\le2N:\exists q~{\rm prime}~{\rm with}~q>\log N~{\rm and}~q\|p-N\}|=\frac N{\log N}+O\Bigl(\frac N{\log^2N}\Bigr).$$

share|cite|improve this answer

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.