On the greatest prime factor of 𝑝-1 with effective constants

Harman, G.

doi:10.1090/S0025-5718-05-01749-7

On the greatest prime factor of $p-1$ with effective constants

Author: G. Harman
Journal: Math. Comp. 74 (2005), 2035-2041
MSC (2000): Primary 11N13
DOI: https://doi.org/10.1090/S0025-5718-05-01749-7
Published electronically: February 16, 2005
MathSciNet review: 2164111
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $p$ denote a prime. In this article we provide the first published lower bounds for the greatest prime factor of $p-1$ exceeding $(p-1)^{\frac 12}$ in which the constants are effectively computable. As a result we prove that it is possible to calculate a value $x_0$ such that for every $x > x_0$ there is a $p < x$ with the greatest prime factor of $p-1$ exceeding $x^{\frac 35}$. The novelty of our approach is the avoidance of any appeal to Siegel’s Theorem on primes in arithmetic progression.

M. Agrawal, N. Kayal and N. Saxena, PRIMES is in P, http://www.cse.iitk.ac.in/primality.pdf.

R. C. Baker and G. Harman, The Brun-Titchmarsh theorem on average, Analytic number theory, Vol. 1 (Allerton Park, IL, 1995) Progr. Math., vol. 138, Birkhäuser Boston, Boston, MA, 1996, pp. 39–103. MR 1399332

R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361. MR 1610553, DOI https://doi.org/10.4064/aa-83-4-331-361

D. Bernstein, Proving primality after Agrawal-Kayal-Saxena, http://cr.yp.to/papers/html#aks.

E. Bombieri, J. B. Friedlander, and H. Iwaniec, Primes in arithmetic progressions to large moduli. III, J. Amer. Math. Soc. 2 (1989), no. 2, 215–224. MR 976723, DOI https://doi.org/10.1090/S0894-0347-1989-0976723-6

Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931

J.-M. Deshouillers and H. Iwaniec, On the Brun-Titchmarsh theorem on average, Topics in classical number theory, Vol. I, II (Budapest, 1981) Colloq. Math. Soc. János Bolyai, vol. 34, North-Holland, Amsterdam, 1984, pp. 319–333. MR 781145

Kevin Ford, Vinogradov’s integral and bounds for the Riemann zeta function, Proc. London Math. Soc. (3) 85 (2002), no. 3, 565–633. MR 1936814, DOI https://doi.org/10.1112/S0024611502013655

Morris Goldfeld, On the number of primes $p$ for which $p+a$ has a large prime factor, Mathematika 16 (1969), 23–27. MR 244176, DOI https://doi.org/10.1112/S0025579300004575

H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134. MR 374060, DOI https://doi.org/10.1112/S0025579300004708

Yoichi Motohashi, A note on the least prime in an arithmetic progression with a prime difference, Acta Arith. 17 (1970), 283–285. MR 268131, DOI https://doi.org/10.4064/aa-17-3-283-285

N. M. Timofeev, The Vinogradov-Bombieri theorem, Mat. Zametki 38 (1985), no. 6, 801–809, 956 (Russian). MR 823418

R. C. Vaughan, An elementary method in prime number theory, Acta Arith. 37 (1980), 111–115. MR 598869, DOI https://doi.org/10.4064/aa-37-1-111-115