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_{ x^{1/2}< q \leq x : q | p+a} ln(q) = x/2 + O(x ln ln x / ln(x))$

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 x/ 2ln(x).

  • $\begingroup$ 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). $\endgroup$ – Greg Martin Mar 4 '11 at 19:48
  • $\begingroup$ 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$. $\endgroup$ – Johan Andersson Nov 26 '12 at 13:26
  • $\begingroup$ Johan, thanks! I've adjusted the text. $\endgroup$ – 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 ́eoreme de Brun-Titchmarsh; application au th ́eoreme de Fermat, Invent. Math 79 (1985), 383–407. MR0778134 (86g:11052)

  • $\begingroup$ I didn't understand. Did you leave the statement incomplete? What is the conclusion about the relative density? $\endgroup$ – Vipul Naik Feb 9 '10 at 22:56
  • $\begingroup$ ..."is positive"? $\endgroup$ – David Hansen Feb 9 '10 at 23:06
  • $\begingroup$ 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. $\endgroup$ – Vipul Naik Feb 10 '10 at 1:07
  • $\begingroup$ @Vipul: I'm sure that I mean $\alpha > 0.6687$ since we're interested in $p-1$ have a large prime factor. $\endgroup$ – Victor Miller Feb 10 '10 at 3:31
  • 1
    $\begingroup$ @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$. $\endgroup$ – 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:


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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