7 On the largest prime factor of the Mersenne
numbers
Kevin Ford
Department of Mathematics
The University of Illinois at Urbana-Champaign Urbana
Champaign, IL 61801, USA
ford@math.uiuc.edu
Florian Luca
Instituto de Matemáticas
Universidad Nacional Autonoma de México
C.P. 58089, Morelia, Michoacán, México
fluca@matmor.unam.mx
Igor E. Shparlinski
Department of Computing
Macquarie University
Sydney, NSW 2109, Australia
igor@ics.mq.edu.au
Abstract
Let P (k) be the largest prime factor of the positive integer k. In
this paper, we prove that the series
(log n)α
P (2n − 1)
is convergent for each constant α < 1/2, which gives a more precise
form of a result of C. L. Stewart of 1977.
http://arxiv.org/abs/0704.1327v1
1 Main Result
Let P (k) be the largest prime factor of the positive integer k. The quantity
P (2n− 1) has been investigated by many authors (see [1, 3, 4, 10, 11, 12, 14,
15, 16]). For example, the best known lower bound
P (2n − 1) ≥ 2n+ 1, for n ≥ 13
is due to Schinzel [14]. No better bound is known even for all sufficiently
large values of n.
C. L. Stewart [15, 16] gave better bounds provided that n satisfies certain
arithmetic or combinatorial properties. For example, he showed in [16], and
this was also proved independently by Erdős and Shorey in [4], that
P (2p − 1) > cp log p
holds for all sufficiently large prime numbers p, where c > 0 is an absolute
constant and log is the natural logarithm. This was an improvement upon a
previous result of his from [15] with (log p)1/4 instead of log p. Several more
results along these lines are presented in Section 3.
Here, we continue to study P (2n − 1) from a point of view familiar to
number theory which has not yet been applied to P (2n − 1). More precisely,
we study the convergence of the series
(logn)α
P (2n − 1)
for some real parameter α.
Our result is:
Theorem 1. The series σα is convergent for all α < 1/2.
The rest of the paper is organized as follows. We introduce some notation
in Section 2. In Section 3, we comment on why Theorem 1 is interesting and
does not immediately follow from already known results. In Section 4, we
present a result C. L. Stewart [16] which plays a crucial role in our argument.
Finally, in Section 5, we give a proof of Theorem 1.
2 Notation
In what follows, for a positive integer n we use ω(n) for the number of distinct
prime factors of n, τ(n) for the number of divisors of n and ϕ(n) for the Euler
function of n. We use the Vinogradov symbols ≫, ≪ and ≍ and the Landau
symbols O and o with their usual meaning. The constants implied by them
might depend on α. We use the letters p and q to denote prime numbers.
Finally, for a subset A of positive integers and a positive real number x we
write A(x) for the set A∩ [1, x].
3 Motivation
In [16], C. L. Stewart proved the following two statements:
A. If f(n) is any positive real valued function which is increasing and f(n) →
∞ as n → ∞, then the inequality
P (2n − 1) >
n(log n)2
f(n) log log n
holds for all positive integers n except for those in a set of asymptotic
density zero.
B. Let κ < 1/ log 2 be fixed. Then the inequality
P (2n − 1) ≥ C(κ)
ϕ(n) logn
2ω(n)
holds for all positive integers n with ω(n) < κ log log n, where C(κ) > 0
depends on κ.
Since for every fixed ε > 0 we have
log logn
n(log n)1+ε
the assertion A above, taken with f(n) = (log n)ε for fixed some small posi-
tive ε < 1− α, motivates our Theorem 1. However, since C. L. Stewart [16]
gives no analysis of the exceptional set in the assertion A (that is, of the size
of the set of numbers n ≤ x such that the corresponding estimate fails for a
particular choice of f(n)), this alone does not lead to a proof of Theorem 1.
In this respect, given that the distribution of positive integers n having a
fixed number of prime factorsK < κ log log n is very well-understood starting
with the work of Landau and continuing with the work of Hardy and Ramanu-
jan [6], it may seem that the assertion B is more suitable for our purpose.
However, this is not quite so either since most n have ω(n) > (1−ε) log logn
and for such numbers the lower bound on P (2n − 1) given by B is only
of the shape ϕ(n)(log n)1−(1−ε) log 2 and this is not enough to guarantee the
convergence of series (1) even with α = 0.
Conditionally, Murty and Wang [11] have shown the ABC-conjecture
implies that P (2n − 1) > n2−ε for all ε > 0 once n is sufficiently large with
respect to ε. This certainly implies the conditional convergence of series (1)
for all fixed α > 0. Murata and Pomerance [10] have proved, under the
Generalized Riemann Hypothesis for various Kummerian fields, that the in-
equality P (2n − 1) > n4/3/ log logn holds for almost all n, but they did not
give explicit upper bounds on the size of the exceptional set either.
4 Main Tools
As we have mentioned in Section 3, neither assertion A nor B of Section 3
are directly suitable for our purpose. However, another criterion, implicit in
the work of C. L. Stewart [16] and which we present as Lemma 2 below (see
also Lemma 3 in [10]), plays an important role in our proof.
Lemma 2. Let n ≥ 2, and let d1 < · · · < dℓ be all ℓ = 2
ω(n) divisors of n
such that n/di is square-free. Then for all n > 6,
#{p | 2n − 1 : p ≡ 1 (mod n)} ≫
log logP (2n − 1)
where
∆(n) = max
i=1,...,ℓ−1
di+1/di.
The proof of C. L. Stewart [16] of Lemma 2 uses the original lower bounds
for linear forms in logarithms of algebraic numbers due to Baker. It is
interesting to notice that following [16] (see also [10, Lemma 3]) but us-
ing instead the sharper lower bounds for linear forms in logarithms due to
E. M. Matveev [9], does not seem to lead to any improvement of Lemma 2.
Let 1 = d1 < d2 < · · · < dτ(n) = n be all the divisors of n arranged in
increasing order and let
∆0(n) = max
i≤τ(n)−1
di+1/di.
Note that ∆0(n) ≤ ∆(n).
We need the following result of E. Saias [13] on the distribution of positive
integers n with “dense divisors”. Let
G(x, z) = {n ≤ x : ∆0(n) ≤ z}.
Lemma 3. The bound
#G(x, z) ≍ x
log z
log x
holds uniformly for x ≥ z ≥ 2.
Next we address the structure of integer with ∆0(n) ≤ z. In what follows,
as usual, an empty product is, by convention, equal to 1.
Lemma 4. Let n = pe11 · · · p
k be the prime number factorization of a positive
integer n, such that p1 < · · · < pk. Then ∆0(n) ≤ z if and only if for each
i ≤ k, the inequality
pi ≤ z
holds.
Proof. The necessity is clear since otherwise the ratio of the two consecutive
divisors
j and pi
is larger than z.
The sufficiency can be proved by induction on k. Indeed for k = 1 it
is trivial. By the induction assumption, we also have ∆(m) ≤ z, where
m = n/pe11 . Remarking that p1 ≤ z, we also conclude that ∆(n) ≤ z.
5 Proof of Theorem 1
We put E = {n : τ(n) ≥ (log n)3}. To bound #E(x), let x be large and
n ≤ x. We may assume that n > x/(log x)2 since there are only at most
x/(log x)2 positive integers n ≤ x/(log x)2. Since n ∈ E(x), we have that
τ(n) > (log(x/ log x))3 > 0.5(log x)3 for all x sufficiently large. Since
τ(n) = O(x log x)
(see [7, Theorem 320]), we get that
#E(x) ≪
(log x)2
By the Primitive Divisor Theorem (see [1], for example), there exists a prime
factor p ≡ 1 (mod n) of 2n − 1 for all n > 6. Then, by partial summation,
n∈E(x)
(log n)α
P (2n − 1)
n∈E(x)
(log n)α
≤ 1 +
(log t)α
d#E(t)
≤ 1 +
#E(x)
#E(t)(log t)α
≪ 1 +
t(log t)2−α
Hence,
(log n)α
P (2n − 1)
< ∞. (2)
We now let F = {n : P (2n − 1) > n(log n)1+α(log log n)2}. Clearly,
(logn)α
P (2n − 1)
n logn(log logn)2
< ∞. (3)
From now on, we assume that n 6∈ E ∪ F . For a given n, we let
D(n) = {d : dn+ 1 is a prime factor of 2n − 1},
D+(n) = max{d ∈ D(n)}.
Since P (2n − 1) ≥ d(n)n+ 1, we have
D+(n) ≤ (log n)
(log logn)2. (4)
Further, we let xL = e
L. Assume that L is large enough. Clearly, for
n ∈ [xL−1, xL] we have D
+(n) ≤ L1+α(logL)2. We let Hd,L be the set of
n ∈ [xL−1, xL] such thatD
+(n) = d. We then note that by partial summation
xL−1≤n≤xL
n 6∈E∪F
(log n)α
P (2n − 1)
d≤L1+α(logL)2
n∈Hd,L
nd+ 1
d≤L1+α(logL)2
#Hd,L
d≤L1+α(logL)2
#Hd,L
We now estimate #Hd,L. We let ε > 0 to be a small positive number
depending on α which is to be specified later. We split Hd,L in two subsets
as follows:
Let Id,L be the set of n ∈ Hd,L such that
#D(n) >
(logn)
(log log n)2 >
Lα+ε(logL)2,
where M = M(ε) is some positive integer depending on ε to be determined
later. Since D+(n) ≤ L1+α(logL)2, there exists an interval of length L1−ε
which contains at least M elements of D(n). Let them be d0 < d1 < · · · <
dM−1. Write ki = di − d0 for i = 1, . . . ,M − 1. For fixed d0, k1, . . . , kM−1, by
the Brun sieve (see, for example, Theorem 2.3 in [5]),
#{n ∈[xL−1, xL] : din + 1 is a prime for all i = 1, . . . ,M}
(log(xL))M
p|d1···dM
i=1 di
i=1 di
xL(log logL)
where we have used that ϕ(m)/m ≫ 1/ log log y in the interval [1, y] with
y = yL = L
1+α(logL)2 (see [7, Theorem 328]). Summing up the inequality (6)
for all d0 ≤ L
1+α(logL)2 and all k1, . . . , kM−1 ≤ L
1−ε, we get that the number
of n ∈ Id,L is at most
#Id,L ≪
xL(logL)
M+2L1+αL(M−1)(1−ε)
xL(logL)
L(M−1)ε−α
. (7)
We now choose M to be the least integer such that (M − 1)ε > 2 + α, and
with this choice of M we get that
#Id,L ≪
. (8)
We now deal with the set Jd,L consisting of the numbers n ∈ Hd,L with
#D(n) ≤ M−1 (log n)
(log log n)2. To these, we apply Lemma 2. Since
τ(n) < (logn)3 and P (2n − 1) < n2 for n ∈ Hd,L, Lemma 2 yields
log∆(n)/ log logn ≪ #D(n) ≪ (log n)
(log log n)2.
Thus,
log∆(n) ≪ (logn)
(log logn)3
≪ (log xL)
(log log xL)
3 ≪ Lα+ε(logL)3.
Therefore
∆0(n) ≤ ∆(n) ≤ zL,
where
zL = exp(cL
α+ε(logL)3)
and c > 0 is some absolute constant.
We now further split Jd,L into two subsets. Let Sd,L be the subset of
n ∈ Jd,L such that P (n) < x
1/ logL
L . From known results concerning the
distribution of smooth numbers (see the corollary to Theorem 3.1 of [2],
or [8], [17], for example),
#Sd,L ≤
L(1+o(1)) log logL
. (9)
Let Td,L = Jd,L\Sd,L. For n ∈ Td,L, we have n = qm, where q > x
1/ logL
L is a
prime. Fix m. Then q < xL/m is a prime such that qdm+1 is also a prime.
By the Brun sieve again,
#{q ≤ xL/m : q, qdm+ 1 are primes}
m(log(xL/m))2
ϕ(md)
xL(logL)
where in the above inequality we used the minimal order of the Euler function
in the interval [1, xLL
1+α(logL)2] together with the fact that
log(xL/m) ≥
log xL
We now sum up estimate (10) over all the allowable values for m.
An immediate consequence of Lemma 4 is that since ∆0(n) ≤ zL, we also
have ∆0(m) ≤ zL for m = n/P (n). Thus, m ∈ G(xL, zL). Using Lemma 3
and partial summation, we immediately get
m∈G(xL,zL)
d(#G(t, zL))
#G(xL, zL)
#G(t, zL)
log zL
+ log zL
t log t
≪ log zL log log xL ≪ L
α+ε(logL)4,
as L → ∞. Thus,
#Td,L ≪
xL(logL)
m∈Md,L
xL(logL)
7Lα+ε
L2−α−2ε
, (11)
when L is sufficiently large. Combining estimates (8), (9) and (11), we get
#Hd,L ≤ #Jd,L +#Sd,L +#Td,L ≪
L2−α−2ε
. (12)
Thus, returning to series (5), we get that
d≤L1+α(logL)2
L2−2α−2ε
L2−2α−2ε
Since α < 1/2, we can choose ε > 0 such that 2− 2α− 2ε > 1 and then the
above arguments show that
(log n)α
P (2n − 1)
≪ 1 +
L2−2α−ε
which is the desired result.
References
[1] G. D. Birkhoff and H. S. Vandiver, ‘On the integral divisors of an−bn’,
Ann. of Math. (2) 5 (1904), 173–180.
[2] E. R. Canfield, P. Erdős and C. Pomerance, ‘On a problem of Oppen-
heim concerning “factorisatio numerorum”’, J. Number Theory 17
(1983), 1–28.
[3] P. Erdős, P. Kiss and C. Pomerance, ‘On prime divisors of Mersenne
numbers’, Acta Arith. 57 (1991), 267–281.
[4] P. Erdős and T. N. Shorey, ‘On the greatest prime factor of 2p− 1 for
a prime p and other expressions’, Acta Arith. 30 (1976), 257–265.
[5] H. Halberstam and H.-E. Richert, Sieve methods , Academic Press,
London, 1974.
[6] G. H. Hardy and S. Ramanujan, ‘The normal number of prime factors
of an integer, Quart. Journ. Math. (Oxford) 48 (1917), 76-92.
[7] G. H. Hardy and E. M. Wright, An Introduction to the Theory of
Numbers, 5th ed., Oxford, 1979.
[8] A. Hildebrand and G. Tenenbaum, ‘Integers without large prime fac-
tors’, J. de Théorie des Nombres de Bordeaux , 5 (1993), 411–484.
[9] E. M. Matveev, ‘An explicit lower bound for a homogeneous rational
linear form in logarithms of algebraic numbers II’, Izv. Ross. Akad.
Nauk. Ser. Math. 64 (2000), 125–180; English translation Izv. Math.
64 (2000), 1217–1269.
[10] L. Murata and C. Pomerance, ‘On the largest prime factor of a
Mersenne number’, Number theory CRM Proc. Lecture Notes vol.36 ,
Amer. Math. Soc., Providence, RI, 2004, 209–218,.
[11] R. Murty and S. Wong, ‘The ABC conjecture and prime divisors of
the Lucas and Lehmer sequences’, Number theory for the millennium,
III (Urbana, IL, 2000), A K Peters, Natick, MA, 2002, 43–54.
[12] C. Pomerance, ‘On primitive divisors of Mersenne numbers’, Acta
Arith. 46 (1986), no. 4, 355–367.
[13] E. Saias, ‘Entiers à diviseurs denses 1’, J. Number Theory 62 (1997),
163–191.
[14] A. Schinzel, ‘On primitive prime factors of an − bn’, Proc. Cambridge
Philos. Soc. 58 (1962), 555–562.
[15] C. L. Stewart, ‘The greatest prime factor of an − bn’, Acta Arith. 26
(1974/75), no. 4, 427–433.
[16] C. L. Stewart, ‘On divisors of Fermat, Fibonacci, Lucas and Lehmer
numbers’, Proc. London Math. Soc. (3) 35 (1977), 425–447.
[17] G. Tenenbaum, Introduction to analytic and probabilistic number the-
ory , Cambridge Univ. Press, 1995.
	Main Result
	Notation
	Motivation
	Main Tools
	Proof of Theorem ??

  Let P(k) be the largest prime factor of the positive integer k. In this
paper, we prove that the series $\sum_{n\ge 1}\frac{(\log n)^a}{P(2^n-1)}$ is
convergent for each constant a<1/2, which gives a more precise form of a result
of C. L. Stewart from 1977.

Introduction to the Theory of
Numbers, 5th ed., Oxford, 1979.
[8] A. Hildebrand and G. Tenenbaum, ‘Integers without large prime fac-
tors’, J. de Théorie des Nombres de Bordeaux , 5 (1993), 411–484.
[9] E. M. Matveev, ‘An explicit lower bound for a homogeneous rational
linear form in logarithms of algebraic numbers II’, Izv. Ross. Akad.
Nauk. Ser. Math. 64 (2000), 125–180; English translation Izv. Math.
64 (2000), 1217–1269.
[10] L. Murata and C. Pomerance, ‘On the largest prime factor of a
Mersenne number’, Number theory CRM Proc. Lecture Notes vol.36 ,
Amer. Math. Soc., Providence, RI, 2004, 209–218,.
[11] R. Murty and S. Wong, ‘The ABC conjecture and prime divisors of
the Lucas and Lehmer sequences’, Number theory for the millennium,
III (Urbana, IL, 2000), A K Peters, Natick, MA, 2002, 43–54.
[12] C. Pomerance, ‘On primitive divisors of Mersenne numbers’, Acta
Arith. 46 (1986), no. 4, 355–367.
[13] E. Saias, ‘Entiers à diviseurs denses 1’, J. Number Theory 62 (1997),
163–191.
[14] A. Schinzel, ‘On primitive prime factors of an − bn’, Proc. Cambridge
Philos. Soc. 58 (1962), 555–562.
[15] C. L. Stewart, ‘The greatest prime factor of an − bn’, Acta Arith. 26
(1974/75), no. 4, 427–433.
[16] C. L. Stewart, ‘On divisors of Fermat, Fibonacci, Lucas and Lehmer
numbers’, Proc. London Math. Soc. (3) 35 (1977), 425–447.
[17] G. Tenenbaum, Introduction to analytic and probabilistic number the-
ory , Cambridge Univ. Press, 1995.
	Main Result
	Notation
	Motivation
	Main Tools
	Proof of Theorem ??
