# Multiplicity one prime in the factorisation of p-N

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.

-
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

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.

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

-