# Primes $p$ for which $p-1$ has a large prime factor

What are the best known density results and conjectures for primes $$p$$ where $$p-1$$ has a large prime factor $$q$$, where by "large" I mean something greater than $$\sqrt{p}$$.

The most extreme case is that of a safe prime (Wikipedia entry), which is a prime $$p$$ such that $$(p - 1)/2$$ is also a prime (the smaller prime is called a Sophie Germain prime). I believe it is conjectured (and not yet proved) that infinitely many safe primes exist, and that the density is roughly $$c/\log^2 n$$ for some constant $$c$$ (as it should be from a probabilistic model).

For the more general setting, where we are interested in the density of primes $$p$$ for which $$p-1$$ has a large prime factor, the only general approach I am aware of is the prime number theorem for arithmetic progressions, and some of its strengthenings such as the Bombieri-Vinogradov theorem (conditional to the GRH), the (still open) Elliott-Halberstam conjecture, Chowla's conjecture on the first Dirichlet prime, and some partial results related to this conjecture. All of these deal with the existence of primes $$p \equiv a \pmod q$$ for arbitrary $$q$$ and arbitrary $$a$$ that is coprime to $$q$$.

My question: can we expect qualitatively better results for the situation where $$q$$ is prime and $$a = 1$$? Also, I am not interested in specifying $$q$$ beforehand, so the existence of a $$p$$ such that there exists any large prime $$q$$ dividing $$p-1$$ would be great. References to existing conjectures, conditional results, and unconditional results would be greatly appreciated.

See "On the number of primes $$p$$ for which $$p+a$$ has a large prime factor." (Goldfeld, Mathematika 16 1969 23--27.) Using Bombieri-Vinogradov he proves, for a fixed integer $$a$$, that

$$\sum_{p \leq x} \sum_{\substack{ x^{1/2}< q \leq x \\ q | p+a}} \ln q = \frac{x}{2} + O\left(\frac{x \ln \ln x}{ \ln x} \right)$$

where the summation is over $$p$$ and $$q$$ prime. Note that this implies that the number of primes $$p$$ less than $$x$$ such that $$p-1$$ has a prime factor greater than $$p^{1/2}$$ is asymptotically at least $$\frac{x}{2\ln x}$$.

• Strange - the density of integers $n$ that have a prime factor greater than $n^{1/2}$ is $\log 2$ by results on friable (or smooth) numbers (see the Dickman rho function). I would think that the density of such shifted primes is also $\log 2$. I have proved this subject to a version of the Hardy-Littlewood prime tuples conjecture (see my J. Number Th. paper of 2002). – Greg Martin Mar 4 '11 at 19:48
• Mark, your conclusion that the number of primes less than x such that p-1 has a prime factor larger than $\sqrt(p)$ is asymptotic to x/(2ln(x)) is not correct. Note that we have a log(q) factor in the result not log(p) and for the relevant range of q we have $\log(p)/2 \leq \log(q) \leq \log(p)$ and they are not asymptotically equal. Greg is correct that the density should be $\log 2$. – Johan Andersson Nov 26 '12 at 13:26
• Johan, thanks! I've adjusted the text. – Mark Lewko Nov 29 '12 at 5:52

I believe that sieve methods (in particular methods similar to Chen's result on "almost" Goldbach and twin primes) should give infinitely primes $p$ such $(p-1)/2$ is a product of two primes. That's more than what you asked.

Wikipedia quotes a result of Bombieri-Friedlander-Iwaniec stating that Linnik's constant is $2$ for almost all moduli. If the same is true for infinitely many prime moduli $q$, then you are in business. A prime $p \equiv 1 \mod q, p \ll q^2$ is what you want.

Maybe an analytic number theorist will come along and give precise references.

Wikipedia - Sieve Methods

Wikipedia - Linnik's Theorem

Fouvry showed that the relative density is positive of primes $$p$$ for which the largest prime factor of $$p+a$$ is $$\ge p^{\alpha}$$ for $$\alpha \approx .6687$$.

Etienne Fouvry, Théorème de Brun-Titchmarsh: application au théorème de Fermat, Invent. Math 79 (1985), 383–407. MR0778134 (86g:11052)

• I didn't understand. Did you leave the statement incomplete? What is the conclusion about the relative density? – Vipul Naik Feb 9 '10 at 22:56
• ..."is positive"? – David Hansen Feb 9 '10 at 23:06
• Did you mean $\alpha \le 0.6687$ above instead of $\alpha > 0.6687$? The larger the $\alpha$, the smaller the density, and the paper you've quoted also seems to suggest that. – Vipul Naik Feb 10 '10 at 1:07
• @Vipul: I'm sure that I mean $\alpha > 0.6687$ since we're interested in $p-1$ have a large prime factor. – Victor Miller Feb 10 '10 at 3:31
• @DavidHansen: perhaps I didn't state it clearly enough. Fouvry showed that there is an $\alpha$ which is approximately 0.6687 so that for a fixed $a \ne 0$ the set $\{p \text{ prime}: P(p+a) \ge p^{\alpha} \}$ has positive density in the set of all primes, where $P(n)$ denotes the larges prime factor dividing $n$. Bigger values of $\alpha$ are better. The post alluding to a result of Goldfeld had $\alpha = \frac 12$. – Victor Miller Feb 15 '10 at 3:50

John A. Gordon introduced the notion of strong primes (try Wikipedia) which, beside other requirements, are primes $p$ satisfying $p \equiv 1 \mod r$ for some large prime $r$ of about the same size as $p$. In the following paper, it has been shown how to construct strong primes of arbitrary bit size efficiently and with high probability: