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

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11N13

Retrieve articles in all journals with MSC (2000): 11N13

Additional Information

**G. Harman**

Affiliation:
Department of Mathematics, Royal Holloway University of London, Egham, Surrey TW20 0EX, United Kingdom

Email:
G.Harman@rhul.ac.uk

Received by editor(s):
March 19, 2004

Received by editor(s) in revised form:
August 16, 2004

Published electronically:
February 16, 2005

Article copyright:
© Copyright 2005
American Mathematical Society