ON FIBONACCI NUMBERS WITH FEW PRIME DIVISORS

YANN BUGEAUD, FLORIAN LUCA, MAURICE MIGNOTTE, SAMIR SIKSEK

Abstract. If n is a positive integer, write F_{n} for the nth Fibonacci number, and ω(n) for the number of distinct prime divisors of n. We give a description of Fibonacci numbers satisfying ω(F_{n}) ≤ 2. Moreover, we prove that the inequality ω(F_{n}) ≥ (log n)^{log 2+o(1)} holds for almost all n. We conjecture that ω(F_{n}) ≫ log n for composite n, and give a heuristic argument in support of this conjecture.

1. Introduction

Let F_{n} be the nth Fibonacci number and L_{n} be the nth Lucas number. In a previous paper [3], the following result was proved.

Theorem 1. The only solutions to the equation

F_{n} = y^{m}, m ≥ 2

are given by n = 0, 1, 2, 6 and 12 which correspond respectively to F_{n} = 0, 1, 1, 8 and 144. Moreover, the only solutions to the equation

L_{n} = y^{p}, m ≥ 2

are given by n = 1 and 3 which correspond respectively to L_{n} = 1 and 4.

The proof involves an intricate combination of Baker’s method and the modular method; it also needs about one week of computer verification using the systems pari [1] and magma [2]. In this paper we use the above theorem, together with wellknown results of Carmichael and Cohn to give a description of Fibonacci numbers with at most two distinct prime divisors.

If n is a positive integer, write ω(n) for the number of distinct prime divisors of n. We prove that the inequality ω(F_{n}) ≥ (log n)^{log 2+o(1)} holds for almost all n. We conjecture that ω(F_{n}) ≫ log n for composite n, and give a heuristic argument in support of this conjecture.

2. The Theorems of Carmichael and Cohn

We need the following two celebrated results on Fibonacci numbers. The first is due to Carmichael [4] and the second to Cohn [5].

Theorem 2. Let n > 2 and n ≠ 6, 12 then F_{n} has a prime divisor which does not divide any F_{m} for 0 < m < n; such a prime is called a primitive divisor of F_{n}.

Date: July 30, 2004.

2000 Mathematics Subject Classification. Primary 11B39, Secondary 11K65.

Key words and phrases. Fibonacci numbers, arithmetic functions, prime divisors.

F. Luca’s work is funded in part by grants SEP-CONACyT 37259-E and 37260-E.

S. Siksek’s work is funded by a grant from Sultan Qaboos University (IG/SCI/DOMS/02/06).

Theorem 3. Let 0 < m < n and suppose that the product F_{m}F_{n} is a square, then (m, n) = (1, 2), (1, 12), (2, 12) or (3, 6).

3. Fibonacci numbers with ω(F_{n}) ≤ 2

Write ω(m) for the number of distinct prime factors of m. Notice that ω(F_{n}) > 0 for n > 2 and that for integers m and n, with 1 < m < n and mn ≠ 6, 12, we have

(1)  ω(F_{mn}) > ω(F_{m}) + ω(F_{n}), if (m, n) = 1,

because first F_{m} and F_{n} both divide F_{mn} and are coprime when the indices are coprime, and secondly Theorem 2 implies that there is a prime number dividing F_{mn} which does not divide the product F_{m}F_{n}.

Lemma 3.1. Suppose n is a positive integer and and ω(F_{n}) ≤ 2. Then either n = 1, 2, 4, 8, 12 or n = ℓ, 2ℓ, ℓ^{2} for some odd prime number ℓ.

Proof. The Lemma follows straightforwardly from the fact that ω(F_{n}) ≥ 3 in the following cases:

(a) if 16 | n, or 24 | n, or

(b) if pq | n where p, q are distinct odd primes, or

(c) if ℓ^{3} | n or 2ℓ^{2} | n or 4ℓ | n for some odd prime ℓ, unless n = 12. These may be verified using a combination of Theorem 2 and inequality (1). For example, if 4ℓ | n where ℓ ≠ 3 is an odd prime then

ω(F_{n}) ≥ ω(F_{4ℓ}) > ω(F_{2ℓ}) > ω(F_{ℓ}) ≥ 1,

where the strict inequalities follow from Theorem 2. Thus ω(F_{n}) ≥ 3. □

If n = 2ℓ with ℓ > 3 then F_{n} = F_{ℓ}L_{ℓ} and ω(F_{n}) = 2 implies that F_{ℓ} and L_{ℓ} are prime numbers (because of Theorem 1).

Consider now the case n = ℓ^{2} with ω(F_{n}) = 2. Then ω(F_{ℓ}) = 1 and, by Theorem 1, F_{ℓ} = p = prime. If ℓ = 5 then F_{ℓ} = 5 and F_{25} = 5^{2} × 3001. If ℓ ≠ 5 then p does not divide F_{n}/F_{ℓ} so that F_{n} = pq^{t}, say. By Theorem 3, the product F_{ℓ}F_{n} = p^{2}q^{t} is not a square, thus t is odd.

We have proved the following result.

Theorem 4. The only solutions to the equation

ω(F_{n}) = 1

are given by n = 4, n = 6 or n is an odd prime number for which F_{n} is prime. The only solutions to the equation

ω(F_{n}) = 2

are given for even n by n = 8 or n = 12 or n = 2ℓ where ℓ is some odd prime number for which F_{n} = F_{ℓ}L_{ℓ} where F_{ℓ} and L_{ℓ} are both prime numbers. For odd n, the only possible cases are n = ℓ or n = ℓ^{2}. Moreover if ω(F_{n}) = 2 and n = ℓ^{2} then F_{ℓ} must be prime, say F_{ℓ} = p; and if ℓ ≠ 5, then

F_{n} = pq^{t}

where q is a prime number distinct from p, and the exponent t is odd.

A short computer search reveals examples of all of the above possibilities. Thus • examples of ω(F_{n}) = 1 with n prime are: F_{5} = 5, F_{7} = 13, F_{11} = 89,

F_{13} = 233, …

• examples of ω(F_{n}) = 2 with n = 2ℓ are: F_{10} = 55, F_{14} = 13 × 29, F_{22} =

89 × 199, F_{26} = 233 × 521, …

• examples of ω(F_{n}) = 2 with n = ℓ, ℓ^{2} are: F_{9} = 34, F_{19} = 37 × 113, F_{25},

F_{31} = 557 × 2417, …, F_{121} = 89 × 97415813466381445596089, …

Remark. Lemma 3.1 can also be proved using some results from [7]. For example, one of the results from [7] is that, if τ(m) denotes the number of divisors of the positive integer m, then we have τ(F_{n}) ≥ F_{τ(n)} for any positive integer n, with equality only for n = 1, 2, 4. Assuming that ω(F_{n}) ≤ 2, one gets immediately that (up to a few exceptions) τ(n) ≤ 4, giving that n is the product of two distinct prime numbers or the square of a prime number, which together with Theorem 2 yields the conclusion of Lemma 3.1.

4. Fibonacci numbers rarely have few prime factors

Theorem 4 in effect tells us that ω(F_{n}) ≥ 3 for almost all n. We mean by this that the set of integers for which this inequality holds has density 1. Indeed, much more is true. For example, by the following theorem, ω(F_{n}) ≥ C holds for almost all n, whatever the value of C.

Theorem 5. The inequality ω(F_{n}) ≥ (log n)^{log 2+o(1)} holds for almost all n.

Proof. By Theorem 2, we know that if a divisor d of n is not 1, 2, 6 or 12 then F_{d} has a primitive prime factor. This translates immediately in saying that

ω(F_{n}) ≥ τ(n) − 4,

where τ(n) is the total number of divisors of n. Certainly, τ(n) ≥ 2^{ω(n)}. Since ω(n) = (1 + o(1)) log log n for almost all n, the desired inequality follows. □

5. Heuristic results

Given the present state of knowledge in analytic number theory, it seems unrealistic to obtain precise results as to whether each of the possibilities from Theorem 4 occurs finitely many times or infinitely often. There is, however, a standard heuristic argument which suggests that there are infinitely many primes ℓ with F_{ℓ} prime, but only finitely many primes ℓ with ω(F_{2ℓ}) = 2 or ω(F_{ℓ^{2}}) = 2.

The heuristic argument goes as follows (compare with [6, page 15]): from the Prime Number Theorem, the ‘probability’ that a positive integer m is prime is 1/ log m. Thus the ‘expected number’ of primes ℓ such that F_{ℓ} is also prime is

∑_{ℓ is prime} \frac{1}{log F_{ℓ}} ≥ A ∑_{ℓ is prime} \frac{1}{ℓ}

for some positive constant A. Since this last series diverges (albeit very slowly), it is reasonable to guess that there are infinitely prime F_{ℓ}.

Applying the same heuristic argument suggests that there are only finitely many primes ℓ with ω(F_{2ℓ}) = 2 or ω(F_{ℓ^{2}}) = 2. For example, the ‘expected number’ of primes ℓ with ω(F_{2ℓ}) = 2 is

∑_{ℓ is prime} \frac{1}{log F_{ℓ} × log L_{ℓ}} ≤ B ∑_{ℓ is prime} \frac{1}{ℓ^{2}} < ∞

where B is some positive constant.

In fact we can go even further. We conjecture the following.

Conjecture 5.1. ω(F_{n}) ≫ log n holds for all composite positive integers n.

In order to ‘justify’ this conjecture, let us make the following heuristic principle.

Heuristic 5.2. Let k : ℕ → ℕ be any function. Let A be a subset of positive integers such that there is no algebraic reason for a ∈ A to have more than k(a) prime factors. Assume that for every a ∈ A there exists a proper divisor of a, let us call it ã > 1, such that the greatest common divisor of ã and a/ã has at most one prime factor and the series

∑_{a∈A} ∑_{k_{1}+k_{2}≤k(a)+1} \frac{1}{(k_{1} − 1)!} \frac{1}{(k_{2} − 1)!} \frac{(log log ã)^{k_{1}−1}(log log(a/ã))^{k_{2}−1}}{log ã × log(a/ã)}

is convergent. Then ω(a) ≤ k(a) should hold only for finitely many a ∈ A.

Heuristic 5.2, is based on the fact that the ‘probability’ for a positive integer n to have k distinct prime factors is

\frac{1}{(k − 1)!} \frac{(log log n)^{k−1}}{log n} .

So, if a ∈ A and ω(a) = k ≤ k(a), then there exist nonnegative integers k_{1} and k_{2} such that ω(ã) = k_{1} and ω(a/ã) = k_{2}. Furthermore, since the greatest common divisor of ã and a/ã has at most one prime factor, it follows that either k_{1} + k_{2} = k ≤ k(a) or k_{1} + k_{2} = k + 1 ≤ k(a) + 1. Thus, the above sum represents just the sum of the ‘probabilities’ that ω(ã) = k_{1} and ω(a/ã) = k_{2} assuming that such events are independent.

5.1. Conjecture 5.1 follows from Heuristic 5.2. Let n be a composite integer. Observe first that, by Theorem 2, if a divisor d of n is different from 1, 2, 6 or 12, then F_{d} has a prime factor not dividing F_{d_{1}} for any positive integer d_{1} < d. Consequently, if n has at least 0.3 log n divisors, then we have

(2)  ω(F_{n}) ≥ max{1, 0.3 log n − 6} ≫ log n.

Let A be the set of Fibonacci numbers F_{n}, where n runs through the composite integers having less than 0.3 log n divisors. Let n be composite and write m for the largest proper divisor of n. Clearly, m = n/p(n), where p(n) is the smallest prime factor of n. Note that m ≥ n^{1/2}. It is known that gcd(F_{m}, F_{n}/F_{m})|p(n), therefore the two numbers F_{m} and F_{n}/F_{m} share at most one prime factor. Fix k and let k_{1} and k_{2} be such that k_{1} + k_{2} = k. One checks immediately that both inequalities F_{m} < e^{m} and F_{n}/F_{m} < e^{n−m} hold. Thus, we get

∑_{k_{1}+k_{2}=k} \frac{1}{(k_{1} − 1)!(k_{2} − 1)!} (log log F_{m})^{k_{1}−1} (log log(F_{n}/F_{m}))^{k_{2}−1}

≤ \frac{1}{(k − 2)!} ∑_{k_{1}+k_{2}=k} \binom{k − 2}{k_{1} − 1}(log m)^{k_{1}−1} (log(n − m))^{k_{2}−1}

= \frac{1}{(k − 2)!} (log m + log(n − m))^{k−2} < (\frac{2e log n}{k − 2})^{k−2} ,

where for the last inequality above we used Stirling’s formula. Using the inequalities log F_{m} ≫ m ≥ n^{1/2} and log(F_{n}/F_{m}) ≫ (n − m) ≫ n (because m divides n), it follows that

∑_{k_{1}+k_{2}=k} \frac{(log log F_{m})^{k_{1}−1} (log log(F_{n}/F_{m}))^{k_{2}−1}}{(k_{1} − 1)!(k_{2} − 1)! log F_{m} × log(F_{n}/F_{m})} ≪ \frac{1}{n^{3/2}} (\frac{2e log n}{k − 2})^{k−2} .

For a fixed y, the function x ⟼ (2ey/x)^{x} is increasing for x < 2y. Thus, taking k(F_{n}) = c_{0} log n, where c_{0} < 2 is some constant, we get that

∑_{k_{1}+k_{2}≤k(F_{n})} \frac{(log log F_{m})^{k_{1}−1} (log log(F_{n}/F_{m}))^{k_{2}−1}}{(k_{1} − 1)!(k_{2} − 1)! log F_{m} × log(F_{n}/F_{m})}

≪ ∑_{k≤k(F_{n})} \frac{1}{n^{3/2}} (\frac{2e log n}{k − 2})^{k−2} ≪ \frac{log n}{n^{3/2}} (\frac{2e}{c_{0}})^{c_{0} log n} .

Choosing c_{0} such that c_{0} log(2e/c_{0}) = c_{1} < 1/2 (we can choose, say, c_{0} = 0.3), we get that the right hand side of the above inequality is

≪ \frac{log n}{n^{3/2−c_{1}}}

and summing up over n we get a convergent series. Hence, Heuristic 5.2 with a = F_{n} and ã = F_{m} for F_{n} in A implies that ω(F_{n}) < 0.3 log n holds only for finitely many composite integers n, which, by (2) and the definition of A, implies that ω(F_{n}) ≫ log n holds for all composite integers n. Actually, our choice of A takes into account an algebraic reason for which F_{n} has more than 0.3 log n divisors.

References

[1] C. Batut, K. Belabas, D. Bernardi, H. Cohen and M. Olivier, User’s guide to PARI-GP,

 version 2.1.1. (See also http://www.parigp-home.de/.)

[2] W. Bosma, J. Cannon and C. Playoust, The Magma Algebra System I: The User Language,

 J. Symb. Comp. 24 (1997), 235–265. (See also http://www.maths.usyd.edu.au:8000/u/magma/.)

[3] Y. Bugeaud, M. Mignotte and S. Siksek, Classical and modular approaches to exponential Diophantine equations, I. Fibonacci and Lucas Perfect Powers. Submitted.

[4] R. D. Carmichael, On the numerical factors of arithmetical forms α^{n} ± β^{n}, Ann. of Math. (2) 15 (1913), 30–70.

[5] J. H. E. Cohn, Squares in some recurrence sequences, Pacific J. Math. 41 (1972), 631–646.

[6] G. H. Hardy and E. M. Wright, Introduction to the theory of numbers, Oxford University Press, fourth edition, 1975.

[7] F. Luca, Arithmetic functions of Fibonacci numbers, Fibonacci Quart. 37 (1999), 265–268.

Yann Bugeaud, Université Louis Pasteur, U. F. R. de mathématiques, 7, rue René Descartes, 67084 Strasbourg Cedex, France

   E-mail address: bugeaud@math.u-strasbg.fr

Florian Luca, Instituto de Matemáticas, UNAM, Ap. Postal 61-3 (Xangari), C.P. 58180, Morelia, Michoacán, Mexico

   E-mail address: fluca@matmor.unam.mx

Maurice Mignotte, Université Louis Pasteur, U. F. R. de mathématiques, 7, rue René Descartes, 67084 Strasbourg Cedex, France

   E-mail address: mignotte@math.u-strasbg.fr

Samir Siksek, Department of Mathematics and Statistics, College of Science, Sultan Qaboos University, P.O. Box 36, Al-Khod 123, Oman

   E-mail address: siksek@squ.edu.om