Primes p for which p - 1 has a large prime factor - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T02:50:24Z http://mathoverflow.net/feeds/question/14796 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/14796/primes-p-for-which-p-1-has-a-large-prime-factor Primes p for which p - 1 has a large prime factor Vipul Naik 2010-02-09T19:00:00Z 2012-11-29T05:51:56Z <p>What are the best known density results and conjectures for primes <em>p</em> where <em>p - 1</em> has a large prime factor <em>q</em>, where by "large" I mean something greater than $\sqrt{p}$.</p> <p>The most extreme case is that of a safe prime (<a href="http://en.wikipedia.org/wiki/Safe_prime" rel="nofollow">Wikipedia entry</a>), which is a prime <em>p</em> 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).</p> <p>For the more general setting, where we are interested in the density of primes <em>p</em> for which <em>p - 1</em> has a large prime factor, the only general approach I am aware of is the <a href="http://en.wikipedia.org/wiki/Prime_number_theorem#The_prime_number_theorem_for_arithmetic_progressions" rel="nofollow">prime number theorem for arithmetic progressions</a>, and some of its strengthenings such as the <a href="http://en.wikipedia.org/wiki/Bombieri-Vinogradov_theorem" rel="nofollow">Bombieri-Vinogradov theorem</a> (conditional to the GRH), the (still open) <a href="http://en.wikipedia.org/wiki/Elliott-Halberstam_conjecture" rel="nofollow">Elliott-Halberstam conjecture</a>, 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 <em>q</em> and arbitrary <em>a</em> that is coprime to <em>q</em>.</p> <p>My question: can we expect qualitatively better results for the situation where <em>q</em> is prime and $a = 1$? Also, I am not interested in specifying <em>q</em> beforehand, so the existence of a <em>p</em> such that there exists <em>any</em> large prime <em>q</em> dividing $p - 1$ would be great. References to existing conjectures, conditional results, and unconditional results would be greatly appreciated.</p> http://mathoverflow.net/questions/14796/primes-p-for-which-p-1-has-a-large-prime-factor/14800#14800 Answer by Felipe Voloch for Primes p for which p - 1 has a large prime factor Felipe Voloch 2010-02-09T19:39:08Z 2010-02-15T03:39:06Z <p>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. </p> <p>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.</p> <p>Maybe an analytic number theorist will come along and give precise references.</p> <p><a href="http://en.wikipedia.org/wiki/Sieve%5Fmethods" rel="nofollow">Wikipedia - Sieve Methods</a></p> <p><a href="http://en.wikipedia.org/wiki/Linnik%27s%5Ftheorem" rel="nofollow">Wikipedia - Linnik's Theorem</a></p> http://mathoverflow.net/questions/14796/primes-p-for-which-p-1-has-a-large-prime-factor/14828#14828 Answer by Victor Miller for Primes p for which p - 1 has a large prime factor Victor Miller 2010-02-09T22:48:45Z 2010-02-15T02:41:58Z <p>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$.</p> <p>Etienne Fouvry, Th ́eor<code>eme de Brun-Titchmarsh; application au th ́eor</code>eme de Fermat, Invent. Math 79 (1985), 383–407. MR0778134 (86g:11052)</p> http://mathoverflow.net/questions/14796/primes-p-for-which-p-1-has-a-large-prime-factor/14833#14833 Answer by MRA for Primes p for which p - 1 has a large prime factor MRA 2010-02-10T00:22:54Z 2010-02-10T00:22:54Z <p>John A. Gordon introduced the notion of <em>strong primes</em> (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:</p> <ul> <li>John A. Gordon: <a href="http://link.springer.de/link/service/series/0558/bibs/0209/02090216.htm" rel="nofollow">"Strong Primes Are Easy to Find"</a>, Proceedings of EUROCRYPT '84, LNCS 209, Springer, 1985.</li> </ul> http://mathoverflow.net/questions/14796/primes-p-for-which-p-1-has-a-large-prime-factor/15089#15089 Answer by Mark Lewko for Primes p for which p - 1 has a large prime factor Mark Lewko 2010-02-12T08:33:51Z 2012-11-29T05:51:56Z <p>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</p> <p>$\sum_{p \leq x} \sum_{ x^{1/2}&lt; q \leq x : q | p+a} ln(q) = x/2 + O(x ln ln x / ln(x))$</p> <p>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).</p>