CLASSICAL AND MODULAR APPROACHES TO EXPONENTIAL DIOPHANTINE EQUATIONS I. FIBONACCI AND LUCAS PERFECT POWERS

YANN BUGEAUD, MAURICE MIGNOTTE, SAMIR SIKSEK

Abstract. This is the first in a series of papers whereby we combine the classical approach to exponential Diophantine equations (linear forms in logarithms, Thue equations, etc.) with a modular approach based on some of the ideas of the proof of Fermat’s Last Theorem. In this paper we give new improved bounds for linear forms in three logarithms. We also apply a combination of classical techniques with the modular approach to show that the only perfect powers in the Fibonacci sequence are 0, 1, 8 and 144 and the only perfect powers in the Lucas sequence are 1 and 4.

1. Introduction

Wiles’ proof of Fermat’s Last Theorem [53], [49] is certainly the most spectacular recent achievement in the field of Diophantine equations. The proof uses what may be called the ‘modular’ approach, initiated by Frey ([19], [20]), which has since been applied to many other Diophantine equations; mostly—though not exclusively—of the form

(1) ax^{p} + by^{p} = cz^{p},  ax^{p} + by^{p} = cz^{2},  ax^{p} + by^{p} = cz^{3}, … (p prime).

The strategy of the modular approach is simple enough: associate to a putative solution of such a Diophantine equation an elliptic curve, called a Frey curve, in a way that the discriminant is a p-th power up to a factor which depends only on the equation being studied, and not on the solution. Next apply Ribet’s levellowering theorem [43] to show that the Galois representation on the p-torsion of the Frey curve arises from a newform of weight 2 and a fairly small level N say. If there are no such newforms then there are no non-trivial solutions to the original Diophantine equation. (A solution is said to be trivial if the corresponding Frey curve is singular.) Occasionally, even when one has newforms of the predicted level there is still a possibility of showing that it is incompatible with the original Galois representation (see for example [18], [5], [21]), though there does not seem to be a general strategy that is guaranteed to succeed.

A fact that has been underexploited is that the modular approach yields a tremendous amount of local information about the solutions of the Diophantine equations. For equations of the form (1) it is perhaps difficult to exploit this information successfully since we neither know of a bound for the exponent p, nor for the variables x, y, z. This suggests that the modular approach should be applied to exponential Diophantine equations; for example, equations of the form

Date: July 24, 2005.

2000 Mathematics Subject Classification. Primary 11D61, 11B39, 11J86, Secondary 11D59.

Key words and phrases. Diophantine equations, Frey curves, level-lowering, linear forms in logarithms, Thue equations, Fibonacci numbers, Lucas numbers.

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

ax^{p} + by^{p} = c, ax^{2} + b = cy^{p}, … (p prime).

For such equations, Baker’s theory of linear forms in logarithms (see the book of Shorey and Tijdeman [46]) gives bounds for both the exponent p and the variables x, y. This approach through linear forms in logarithms and Thue equations, which we term the ‘classical’ approach, has undergone substantial refinements, though it still often yields bounds that can only be described as ‘number theoretical’.

The present paper is the first in a series of papers whose aims are the following: (I) To present theoretical improvements to various aspects of the classical ap-

proach. (II) To show how local information obtained through the modular approach

can be used to reduce the size of the bounds, both for exponents and for variables, of solutions to exponential Diophantine equations.

(III) To show how local information obtained through the modular approach can be pieced together to provide a proof that there are no missing solutions less than the bounds obtained in (I), (II).

(IV) To solve various outstanding exponential Diophantine equations.

Our theoretical improvement in this paper is a new and powerful lower bound for linear forms in three logarithms. Such a lower bound is often the key to bounding the exponent in an exponential Diophantine equation. This is our choice for (I). Our choice for (IV) is the infamous problem of determining all perfect powers in the Fibonacci and Lucas sequences. Items (II), (III) will be present in this paper only in the context of solving this problem. A sequel combining the classical and modular approaches for Diophantine equations of the form x^{2} + D = y^{p} has just been completed [13].

We delay presenting our lower bound for linear forms in three logarithms till Section 12, as this is somewhat technical. Regarding the Fibonacci and Lucas sequences we prove the following Theorems.

Theorem 1. Let F_{n} be the n-th term of the Fibonacci sequence defined by

F_{0} = 0, F_{1} = 1 and F_{n+2} = F_{n+1} + F_{n} for n ≥ 0.

The only perfect powers in this sequence are F_{0} = 0, F_{1} = 1, F_{2} = 1, F_{6} = 8 and F_{12} = 144.

Theorem 2. Let L_{n} be the n-th term of the Lucas sequence defined by

L_{0} = 2, L_{1} = 1 and L_{n+2} = L_{n+1} + L_{n} for n ≥ 0.

The only perfect powers in this sequence are L_{1} = 1 and L_{3} = 4.

It is appropriate to point out that equations F_{n} = y^{p} and L_{n} = y^{p} have previously been solved for small values of the exponent p by various authors. We present a brief survey of known results in Section 2.

The main steps in the proofs of Theorems 1 and 2 are as follows:

(i) We associate Frey curves to putative solutions of the equations F_{n} = y^{p} and L_{n} = y^{p} with even index n to Frey curves and apply level-lowering. This, together with some elementary arguments is used to reduce to the case where the index n satisfies n ≡ ±1 (mod 6).

(ii) We then show that we may suppose that the index n in the equations F_{n} = y^{p} and L_{n} = y^{p} is prime. In the Fibonacci case this is essentially a result proved first by Pethő [40] and Robbins [44] (independently).

(iii) We apply level-lowering again under the assumption that the index n is odd. We are able to show using this that n ≡ ±1 (mod p) for p < 2 × 10^{8} in the Fibonacci case. In the Lucas case we prove that n ≡ ±1 (mod p) unconditionally.

(iv) We show how to reduce the equations F_{n} = y^{p} and L_{n} = y^{p} to Thue equations. We do not solve these Thue equations completely, but compute explicit upper bounds for their solutions using classical methods (see for example [10]). This provides us with upper bounds for n in terms of p. In the Lucas case we need the fact that n ≡ ±1 (mod p) to obtain a simpler equation of Thue type.

(v) We show how the results of the level-lowering of step (iii) can be used, with the aid of a computer program, to produce extremely stringent congruence conditions on n. For p ≤ 733 in the Fibonacci case, and for p ≤ 281 in the Lucas case, the congruences obtained are so strong that, when combined with the upper bounds for n in terms of p obtained in (iv), they give a complete resolution for F_{n} = y^{p} and L_{n} = y^{p}.

(vi) It is known that the equation L_{n} = y^{p} yields a linear form in two logarithms. Applying the bounds of Laurent, Mignotte and Nesterenko [27] we show that p ≤ 281 in the Lucas case. This completes the determination of perfect powers in the Lucas sequences.

(vii) The equation F_{n} = y^{p} yields a linear form in three logarithms. However if p < 2 × 10^{8} then by step (iii) we know that n ≡ ±1 (mod p). We show how in this case the linear form in three logarithms may be rewritten as a linear form in two logarithms. Applying [27] we deduce that p ≤ 733, which is the case we have already solved in step (v).

(viii) To complete the resolution of F_{n} = y^{p} it is enough to show that p < 2×10^{8}. We present a powerful improvement to known bounds for linear forms in three logarithms. Applying our result shows indeed that p < 2×10^{8} and this completes the determination of perfect powers in the Fibonacci sequence.

Let us make some brief comments. The condition n ≡ ±1 (mod p) obtained after step (iii) cannot be strengthened.

Indeed, we may define F_{n} and L_{n} for negative n by the recursion formulae F_{n+2} = F_{n+1} + F_{n} and L_{n+2} = L_{n+1} + L_{n}. We then observe that F_{−1} = 1 and L_{−1} = −1. Consequently, F_{−1}, F_{1}, L_{−1} and L_{1} are p-th powers for any odd prime p. Thus equations F_{n} = y^{p} and L_{n} = y^{p} do have solutions with n ≡ ±1 (mod p).

The strategy of combining explicit upper bounds for the solutions of Thue equations with a sieve has already been applied successfully in [12]. The idea of combining explicit upper bounds with the modular approach was first tentatively floated in [48].

A crucial observation for the proof of Theorem 1 is the fact that, with a modicum of computation, we can indeed use linear forms in two logarithms, and then get a much smaller upper bound for the exponent p.

The present paper is organised as follows. Section 2 is devoted to a survey of previous results. Sections 3 and 4 are concerned with useful preliminaries. Steps (i) and (ii) are treated in Sections 5 and 6, respectively. Sections 7 and 8 are devoted to step (iii). Sections 9 and 10 are concerned with Steps (iv) and (v). Section 11 deals with steps (vi) and (vii), and finishes the proof of Theorem 2. Finally, the proof of Theorem 1 is completed in Section 13, which deals with step (viii), by applying estimates for linear forms in three logarithms proved in Section 12.

The computations in the paper were performed using the computer packages PARI/GP [2] and MAGMA [7]. The total running time for the various computational parts of the proof of Theorem 1 is roughly 158 hours on a 1.7 GHz Intel Pentium 4. By contrast, the total time for the corresponding computational parts of the proof of Theorem 2 is roughly 6 hours.

2. A Brief Survey of Previous Results

In this section we would like place our Theorems 1 and 2 in the context of other exponential Diophantine equations. We also give a very brief survey of results known to us on the problem of perfect powers in the Fibonacci and Lucas sequences, though we make no claim that our survey is exhaustive.

Thanks to Baker’s theory of linear forms in logarithms, we know (see for example the book of Shorey and Tijdeman [46]) that many families of Diophantine equations have finitely many integer solutions, and that one can even compute upper bounds for their absolute values. These upper bounds are however huge and do not enable us to provide complete lists of solutions by brutal enumeration. During the last decade, thanks to important progress in computational number theory (such as the LLL-algorithm) and also in the theory of linear forms in logarithms (the numerical constants have been substantially reduced in comparison to Baker’s first papers), we are now able to solve completely some exponential Diophantine equations. Perhaps the most striking achievement obtained via techniques from Diophantine approximation is a result of Bennett [4], asserting that, for any integers a, b and p ≥ 3 with a > b ≥ 1, the Diophantine equation

|aX^{p} − bY^{p}| = 1

has at most one solution in positive integers X and Y.

Among other results in this area obtained thanks to (at least in part) the theory of linear forms in logarithms, let us quote that Bugeaud and Mignotte [11] proved that the equation (10^{n} − 1)/(10 − 1) = y^{p} has no solution with y > 1, and that Bilu, Hanrot and Voutier [6] solved the long-standing problem of the existence of primitive divisors of Lucas–Lehmer sequences.

Despite substantial theoretical progress and the use of techniques coming from arithmetic geometry and developed in connection with Fermat’s Last Theorem (see for example the paper of Bennett and Skinner [5]), some celebrated Diophantine equations are still unsolved. We would particularly like to draw the reader’s attention to the following three equations:

(2)  x^{2} + 7 = y^{p},  p ≥ 3,
(3)  x^{2} − 2 = y^{p},  p ≥ 3,

and

(4)  F_{n} = y^{p},  n ≥ 0 and p ≥ 2,

where F_{n} is the n-th term in the Fibonacci sequence. Let us explain the difficulties encountered with equations (2), (3) and (4). Classically, we first use estimates for linear forms in logarithms in order to bound the exponent p, and then we perform a sieve. Equations (2) and (4) yield linear forms in three logarithms, and thus upper bounds for p of the order of 10^{13}; at present far too large to allow the complete resolution of (2) and (4) using classical methods (however, a promising attempt at equation (2) is made in [48]). The case of (3) is different, since estimates for linear forms in two logarithms yield that n is at most 164969 [22], an upper bound which can certainly be (at least) slightly improved. There is however a notorious difficulty in (3) and (4), namely the existence of solutions 1^{2} − 2 = (−1)^{p} and F_{1} = 1^{p} for each value of the exponent p. These small solutions prevent us from using a sieve as efficient as the one used for (2). A natural way to overcome this is to derive from (3) and (4) Thue equations, though these are of degree far too large to allow for a complete resolution using classical methods alone.

As we have explained in the introduction, the present work is devoted to equation (4), and to the analogous equation for the Lucas sequence.

As for general results, Pethő [39] and, independently, Shorey and Stewart [45] proved that there are only finitely many perfect powers in any non-trivial binary recurrence sequence. Their proofs, based on Baker’s theory of linear forms in logarithms, are effective but yield huge bounds. We now turn to specific results on the Fibonacci and Lucas sequences.

• The only perfect squares in the Fibonacci sequence are F_{0} = 0, F_{1} = F_{2} = 1 and F_{12} = 144; this is a straightforward consequence of two papers by Ljunggren [29, 30, 32]. This has been rediscovered by Cohn [14] (see the Introduction to [31]) and Wyler [54].

• London and Finkelstein [33] showed that the only perfect cubes in the Fibonacci sequence are F_{0} = 0, F_{1} = F_{2} = 1 and F_{6} = 8. This was reproved by Pethő [40], using a linear form in logarithms and congruence conditions.

• For m = 5, 7, 11, 13, 17, the only m-th powers are F_{0} = 0, F_{1} = F_{2} = 1. The case m = 5 is due to Pethő [41], using the method described in [40]. It has been reproved by McLaughlin [34] by using a linear form in logarithms together with the LLL algorithm. The other cases are solved in [34] with this method.

• If n > 2 and F_{n} = y^{p} then p < 5.1 × 10^{17}; this was proved by Pethő using a linear form in three logarithms [42]. In the same paper he also showed that if n > 2 and L_{n} = y^{p} then p < 13222 using a linear form in two logarithms.

• Another result which is particularly relevant to us is the following: If p ≥ 3 and F_{n} = y^{p} for integer y then either n = 0, 1, 2, 6 or there is a prime q | n such that F_{q} = y_{1}^{p}, for some integer y_{1}. This result was established by Pethő [40] and Robbins [44] independently.

• Cohn [15] proved that L_{1} = 1 and L_{3} = 4 are the only squares in the Lucas sequence.

• London and Finkelstein [33] proved that L_{1} = 1 is the only cube in the Lucas sequence.

3. Preliminaries

We collect in this section various results which will be useful throughout this paper. Our problem of determining the perfect powers in the Fibonacci and Lucas sequences naturally reduces to the problem of solving the following pair of equations:

(5)  F_{n} = y^{p},  n ≥ 0, and p prime,

and

(6)  L_{n} = y^{p},  n ≥ 0, and p prime.

Throughout this paper we will use the fact that

(7)  F_{n} = \frac{ω^{n} − τ^{n}}{\sqrt{5}} ,  L_{n} = ω^{n} + τ^{n},

where

(8)  ω = \frac{1 + \sqrt{5}}{2},  τ = \frac{1 − \sqrt{5}}{2}.

This quickly leads us to associate the equations F_{n} = y^{p} and L_{n} = y^{p} with auxiliary equations as the following two Lemmas show.

Lemma 3.1. Suppose that F_{n} = y^{p}. If n is odd then

(9)  5y^{2p} = L_{n}^{2} + 4,

and if n is even then

(10)  5y^{2p} = L_{n}^{2} − 4.

Lemma 3.2. Suppose that L_{n} = y^{p}. If n is odd then

(11)  y^{2p} = 5F_{n}^{2} − 4,

and if n is even then

(12)  y^{2p} = 5F_{n}^{2} + 4.

For a prime l ≠ 5 define

(13)  M(l) = \{ \begin{matrix}l − 1, & if l ≡ ±1 (mod 5), \\ 2(l + 1), & if l ≡ ±2 (mod 5). \end{matrix}

We will need the following two Lemmas.

Lemma 3.3. Suppose that l ≠ 5 is a prime and n ≡ m (mod M(l)). Then

F_{n} ≡ F_{m} (mod l) and L_{n} ≡ L_{m} (mod l).

Proof. Write O for the ring of integers of the field ℚ(\sqrt{5}). Recall, by (7), that F_{n} and L_{n} are expressed in terms of ω, τ. Let π be a prime in O dividing l. To prove the Lemma all we need to show is that

ω^{M(l)} ≡ τ^{M(l)} ≡ 1 (mod π).

If l ≡ ±1 (mod 5) then 5 is a quadratic residue modulo l. The Lemma follows immediately in this case from the fact that (O/πO)^{∗} ≅ 𝔽_{l}^{∗} and so has order l − 1.

Now suppose that l ≡ ±2 (mod 5). Note that

ω^{l} ≡ \frac{1^{l} + 5^{\frac{l−1}{2}} \sqrt{5}}{2^{l}} ≡ \frac{1 − \sqrt{5}}{2} ≡ τ (mod π),

since 5 is a quadratic non-residue modulo l. Thus

ω^{M(l)} ≡ ω^{2(l+1)} ≡ (ωτ)^{2} ≡ 1 (mod π),

and similarly for τ. □

Lemma 3.4. The residues of L_{n}, F_{n} modulo 4 depend only on the residue of n modulo 6, and are given by the following table

L_{n} (mod 4) F_{n} (mod 4)
n ≡ 0 (mod 6)  2  0
n ≡ 1 (mod 6)  1  1
n ≡ 2 (mod 6)  3  1
n ≡ 3 (mod 6)  0  2
n ≡ 4 (mod 6)  3  3
n ≡ 5 (mod 6)  3  1

Proof. The Lemma is proved by a straightforward induction, using the recurrence relations defining F_{n} and L_{n}. □

4. Eliminating Small Exponents and Indices

We will later need to assume that the exponent p and the index n in the equations (5) and (6) are not too small. More precisely, in this Section, we prove the following pair of Propositions.

Proposition 4.1. If there is a perfect power in the Fibonacci sequence not listed in Theorem 1 then there is a solution to the equation

(14)  F_{n} = y^{p},  n > 25000 and p ≥ 7 is prime.

Proposition 4.2. If there is a perfect power in the Lucas sequence not listed in Theorem 2 then there is a solution to the equation

(15)  L_{n} = y^{p},  n > 25000 and p ≥ 7 is prime.

The propositions follow from the results on Fibonacci perfect powers quoted in Section 2 together with Lemmas 4.3 and 4.4 below.

4.1. Ruling Out Small Values of the Index n.

Lemma 4.3. For no integer 13 ≤ n ≤ 25000 is F_{n} a perfect power. For no integer 4 ≤ n ≤ 25000 is L_{n} a perfect power.

Proof. Suppose F_{n} = y^{p} where p is some prime and n is in the range 13 ≤ n ≤ 25000. It is easy to see from (7), (8) that 2 ≤ p ≤ n log(ω)/ log(2). Now fix n, p and we would like to show that F_{n} is not a p-th power.

Suppose l is a prime satisfying l ≡ ±1 (mod 5) and l ≡ 1 (mod p). The condition l ≡ ±1 (mod 5) ensures that 5 is a quadratic residue modulo l. Then one can easily compute F_{n} modulo l using (7) (without having to write down F_{n}). Now let k = (l − 1)/p. If F_{n}^{k} ≢ 1 (mod l) then we know that F_{n} is not a p-th power.

We wrote a short PARI/GP program to check for n in the above range, and for each prime 2 ≤ p ≤ n log(ω)/ log(2) that there exits a prime l proving that F_{n} is not a p-th power, using the above idea. This took roughly 15 minutes on a 1.7 GHz Pentium 4.

The corresponding result for the Lucas sequence is proved in exactly the same way, with program taking roughly 16 minutes to run on the same machine. □

4.2. Solutions with Exponent p = 2, 3, 5. Later on when we come to apply level-lowering we will need to assume that p ≥ 7. It is straightforward to solve equations (5) and (6) for p = 2, 3, 5 with the help of the computer algebra package MAGMA. We give the details for the Lucas case; the Fibonacci case is similar. Alternatively we could quote the known results surveyed in Section 2, although p = 5 for the Lucas case does not seem to be covered by the literature.

Lemma 4.4. The only solutions to the equation (6) with p = 2, 3, 5 are (n, y, p) = (1, 1, p) and (3, 2, 2).

Proof. Suppose first that n is even. By Lemma 3.2 it is enough to show that (12) does not have a solution. Suppose that (n, y, p) is a solution to (12). Clearly F_{n} and y are odd, and y is not divisible by 5. Thus we have

(2 + F_{n}\sqrt{−5}) = 𝔞^{2p}

for some ideal 𝔞 of ℤ[\sqrt{−5}]. Now the class number of ℤ[\sqrt{−5}] is 2, and hence 𝔞^{2} is a principal ideal. It follows that

2 + F_{n}\sqrt{−5} = ϵ(u + v\sqrt{−5})^{p}

for some integers u, v, where ϵ = ±1 if p = 2 and ϵ = 1 otherwise. If p = 2 then we get ±2 = u^{2} − 5v^{2} which is impossible modulo 5. If p = 3 then

2 = u(u^{2} − 15v^{2}),

and if p = 5 then

2 = u(u^{4} − 50u^{2}v^{2} + 125v^{4}).

It is straightforward to see that both of these are impossible. Next we turn to the case where n is odd. Again by Lemma 3.2 it is enough to solve the equation (11). Suppose first that p = 3, 5. If (n, y, p) is any solution to equation (11) then we quickly see that y must be odd and

2 + \sqrt{5}F_{n} = (\frac{1 + \sqrt{5}}{2})^{r} (u + v\sqrt{5})^{p}

For some r = 0,…, p − 1 and u, v are both integers or both halves of odd integers. The computer algebra package MAGMA quickly solves all the resulting Thue equations showing that y = ±1. This implies that for p = 3, 5 the only solution to equation (6) is the trivial one (1, 1, p).

Finally to deal with p = 2 we note that if (n, y) satisfies (11) then (X, Y) = (5y^{2}, 25F_{n}y) is an integral point on the elliptic curve Y^{2} = X^{3} + 100X. Again MAGMA quickly computes all integral points on this curve: these are (X, Y) = (0, 0), (5, ±25), (20, ±100), which yields the solutions (n, y) = (1, 1), (3, 2). This completes the proof of the Lemma. □

5. Reducing to the Case n ≡ ±1 (mod 6)

In this section we would like to reduce the study of equations (5) and (6) to the special case where the index n satisfies n ≡ ±1 (mod 6). For Fibonacci we show that if there is some solution (n, y, p) to (5) then there is another solution with the same exponent p such that the index n satisfies the above condition. For the Lucas sequence we prove the following stronger result.

Lemma 5.1. If (n, y, p) is a solution to the equation (6) with p ≥ 7 then n ≡ ±1 (mod 6).

For Fibonacci our result is weaker but still useful.

Lemma 5.2. If (n, y, p) is a solution to equation (5) with p ≥ 7 then either n = 0 or n ≡ ±1 (mod 6) or else n = 2k with

(a) k ≡ ±1 (mod 6)

(b) F_{k} = U^{p} and L_{k} = V^{p} for some positive integers U and V.

The proofs of both of Lemmas 5.1 and 5.2 make use of Frey curves and levellowering. Here and elsewhere where we make use of these tools, we do not directly apply the original results in this field (Ribet’s level-lowering Theorem [43], modularity of elliptic curves by Wiles and others [53], [8], irreducibility of Galois representations by Mazur and others [36], etc.). We will instead quote directly from the excellent recent paper of Bennett and Skinner [5], which is concerned with equations of the form Ax^{n} + By^{n} = Cz^{2}. In every instance we will put our equation in this form before applying the results of [5].

Proof of Lemma 5.1. Suppose that (n, y, p) is a solution to equation (6) with p ≥ 7.

We observe first that n ≢ 0, 3 (mod 6). For in this case Lemma 3.4 implies that both F_{n} and L_{n} are even, and hence by Lemma 3.2 either 5 or −5 is a 2-adic square, which is not the case.

We now restrict our attention to n ≡ 2, 4 (mod 6) and p ≥ 7 and show that this leads to a contradiction. This is enough to prove the Lemma. Let

G_{n} = \{ \begin{matrix}−F_{n} & if n ≡ 2 (mod 6) \\ F_{n} & if n ≡ 4 (mod 6). \end{matrix}

It follows from Lemma 3.2 that

y^{2p} = 5G_{n}^{2} + 4.

We associate to our solution (n, y, p) of (6) with n ≡ 2, 4 (mod 6) the Frey curve

(16)  E_{n} :  Y^{2} = X^{3} + 5G_{n}X^{2} − 5X.

Let E be the elliptic curve 100A1 in Cremona’s tables [17]; E has the following model:

E : Y^{2} = X^{3} − X^{2} − 33X + 62.

Write ρ_{p}(E) for the Galois representation

ρ_{p}(E) : Gal(\overline{ℚ}/ℚ) → Aut(E[p])

on the p-torsion of E, and let ρ_{p}(E_{n}) be the corresponding Galois representation for E_{n}.

Applying the results of [5, Sections 2, 3], we see that ρ_{p}(E_{n}) arises from a cuspidal newform of weight 2, level 100, and trivial Nebentypus character. However using the computer algebra package MAGMA we find that the dimension of newforms of weight 2 and level 100 is one. Moreover the curve E above is (up to isogeny) the unique elliptic curve of conductor 100. Thus ρ_{p}(E_{n}) and ρ_{p}(E) are isomorphic. It follows from this, by [5, Proposition 4.4], that 5 does not divide the denominator of the j-invariant of E. This is not true as j(E) = 16384/5, giving us a contradiction.

For the convenience of the reader we point out that in Bennett and Skinner’s notation:

A = 1, B = −4, C = 5, a = y^{2}, b = 1, c = G_{n}.

Lemma 3.4 and our definition of G_{n} above imply that c ≡ 3 (mod 4) which is needed to apply the results of Bennett and Skinner. This completes our proof of Lemma 5.1. □

Proof of Lemma 5.2. Suppose that (n, y, p) is a solution to equation (5) with n ≠ 0 and p ≥ 7. By Lemma 3.4 we see that n ≢ 3 (mod 6). Suppose then that n ≢ ±1 (mod 6). Clearly n = 2k for some integer k. It is well-known and easy to see from (7) that F_{n} = F_{2k} = F_{k}L_{k}. It is also easy to see that the greatest common divisor of F_{k} and L_{k} is either 1 or 2. The crux of the proof is to show that if F_{n} = y^{p} then F_{n} is odd.

Thus suppose that F_{n} (and hence y) is even. Lemma 3.2 tells us that 5y^{2p} + 4 = L_{n}^{2}. Since y even, we see that 2 ∥ L_{n}. Let z = y/2 and

x = \{ \begin{matrix}L_{n}/2, & if L_{n} ≡ 2 (mod 8), \\ −L_{n}/2, & if L_{n} ≡ 6 (mod 8) . \end{matrix}

Thus x ≡ 1 (mod 4) and

2^{2p−2} · 5z^{2p} + 1 = x^{2}.

Following [5, Section 2] we associate to this equation the Frey curve

Y^{2} + XY = X^{3} + (\frac{x − 1}{4}) X^{2} + 2^{2p−8} · 5z^{2p}X.

Applying level-lowering [5, Section 3] shows that the Galois representation arises from a cusp form of weight 2 and level 10. Since there are no such cusp forms we get a contradiction. (This is essentially the same argument used in the proof of Fermat’s Last Theorem.) It is noted that the argument here fails for n = 0 since in this case the Frey curve is singular.

We deduce that F_{n} is odd, and so that F_{k} = U^{p} and L_{k} = V^{p} for some positive integers U, V. By Lemma 5.1 we know that k ≡ ±1 (mod 6). This completes the proof of Lemma 5.2. □

6. Reduction to the Prime Index Case

In this section we reduce our problem to the assumption that the index n is prime, as in the following pair of Propositions.

Proposition 6.1. If there is a perfect power in the Fibonacci sequence not listed in Theorem 1 then there is a solution to the equation

(17)  F_{n} = y^{p},  n > 25000, p ≥ 7 with n, p prime.

Proposition 6.2. If there is a perfect power in the Lucas sequence not listed in Theorem 2 then there is a solution to the equation

(18)  L_{n} = y^{p},  n > 25000, p ≥ 7 with n, p prime.

After proving these two propositions the remainder of this paper will be devoted to showing the there are no solutions to equations (17) and (18).

Proof of Proposition 6.1. If F_{n} = y^{p} with n is odd then this just the result of Pethő and Robbins quoted in Section 2 together with our Proposition 4.1. Suppose n = 2k. By Lemma 5.2 we know that k is odd and F_{k} = U^{p} for some integer U. Now simply apply the result of Pethő and Robbins again together with Proposition 4.1. □

Proof of Proposition 6.2. Suppose that L_{n} = y^{p} where n ≠ 1, 3 and p ≥ 7. By Lemma 5.1 we know that n ≡ ±1 (mod 6), and so n is odd. If n is prime then the result follows from Proposition 4.2. Thus suppose that n is composite and let q be its smallest prime factor. Write n = kq, where k > 1. Then L_{n} = y^{p} can be rewritten as

(19) (ω^{k} − ω^{−k})(ω^{k(q−1)} + ω^{k(q−3)} + ⋯ + ω^{−k(q−3)} + ω^{−k(q−1)}) = ω^{n} − ω^{−n} = y^{p}.

It is straightforward to see that the two factors on the left-hand side are in ℤ and that their greatest common factor divides q. [Proof: If this gcd is d then ω^{2k} ≡ 1 (mod d) and ω^{k(q−1)} + ⋯ + ω^{−k(q−1)} ≡ q ≡ 0 (mod d), which shows that d divides q.] Suppose that q divides the two factors. Then we see that

ω^{2k} ≡ 1 (mod π)

for some prime π of O lying above q. But ω^{2} − 1 = ω and so ω^{2} ≢ 1 (mod π). It follows that the order of the image of ω^{2} in (O/π)^{∗} is not 1 and that it divides k and hence n. But #(O/π)^{∗} is either q −1 or q^{2} −1. It follows that some non-trivial factor of n divides (q − 1)(q + 1). Moreover, n is odd, and all odd prime factors of (q − 1)(q + 1) are smaller than q. This contradicts the assumption that q is the smallest prime factor of n.

We deduce that q does not divide the factors on the right-hand side of (19). Hence L_{k} = ω^{k} − ω^{−k} = y_{1}^{p} for some integer y_{1}. If k is prime then the proof is complete by invoking Proposition 4.2. Otherwise apply the above argument recursively. □

7. Level-Lowering for Fibonacci - The Odd Index Case

Previously we have used a Frey curve and level-lowering to obtain information about solutions of F_{n} = y^{p} for even n. In this section we associate a Frey curve to any solution of equation (17).

Suppose that (n, y, p) is a solution to (17). Thus n and p are primes with p ≥ 7 and n > 25000. Let

(20)  H_{n} = \{ \begin{matrix}L_{n}, & if n ≡ 1 (mod 6), \\ −L_{n}, & if n ≡ 5 (mod 6). \end{matrix}

Lemma 7.1. With notation as above, H_{n} ≡ 1 (mod 4) and

(21)  5y^{2p} − 4 = H_{n}^{2}.

The Lemma follows immediately from Lemma 3.1 and Lemma 3.4.

We associate to the solution (n, y, p) the Frey curve

(22)  E_{n} :  Y^{2} = X^{3} + H_{n}X^{2} − X.

We now come to level-lowering. Let E be the following elliptic curve over ℚ:

(23)  E : Y^{2} = X^{3} + X^{2} − X;

this is curve 20A2 in Cremona’s tables [17]. As before, write ρ_{p}(E) for the Galois representation on the p-torsion of E, and let ρ_{p}(E_{n}) be the corresponding Galois representation on the p-torsion of E_{n}. If l is a prime, let a_{l}(E) be the trace of Frobenius of the curve E at l, and let a_{l}(E_{n}) denote the corresponding trace of Frobenius of E_{n}.

Proposition 7.2. Suppose that (n, y, p) is a solution to (17). With notation as above, the Galois representations ρ_{p}(E_{n}), ρ_{p}(E) are isomorphic. Moreover, for any prime l ≠ 2, 5,

(i) a_{l}(E_{n}) ≡ a_{l}(E) (mod p) if l ∤ y,

(ii) l + 1 ≡ ±a_{l}(E) (mod p) if l | y.

Proof. First we apply the results of [5, Sections 2,3]. From these we know that ρ_{p}(E_{n}) arises from a cuspidal newform of weight 2, level 20, and trivial Nebentypus character. (In applying the results of [5] we need Lemma 7.1). However S_{2}(Γ_{0}(20)) has dimension 1. Moreover, the curve E is (up to isogeny) the unique curve of conductor 20. It follows that ρ_{p}(E) and ρ_{p}(E_{n}) are isomorphic.

The rest of the Proposition follows from [24, Proposition 3], and the fact that if l ≠ 2, 5 and l | y then l is a prime of multiplicative reduction for E_{n} and so a_{l}(E_{n}) = ±1. □

Proposition 7.2 is useful in several stages of our proof of Theorem 1. The following Proposition is needed later, and follows from Proposition 7.2 and some computational work.

Proposition 7.3. If (n, y, p) is any solution to equation (17) with p < 2×10^{8} then n ≡ ±1 (mod p).

The idea behind the proof is inspired by a method of Kraus (see [23] or [48]) but there are added complications in our situation: for any prime p the equation F_{n} = y^{p} has the solution (n, y) = (1, 1), and also the solution (n, y) = (−1, 1) (obtained by extrapolating the definition of the Fibonacci sequence backwards).

Before proving Proposition 7.3 we start with a little motivation. Suppose that p ≥ 7 is a prime, and we find some small positive integer k such that l = 2kp + 1 is prime, and l ≡ ±1 (mod 5). It follows that 5 is a quadratic residue modulo l, and we choose an element in 𝔽_{l} which we conveniently denote by \sqrt{5}, satisfying (\sqrt{5})^{2} ≡ 5 (mod l). We may then consider ω, τ (defined in (8)) as elements of 𝔽_{l}.

Consider the equation F_{n} = y^{p}. Now l − 1 = 2kp, with k is small. This means that y^{p} comes from a small subset of 𝔽_{l}. We can now use the level-lowering to predict the values of y^{p}. Hopefully, we may find that the only value of y^{p} modulo l predicted by the level-lowering and also belonging to our small subset are ±1. Under a further minor hypothesis we can show that this implies that n ≡ ±1 (mod p). If a particular value of k does not work, we may continue trying until a suitable k is found.

We make all this precise. Suppose as above that l, p are primes with l = 2kp + 1 and l ≡ ±1 (mod 5). Define

A(p, k) = \{ζ ∈ (𝔽_{l}^{∗})^{2p} \\{1\} : (\frac{5ζ − 4}{l}) = 0 or 1\} .

For each ζ ∈ A(p, k), choose an integer δ_{ζ} such that

δ_{ζ}^{2} ≡ 5ζ − 4 (mod l).

Let

E^{ζ} : Y^{2} = X^{3} + δ_{ζ}X^{2} − X.

As above, E will denote the elliptic curve 20A2.

Lemma 7.4. Suppose p ≥ 7 is a prime. Suppose there exists an integer k satisfying the following conditions:

(a) The integer l = 2kp + 1 is prime, and l ≡ ±1 (mod 5).

(b) The order of ω modulo l is divisible by p; equivalently ω^{2k} ≢ 1 (mod l).

(c) For all ζ ∈ A(p, k), we have

a_{l}(E^{ζ})^{2} ≢ a_{l}(E)^{2} (mod p).

Then any solution to the equation (17) must satisfy n ≡ ±1 (mod p).

Proof. Suppose p, k satisfy the conditions of the Lemma, and that (n, y, p) is a solution to equation (17). Let H_{n} and E_{n} be as above. Thus H_{n} satisfies (21).

We will prove first that l ∤ y. Suppose that l | y. Then (ω^{n} + ω^{−n})/\sqrt{5} = F_{n} = y^{p} ≡ 0 (mod l) and so ω^{4n} ≡ 1 (mod l). From (b) we deduce that p | 4n. However, the integer n is prime, and so p = n. This is impossible, since otherwise F_{p} = y^{p} and clearly 1 < F_{p} < 2^{p}. Hence l ∤ y.

Next we will show that y^{2p} ≡ 1 (mod l). Thus suppose that y^{2p} ≢ 1 (mod l). By Lemma 7.1 there is some ζ ∈ A(p, k) such that y^{2p} ≡ ζ (mod l). Further δ_{ζ} ≡ ±H_{n} (mod l). It follows that a_{l}(E^{ζ}) = ±a_{l}(E_{n}). Applying Proposition 7.2 again, we see that a_{l}(E_{n}) ≡ a_{l}(E) (mod p). These congruences now contradict condition (c).

We have finally proven that y^{2p} ≡ 1 (mod l). By equation (21) we see that H_{n} ≡ ±1 (mod l). Since n is odd (in fact an odd prime), and τ = −ω^{−1}, we get from the definition of H_{n} that ω^{2n} ± ω^{n} − 1 ≡ 0 (mod l). Solving this we find that ω^{n} ≡ ±ω^{±1} (mod l). Thus

ω^{2(n+1)} ≡ 1 (mod l)  or  ω^{2(n−1)} ≡ 1 (mod l).

However, condition (b) of the Lemma assures us that the order of ω modulo l is divisible by p. This immediately shows that n ≡ ±1 (mod p) as required. □

Proof of Proposition 7.3. We used a PARI/GP program to check that for each prime in the range 7 ≤ p < 2 × 10^{8}, there is some k satisfying conditions (a), (b) and (c) of Lemma 7.4. This took approximately 41 hours on a 1.7 GHz Pentium 4. This proves the Proposition. □

8. Level-lowering for Lucas - The Odd Index Case

In this section we associate a Frey curve to solutions of (18) and apply levellowering. Our objective is to give the Lucas analogue of Propositions 7.2 and 7.3.

Suppose then that (n, y, p) is a solution to (18), and we associate to this solution the Frey curve

(24)  E_{n} :  Y^{2} = X^{3} − 5F_{n}X^{2} + 5X.

Let E be the elliptic curve 200B1 in Cremona’s tables [17]. This has the model

(25)  E : Y^{2} = X^{3} + X^{2} − 3X − 2.

Proposition 8.1. Suppose that (n, y, p) is a solution to (18). With notation as above, the Galois representations ρ_{p}(E_{n}), ρ_{p}(E) are isomorphic. Moreover, for any prime l ≠ 2, 5

(i) a_{l}(E_{n}) ≡ a_{l}(E) (mod p) if l ∤ y,

(ii) l + 1 ≡ ±a_{l}(E) (mod p) if l | y.

Proposition 8.2. If (n, y, p) is any solution to equation (18) then n ≡ ±1 (mod p).

The proof of Proposition 8.1 is by no means as simple as the proof of the corresponding Proposition for Fibonacci. However, given Proposition 8.1, the proof of Proposition 8.2 is a fairly trivial modification of the proof of Proposition 7.3 and we omit it. The reader will notice that in Proposition 7.3 (the Fibonacci case) we suppose that p < 2 × 10^{8}, but in the Lucas case above there is no such assumption. This is because we know by a result of Pethő quoted in Section 2 that p < 13222, which also means that our program for the proof of Proposition 8.2 takes only a few seconds. Later on we will prove a much better bound for p in the Lucas case, namely p ≤ 283, but we do not need such a good bound for the proof of Proposition 8.2.

8.1. Level-Lowering. Let E^{1}, …, E^{5} be the elliptic curves 200A1, 200B1, 200C1, 200D1, 200E1 in Cremona’s tables [17]. Note that E^{2} is just our elliptic curve E defined above. We follow the notation of previous sections with regard to Galois representations and traces of Frobenius.

Lemma 8.3. Suppose (n, y, p) is a solution to equation (18). With notation as above, the Galois representation ρ_{p}(E_{n}) is isomorphic to one of the Galois representations ρ_{p}(E^{1}), …, ρ_{p}(E^{5}). Moreover, if ρ_{p}(E_{n}) is isomorphic to ρ_{p}(E^{i}) then, for any prime l ≠ 2, 5,

(i) a_{l}(E_{n}) ≡ a_{l}(E^{i}) (mod p) if l ∤ y.

(ii) l + 1 ≡ ±a_{l}(E^{i}) (mod p) if l | y.

Proof. By the results of [5, Sections 2, 3], ρ_{p}(E_{n}) arises from a cuspidal newform of weight 2, level 200, and trivial Nebentypus character. For this we need Lemma 3.2. However using MAGMA we find that the dimension of newforms of weight 2 and level 200 is 5. However, there are (up to isogeny) exactly 5 elliptic curves of conductor 200, and these are the curves E^{1}, …, E^{5} above.

The rest of the lemma follows from [24, Proposition 3], and the fact that if l ≠ 2, 5 and l | y then l is a prime of multiplicative reduction for E_{n} and so a_{l}(E_{n}) = ±1. □

8.2. Eliminating Newforms. Lemma 8.3 relates the Galois representation of E_{n} to too many Galois representations. We now eliminate all but one of them.

Suppose l ≠ 2, 5 is a prime. Define d_{l}(E_{n}, E^{i}) = a_{l}(E_{n}) − a_{l}(E^{i}). Let M(l) be given by (13). Recall that (Lemma 3.3) the residue class of F_{n} modulo l, and hence the Frey curve E_{n} modulo l, depends only on the residue class of n modulo M(l). We see that the following definitions make sense: let

T_{l}(E^{i}) = {m ∈ ℤ/M(l) : d_{l}(E_{m}, E^{i}) = 0} ,
g_{l}(E^{i}) = lcm {d_{l}(E_{m}, E^{i}) : m ∈ ℤ/M(l), m ∉ T_{l}(E^{i})} ,

and

h_{l}(E^{i}) = \{ \begin{matrix}g_{l}(E^{i}), & if l ≡ ±2 (mod 5), \\ lcm(g_{l}(E^{i}), l + 1 − a_{l}(E^{i}), l + 1 + a_{l}(E^{i})), & if l ≡ ±1 (mod 5). \end{matrix}

Lemma 8.4. Suppose that l ≠ 2, 5 is a prime. If ρ_{p}(E_{n}) is isomorphic to ρ_{p}(E^{(i)}) then either the reduction of n modulo M(l) belongs to T_{l}(E^{i}) or else p divides h_{l}(E^{i}).

Proof. Recall that by Lemma 3.2, y^{2p} = 5F_{n}^{2} − 4. Thus if l ≡ ±2 (mod 5) then l does not divide y. The Lemma now follows from Lemma 8.3. □

Given two positive integers M_{1}, M_{2}, and two sets T_{1} ⊂ ℤ/M_{1} and T_{2} ⊂ ℤ/M_{2} we loosely define their ‘intersection’ T_{1} ∩ T_{2} to be the set of all elements of ℤ/lcm(M_{1}, M_{2}) whose reduction modulo M_{1} and M_{2} is respectively in T_{1} and T_{2}.

We are now ready to prove Proposition 8.1.

Proof of Proposition 8.1. Suppose that (n, y, p) is a solution to (18). Thus p ≥ 7 and n ≡ ±1 (mod 6). We recall that the elliptic curves E and E^{2} are one and the same. Thus the Proposition follows from Lemma 8.3 if we can demonstrate that ρ_{p}(E_{n}) cannot be isomorphic to the corresponding representation for E^{1}, E^{3}, E^{4} and E^{5}. Fix i one of 1, 3, 4, 5. By the above Lemma, to show that the Galois representations of E_{n} and E^{i} are not isomorphic it it is enough to produce a set of primes S = {l_{1}, …, l_{r}} all neither 2 nor 5 satisfying

(1) For every l ∈ S the integer h_{l}(E^{i}) is not divisible by any prime number greater than 5,

(2) (∩_{l∈S}T_{l}(E^{i})) ∩ T_{0} = ∅,

where T_{0} = \{\overline{1}, \overline{5}\} ⊆ ℤ/6Z. With the help of a short PARI/GP program we find that we can take S = {3} to eliminate E^{1}, E^{3}, E^{5} and S = {3, 7, 11, 13, 17, 19, 23} to eliminate E^{4}.

We note in passing that the j-invariant of the curve E^{3} is 55296/5, and so the argument used in the proof of Lemma 5.1 also shows that the Galois representation ρ_{p}(E^{3}) is not isomorphic to ρ(E_{n}). This argument does not apply to the Galois representations of E^{1}, E^{4}, E^{5} as these have integral j-invariants. □

9. Bounds for n in terms of p

Our objective in this section is to obtain bounds for n in terms of p for solutions to (17) and (18). It follows from Baker’s theory of linear forms in logarithms (see for example the book of Shorey and Tijdeman [46]) that the sizes of n and y are bounded in terms of p. Unfortunately, these bounds are huge, and there is no hope to complete the resolution of our equations by proceeding in that way. We however recall, by Lemma 3.1 (and 3.2), that it is sufficient to obtain upper bounds for the size of integer solutions to the equation x^{2} + 4 = 5y^{2p} (and one like it in the Lucas case). As is explained below, this equation easily reduces to a Thue equation, and we may apply the results of Bugeaud and Győry [10] to get an upper bound for x and y. However, it is of much interest to rework the proof of Bugeaud and Győry in our particular context. On the one hand, our particular equation has some nice properties not taken into account in the general result of [10], and, on the other hand, there has been an important improvement, due to Matveev, in the theory of linear forms in logarithms since [10] has appeared. Altogether we actually compute a much better upper bound than the one obtained by applying the main result of [10] directly.

Before giving a precise statement of the main results of this section, we need an upper bound for the regulators of number fields. Several explicit upper bounds for regulators of a number field are available in the literature; see for example [28] and [47]. We have however found it best to use a result of Landau. Lemma 9.1. Let 𝕂 be a number field with degree d = r_{1} +2r_{2} where r_{1} and r_{2} are numbers of real and complex embeddings. Denote the discriminant by D_{𝕂} and the regulator by R_{𝕂}, and the number of roots of unity in 𝕂 by w. Suppose, moreover, that L is a real number such that D_{𝕂} ≤ L. Let

a = 2^{−r_{2}} π^{−d/2} \sqrt{L}.

Define the function f_{𝕂}(L, s) by

f_{𝕂}(L, s) = 2^{−r_{1}} w a^{s} (Γ(s/2))^{r_{1}} (Γ(s))^{r_{2}}s^{d+1} (s − 1)^{1−d},

and let C_{𝕂}(L) = min {f_{K}(L, 2 − t/1000) : t = 0, 1, …, 999}. Then R_{𝕂} < C_{𝕂}(L).

Proof. Landau [25] proved the inequality R_{𝕂} < f_{𝕂}(D_{𝕂}, s) for all s > 1. It is thus clear that R_{𝕂} < C_{𝕂}(L).

Perhaps a comment is in order. For a complicated number field of high degree it is difficult to calculate the discriminant D_{𝕂} exactly, though it is easy to give an upper bound L for its size. It is also difficult to minimise the function f_{𝕂}(L, s) analytically, but we have found that the above gives an accurate enough result, which is easy to calculate on a computer. □

We are now ready to state our upper bound for n in terms of p for the Fibonacci and Lucas cases.

Proposition 9.2. Suppose p ≥ 7 is prime. Let α be any root of the polynomial

(26)  P (X) := ∑_{k=0}^{p} (−4)^{[(p−k)/2]} \binom{p}{k} X^{k},

and let 𝕂 = ℚ(α). Let C_{𝕂}(·) be as in Lemma 9.1 and

Θ = 3.9 · 30^{p+3} p^{13/2} (p − 1)^{p+1} ((p − 1)!)^{2} (3p + 2) (1 + log(p(p − 1))) C_{𝕂}(10^{p−1}p^{p}).

If (n, y, p) satisfies the equation and conditions (17) then n < 2.5pΘ log Θ.

Proposition 9.3. Suppose p ≥ 7 is prime. Denote by \sqrt[p]{ω} the real p-th root of ω (where ω is given by (8)) and set 𝕂 = ℚ(\sqrt{5}, \sqrt[p]{ω}), and let C_{𝕂}(·) be as in Lemma 9.1. Let

Θ = 67 · 30^{p+5}(p − 1)^{p+2}p^{3} (p + 2)^{5.5} (p!)^{2} (1 + log(2p(p − 1))) C_{𝕂}(5^{p}p^{2p}).

If (n, y, p) satisfies the equation and conditions (18) then n < 2.5 p Θ log Θ.

9.1. Preliminaries. We first need a lower bound for linear forms in logarithms due to Matveev. Let 𝕃 be a number field of degree D, let α_{1}, …, α_{n} be non-zero elements of 𝕃 and b_{1}, …, b_{n} be rational integers. Set

B = max{|b_{1}|, …, |b_{n}|},

and

Λ = α_{1}^{b_{1}} … α_{n}^{b_{n}} − 1.

Let h denote the absolute logarithmic height and let A_{1}, …, A_{n} be real numbers with

A_{j} ≥ h′(α_{j}) := max{D h(α_{j}), | log α_{j}|, 0.16}, 1 ≤ j ≤ n.

We call h′ the modified height (with respect to the field 𝕃). With this notation, the main result of Matveev [35] implies the following estimate.

Theorem 9.4. Assume that Λ is non-zero. We then have

log |Λ| > −3 · 30^{n+4} (n + 1)^{5.5} D^{2} (1 + log D) (1 + log nB) A_{1} … A_{n}.

Furthermore, if 𝕃 is real, we have

log |Λ| > −1.4 · 30^{n+3} n^{4.5} D^{2} (1 + log D) (1 + log B) A_{1} … A_{n}.

Proof. Denote by log the principal determination of the logarithm. If |Λ| < 1/3, then there exists an integer b_{0}, with |b_{0}| ≤ n B, such that

Ω := |b_{0} log(−1) + b_{1} log α_{1} + … + b_{n} log α_{n}|

satisfies |Λ| ≥ Ω/2. Noticing that h′(−1) = π, and that b_{0} = 0 if 𝕃 is real, we deduce our lower bounds from Corollary 2.3 of Matveev [35]. □

We also need some precise results from algebraic number theory. In the rest of this Section, let 𝕂 denote a number field of degree d = r_{1} + 2r_{2} and unit rank r = r_{1} + r_{2} − 1 with r > 0. Let R_{𝕂} and D_{𝕂} be its regulator and discriminant, respectively. Let w denote the number of roots of unity in 𝕂. Observe that w = 2 if r_{1} > 0.

Lemma 9.5. For every algebraic integer η which generates 𝕂 we have

d h(η) ≥ \frac{log |D_{𝕂}| − d log d}{2(d − 1)}.

Proof. As in Mignotte [37], it follows from the Hadamard inequality that

|D_{𝕂}| ≤ Discr(1, η, …, η^{d−1})^{2} ≤ d^{d} M(η)^{2(d−1)},

where M(η) is the Mahler measure of η. Since d log M(η) = h(η), the lemma is proved. □

In the course of our proof, we use fundamental systems of units in 𝕂 with specific properties.

Lemma 9.6. There exists in 𝕂 a fundamental system {ε_{1}, …, ε_{r}} of units such that

∏_{i=1}^{r} h(ε_{i}) ≤ 2^{1−r} (r!)^{2} d^{−r} R_{𝕂},

and the absolute values of the entries of the inverse matrix of (log |ε_{i}|_{v_{j}})_{i,j=1,...,r} do not exceed (r!)^{2} 2^{−r} (log(3d))^{3}.

Proof. This is Lemma 1 of [9] combined with a result of Voutier [50] (see [10]) giving a lower bound for the height of any non-zero algebraic number which is not a root of unity. □

Furthermore, we need sharp bounds for discriminants of number fields in a relative extension.

Lemma 9.7. Let 𝕂_{1} and 𝕂_{2} be number fields with 𝕂_{1} ⊆ 𝕂_{2} and denote the discriminant of the extension 𝕂_{2}/𝕂_{1} by D_{𝕂_{2}/𝕂_{1}}. Then

|D_{𝕂_{2}}| = |D_{𝕂_{1}}|^{[𝕂_{2}:𝕂_{1}]} |N_{𝕂_{1}/ℚ}(D_{𝕂_{2}/𝕂_{1}})|.

Proof. This is Proposition 4.9 of [38]. □

9.2. Proof of Proposition 9.2. We now turn our attention to the proof of Proposition 9.2 and so to equation (17). Lemma 3.1 reduces the problem to solving the superelliptic equation x^{2} + 4 = 5y^{2p}. Factorising the left-hand side over ℤ[i], we deduce the existence of integers a and b with a^{2} + b^{2} = y^{2} and

(27)  ±4i = (2 + i)(a + ib)^{p} − (2 − i)(a − ib)^{p}.

Dividing by 2i, we get

\begin{matrix}±2 = & 2 ∑_{k=0}^{[p/2]} \binom{p}{2k} a^{2k} (−1)^{(p−2k−1)/2} b^{p−2k} \\ + ∑_{k=0}^{[p/2]} \binom{p}{2k + 1} a^{2k+1} (−1)^{(p−2k−1)/2} b^{p−2k−1}. \end{matrix}

We infer that a is even. Consequently, (b, a/2) is an integer solution of the Thue equation

(28)  ∑_{k=0}^{p} (−4)^{[(p−k)/2]} \binom{p}{k} X^{k} Y^{p−k} = ±1.

To bound the size of the solutions of (28) we follow the general scheme of [10], which was also used in [12]. Let P (X) and α and 𝕂 be as in Proposition 9.2; we note that P (X) is the polynomial naturally associated to the Thue equation (28). We first need information on the number field 𝕂 and its Galois closure. We would like to thank Mr. Julien Haristoy for his help in proving the following Lemma.

Lemma 9.8. The field 𝕂 = ℚ(α) is totally real and its Galois closure 𝕃 has degree p(p − 1) over ℚ. Furthermore, the discriminant of 𝕂 divides 10^{p−1}p^{p}.

Proof. Observe that any root of the polynomial

Q(X) := \frac{1}{2i} · ((2 + i)(X + i)^{p} − (2 − i)(X − i)^{p}) = (−1)^{(p−1)/2}(X/2)^{p}P (2/X).

satisfies |X + i| = |X − i|, and so must be real. Hence, 𝕂 is a totally real field. Furthermore, 𝕃(i)/ℚ(i) is a Kummer extension got by adjoining the p-th roots of unity and the p-th roots of (2+i)/(2−i). Hence, this extension has degree p(p−1), and this is the same for 𝕃/ℚ.

Observe now that 𝕂(i) is generated over ℚ(i) by any root of either of the following two monic polynomials with coefficients in ℤ[i], namely Y^{p} − (2 + i)(2 − i)^{p−1} and Y^{p} − (2 − i)(2 + i)^{p−1}. Since the discriminant D_{1} (viewed as an algebraic integer in ℤ[i] and not as an ideal) of the extension 𝕂(i)/ℚ(i) divides the discriminant of each of these polynomials, D_{1} divides p^{p}5^{p−1}(2−i)^{(p−1)(p−2)} and p^{p}5^{p−1}(2+i)^{(p−1)(p−2)}. However, 2 + i and 2 − i are relatively prime, thus D_{1} divides 5^{p−1}p^{p}. Furthermore, estimating the discriminant of 𝕂(i)/ℚ in two different ways thanks to Lemma 9.7 gives

(29)  |D_{𝕂(i)}| = 4^{p}D_{1}^{2} = |D_{𝕂}|^{2} · |N_{𝕂/ℚ}(D_{𝕂(i)/𝕂})|.

Consequently, |D_{𝕂}| divides 5^{p−1}(2p)^{p}. We now refine this estimate by showing that 4 divides |N_{𝕂/ℚ}(D_{𝕂(i)/𝕂})|.

Suppose that the decomposition of the ideal 2 · O_{𝕂} in 𝕂/ℚ is given by

2 · O_{𝕂} = P_{1}^{e_{1}} … P_{s}^{e_{s}}.

At least one of the e_{i} is odd, since otherwise 2 would divide ∑_{i=1}^{s} e_{i}f_{i} = p. Thus, there is (at least) one prime P in O_{𝕂} lying above 2 whose ramification index e is odd: this prime must ramify in 𝕂(i)/𝕂, since 2i = (1 + i)^{2} in 𝕂(i). Thus P divides D_{𝕂(i)/𝕂} and so |N_{𝕂/ℚ}(D_{𝕂(i)/𝕂})| is divisible by 2. However, by (29), we know that |N_{𝕂/ℚ}(D_{𝕂(i)/𝕂})| is a square and so must be divisible by 4.

□

Remark: Based on computations for small p, it seems very likely that 10^{p−1}p^{p} is the exact value of |D_{𝕂}| for most p.

Since we introduce many changes in the proof of [10], we give a complete proof, rather than only quoting [10].

Let α_{1}, …, α_{p} be the roots of P (X) and let (X, Y) be a solution of (28). Without any loss of generality, we assume that α = α_{1} and |X −α_{1}Y | = min_{1≤j≤p} |X −α_{j}Y |. We will make repeated use of the fact that |α_{1}|, … |α_{p}| are neither greater than 4^{p}, nor smaller than 4^{−p} (since 4^{p} − 1 is an upper bound for the absolute values of the coefficients of P (X)). Assuming that Y is large enough, namely that

(30)  log |Y | ≥ (30p)^{p},

we get |Y | ≥ 2 min_{2≤j≤p} {|α_{1} − α_{j}|^{−1}} and

(31)  |X − α_{1}Y | ≤ 2^{p−1} ∏_{2≤j≤p} |α_{1} − α_{j}| |Y |^{−p+1} ≤ 2^{2p^{2}} |Y |^{−p+1},

since |X − α_{j}Y | ≥ |α_{1} − α_{j}| · |Y |/2 if |X − α_{1}Y | ≤ |α_{1} − α_{j}| · |Y |/2, for any j = 2, …, p.

From the ‘Siegel identity’

(X − α_{1}Y)(α_{2} − α_{3}) + (X − α_{2}Y)(α_{3} − α_{1}) + (X − α_{3}Y)(α_{1} − α_{2}) = 0

we have

Λ := \frac{α_{2} − α_{3}}{α_{3} − α_{1}} · \frac{X − α_{1}Y}{X − α_{2}Y} = \frac{X − α_{3}Y}{X − α_{2}Y} · \frac{α_{2} − α_{1}}{α_{3} − α_{1}} − 1.

Observe that the unit rank of 𝕂 is p − 1, since 𝕂 is totally real. Let ε_{1,1}, …, ε_{1,p−1} be a fundamental system of units in 𝕂 := ℚ(α_{1}) given by Lemma 9.6, hence, satisfying

(32)  ∏_{1≤i≤p−1} h(ε_{1,i}) ≤ \frac{((p − 1)!)^{2}}{2^{p−2}p^{p−1}} R_{𝕂},

where R_{𝕂} denotes the regulator of the field 𝕂. For j = 2, 3, denote by ε_{2,1}, …, ε_{2,p−1} and ε_{3,1}, …, ε_{3,p−1} the conjugates of ε_{1,1}, …, ε_{1,p−1} in ℚ(α_{2}) and ℚ(α_{3}), respectively. They all belong to the Galois closure 𝕃 of 𝕂.

The polynomial P (X) is monic and the left-hand side of (28) is a unit. Thus X − α_{1}Y is a unit. This simple observation appears to be crucial, since, roughly speaking, it allows us to gain a factor of size around p^{p}R_{𝕂} (compare with the proofs in [10] and in [12]).

Since the only roots of unity in 𝕂 are ±1, there exist integers b_{1}, …, b_{p−1} such that X − α_{1}Y = ±ε_{1,1}^{b_{1}} … ε_{1,p−1}^{b_{p−1}}, thus we have

Λ = ±(\frac{ε_{3,1}}{ε_{2,1}} )^{b_{1}} … (\frac{ε_{3,p−1}}{ε_{2,p−1}} )^{b_{p−1}} \frac{α_{2} − α_{1}}{α_{3} − α_{1}} − 1.

As in [10, 6.12], we infer from Lemma 9.6 that

B := max{|b_{1}|, …, |b_{p−1}|} ≤ 2^{2−p} p (p!)^{2} (log(3p))^{3} h(X − α_{1}Y)
≤ p^{2(p+1)} log |Y |,

(33)

by (31).

Further, we notice that

h(\frac{α_{2} − α_{1}}{α_{3} − α_{1}} ) = h(\frac{α_{2}/2 − α_{1}/2}{α_{3}/2 − α_{1}/2}) ≤ 4 h(α_{1}/2) + log 4 ≤ \frac{6p + 4}{p} log 2,

since we have (here and below, M(·) denotes the Mahler measure and H(·) stands for the naïve height)

h(α_{1}/2) ≤ \frac{log M(Q)}{p} ≤ \frac{log(\sqrt{p + 1} H(Q))}{p} ≤ \frac{log(2\sqrt{p + 1}\binom{p}{[p/2]})}{p} ≤ \frac{p + 1}{p} log 2.

Hence, with the modified height h′ related to the field 𝕃, we have

h′(\frac{α_{2} − α_{1}}{α_{3} − α_{1}} ) ≤ 2(3p + 2)(p − 1) log 2.

We may assume from Lemma 9.8 that the absolute value of the discriminant of 𝕂 is 10^{p−1}p^{p}, since the upper bound for n we aim to prove is an increasing function of |D_{𝕂}|. For i = 1, …, p − 1, we have h(ε_{1,i}) = h(ε_{2,i}) = h(ε_{3,i}) and, by Lemma 9.5, the height of the real algebraic integer ε_{1,i} satisfies h(ε_{1,i}) ≥ (log 10)/2. Thus, we get

h′(\frac{ε_{2,i}}{ε_{3,i}} ) ≤ 2p(p − 1)h(ε_{1,i}).

Consequently, using Theorem 9.4 in the real case with n = p and D = p(p − 1), we get

log |Λ| > −1.4 · 30^{p+3}p^{7/2}(p(p − 1))^{p+2} (3p + 2)(1 + log(p(p − 1)))

× (1 + log B) (2 log 2) 2^{p−1} ∏_{1≤i≤p−1} h(ε_{1,i}). (34)

Then, (32) gives us that

log |Λ| > −3.9 · 30^{p+3} p^{13/2} (p − 1)^{p+2} (3p + 2) ((p − 1)!)^{2}
× (1 + log(p(p − 1))) (1 + log B) R_{𝕂}.

(35)

Furthermore, it follows from (31) that

(36)  log |Λ| < 5p^{2} − (p − 1) log |Y |.

By (33), we have the upper bound

(37)  (1 + log B) < 3p^{2} + log log |Y |.

Finally, we observe that if F_{n} is a p-th power for some odd n, then there are integers X and Y such that (X, Y) is a solution of the Thue equation (28) and F_{n}^{2/p} = 4X^{2} + Y^{2}. Since |X| ≤ 1 + 4^{p}|Y | and F_{n} ≥ 0.4 · 1.6^{n} (for n ≥ 7), we derive from (30) that n < 2.2 p log |Y |, It then follows from (35), (36), and (37), together with Lemmas 9.1 and (9.8) that

n < 2.5 p Θ log Θ,

with

Θ = 3.9 · 30^{p+3} p^{13/2} (p − 1)^{p+1} (3p + 2) ((p − 1)!)^{2} (1 + log(p(p − 1))) C_{𝕂}(10^{p−1}p^{p}).

This proves Proposition 9.2.

9.3. Proof of Proposition 9.3. Suppose that (n, y, p) is a solution to the equation (18). In particular, we know

y^{p} = L_{n} = ω^{n} + τ^{n},

where we recall that ω = (1 + \sqrt{5})/2 and τ is conjugate of ω. We also know by Proposition 8.2 that n is congruent to ±1 modulo p. This means that there exists an integer ν such that

y^{p} − ω^{±1} (ω^{ν})^{p} = −τ^{n}.

Thus, we are left with an equation of Thue type, namely

(38)  X^{p} − ω^{±1} Y^{p} = unit in ℚ(\sqrt{5}).

We only deal with the + case, since the − case is entirely similar.

As in the statement of Proposition 9.3, denote by \sqrt[p]{ω} the real p-th root of ω and set 𝕂 = ℚ(\sqrt{5}, \sqrt[p]{ω}). Let ζ be a primitive p-th root of unity.

Lemma 9.9. The field 𝕂 has degree 2p and we have r_{1} = 2, r_{2} = p − 1 and r = p. The absolute value of the discriminant of 𝕂 is at most equal to 5^{p}p^{2p}. Its non-trivial subfields are ℚ(\sqrt{5}) and ℚ(\sqrt[p]{ω} − (\sqrt[p]{ω})^{−1}), whose discriminant is, in absolute value, at most equal to 5^{(p−1)/2}p^{p}. Furthermore, the Galois closure 𝕃 of 𝕂 is the field 𝕂(ζ), of degree 2p(p − 1).

Proof. We observe that the minimal defining polynomial of \sqrt[p]{ω} over ℤ is R(X) := X^{2p} − X^{p} − 1, thus we have

|D_{𝕂}| ≤ |N_{𝕂/ℚ}(R′(\sqrt[p]{ω}))| = |N_{𝕂/ℚ}(p\sqrt{5}(\sqrt[p]{ω})^{p−1})| = 5^{p} p^{2p}.

The fact that 𝕂 has only two non-trivial subfields, one of degree two, and another of degree p, is clear. Furthermore, since 𝕂 is obtained from the field ℚ(\sqrt[p]{ω} −(\sqrt[p]{ω})^{−1}) by adjoining \sqrt{5}, we get from Lemma 9.7 that the absolute value of the discriminant of the field ℚ(\sqrt[p]{ω} − (\sqrt[p]{ω})^{−1}) is not greater than 5^{(p−1)/2}p^{p}. Since the roots of the polynomial R(X) are the algebraic numbers \sqrt[p]{ω}, ζ \sqrt[p]{ω}, …, ζ^{p−1} \sqrt[p]{ω}, \sqrt[p]{τ}, ζ \sqrt[p]{τ}, …, ζ^{p−1} \sqrt[p]{τ}, we see that the Galois closure of 𝕂 is the field 𝕂(ζ). □

Let ε_{1,1}, …, ε_{1,p} be a fundamental system of units in 𝕂 given by Lemma 9.6. There exist integers b_{1}, …, b_{p} such that

X − \sqrt[p]{ω}Y = ±ε_{1,1}^{b_{1}} … ε_{1,p}^{b_{p}}.

Keep in mind that we are only interested in solutions (X, Y) of (38) with X integer and Y algebraic integer in the field ℚ(\sqrt{5}). Thus, X/Y is real, |X − \sqrt[p]{ω}Y | is small, and |X − ζ^{j} \sqrt[p]{ω}Y | is quite large for j = 1, …, p − 1 (consider the imaginary part). More precisely, for Y > 2, we get

(39)  |X − \sqrt[p]{ω}Y | ≤ p^{p} Y^{−p+1}.

Furthermore, setting B = max{|b_{1}|, …, |b_{p}|}, Lemma 9.6 yields that

\begin{aligned}B & ≤ 2^{1−p} p(p!)^{2}(log 6p)^{3} h(X − \sqrt[p]{ω}Y) \\ & ≤ p^{2(p+1)} log Y, \end{aligned} ; (40)

by our assumptions on X and Y.

Recall that ζ is a primitive p-th root of unity. We introduce the quantity

(41)  Λ := \frac{ζ − ζ^{2}}{ζ^{2} − 1} · \frac{X − \sqrt[p]{ω}Y}{X − ζ \sqrt[p]{ω}Y} = \frac{X − ζ^{2} \sqrt[p]{ω}Y}{X − ζ \sqrt[p]{ω}Y} · \frac{ζ − 1}{ζ^{2} − 1} − 1,

hence, the linear form in logarithms

Λ = (\frac{ε_{3,1}}{ε_{2,1}} )^{b_{1}} … (\frac{ε_{3,p}}{ε_{2,p}} )^{b_{p}} \frac{ζ − 1}{ζ^{2} − 1} − 1.

Let h′ denote the modified height related to the field 𝕃. We have

h′(\frac{ζ − 1}{ζ^{2} − 1}) ≤ 2p(p − 1) log 4,

and h′(ε_{1,i}) = h(ε_{1,i}). To check this, we observe that any algebraic unit in 𝕂 generates one of the subfields of 𝕂, and we apply Lemma 9.9 (we may assume that the absolute value of the discriminant of 𝕂 is 5^{p}p^{2p}, since the upper bound for n we aim to prove is an increasing function of |D_{𝕂}|). Using Theorem 9.4 in the complex case with n = p + 1 and D = 2p(p − 1), we get

log |Λ| > −3 · 30^{p+5}(p + 2)^{5.5}(2p(p − 1))^{p+3} (1 + log(2p(p − 1)))

× (1 + log(p + 1)B) (log 4) 2^{p} ∏_{1≤i≤p} h(ε_{1,i}). (42)

By (42) and Lemma 9.6, we get

log |Λ| > −3 · 30^{p+5}(p + 2)^{5.5}(2p(p − 1))^{p+3} (1 + log(2p(p − 1)))
× (1 + log((p + 1)B)) (log 4) 2^{−p+1} p^{−p} (p!)^{2} R_{𝕂}.

(43)

Furthermore, it follows from (39) and (41) that

(44)  log |Λ| < 5p^{2} − (p − 1) log |Y |.

Observe now that if L_{n} = y^{p} for some n, then equation (38) has a solution (X, Y) with Y = ω^{(n±1)/p}, and we get that −1 < L_{n} − ω^{±1}y^{p} < 0, thus n < 2.2 p log Y. It then follows from (40), (42)–(44), together with Lemma 9.1 that

n < 2.5 p Θ log Θ,

with

Θ = 67 · 30^{p+5}(p − 1)^{p+2}p^{3} (p + 2)^{5.5} (p!)^{2} (1 + log(2p(p − 1))) C_{𝕂}(5^{p}p^{2p}).

This completes the proof of Proposition 9.3.

10. The Sieve

In this section we use Propositions 7.2 and 9.2 (for the Fibonacci case) and Propositions 8.1 and 9.3 (for the Lucas case) together with a substantial computation to prove the following.

Proposition 10.1. If (n, y, p) satisfies the equation and conditions (17) then

p > 733,  n ≥ 1.033 × 10^{8733},  log y > 10^{8000}.

Proposition 10.2. If (n, y, p) satisfies the equation and conditions (18) then

p > 283,  n ≥ 4.938 × 10^{3383},  log y > 10^{3000}.

We will focus on the Fibonacci case; the Lucas case is entirely similar. Throughout this section we will follow the notation of Section 7. In particular, H_{n}, E_{n} and E are given respectively by (20), (22), and (23).

Lemma 10.3. Suppose l ≡ ±1 (mod 5) is prime and let

K(l) = lcm(l − 1, 6).

The trace of Frobenius a_{l}(E_{n}) depends only on the residue class of n modulo K(l).

Proof. By Lemma 3.3, the residue class of L_{n} modulo l depends only on the residue class of n modulo l − 1. From the definition of the integer H_{n} in (20) we see that H_{n} modulo l depends only on the residue class of n modulo K(l). The Lemma follows at once from the fact that the Frey curve E_{n} depends only on H_{n}. □

Suppose l ≡ ±1 (mod 5); we see by Lemma 10.3 that for n ∈ ℤ/K(l) it makes sense to talk of a_{l}(E_{n}). Suppose q ≥ 5 is a fixed prime. Define N (l, q) to be the subset of all n ∈ (ℤ/K(l))^{∗} such that

• either H_{n}^{2} + 4 ≢ 0 (mod l), and the integer a_{l}(E_{n}) − a_{l}(E) is divisible by some prime p > q,

• or H_{n}^{2} + 4 ≡ 0 (mod l) and one of the two integers l + 1 ± a_{l}(E) is divisible by some prime p > q.

Lemma 10.4. Suppose that q ≥ 5 is prime. Suppose l satisfies

(45) l ≡ ±1 (mod 5) is prime and every prime factor of l − 1 is < 25000.

If (n, p, y) satisfies the equation (17) and p > q then the reduction of n modulo K(l) belongs to N (l, q).

Proof. First observe, since n satisfies (17), that n is prime and n ≥ 25000. However, every prime divisor of l − 1 is < 25000 and the same must be true of K(l) = lcm(l − 1, 6). Thus the reduction of n modulo K(l) certainly belongs to (ℤ/K(l))^{∗}.

Next we recall (Lemma 7.1) that H_{n}^{2} + 4 = 5y^{2p} and so l | y if and only if H_{n}^{2}+4 ≡ 0 (mod l). The Lemma now immediately follows from Proposition 7.2. □

Given two positive integers M_{1}, M_{2}, and two sets T_{1} ⊂ ℤ/M_{1} and T_{2} ⊂ ℤ/M_{2} we recall that we have already defined their ‘intersection’ T_{1} ∩ T_{2} to be the set of all elements of ℤ/lcm(M_{1}, M_{2}) whose reduction modulo M_{1} and M_{2} is respectively in T_{1} and T_{2}.

The following Proposition will be our main tool in proving Proposition 10.1.

Proposition 10.5. Suppose S = {(l_{1}, q_{1}), …, (l_{t}, q_{t})} is a finite set of pairs of primes (l, q) where each l satisfies the condition (45) and each q is ≥ 5. Let K(S) = lcm(6, l_{1} − 1, …, l_{t} − 1), and

N (S) = ∩_{(l,q)∈S}N (l, q) ⊂ (ℤ/K(S))^{∗}.

Write

N (S) = \{\overline{1}, \overline{a}, \overline{b}, …\} where 1 < a < b < ⋯ < K(S).

If (n, y, p) is a solution to (17) with p > q_{1},…, q_{t} then n ≥ a.

Proof. Suppose that (n, y, p) is a solution to the equation (17). It follows immediately from Lemma 10.4 and the definition of ‘intersection’ that the reduction of n modulo K(S) belongs to N (S).

The reader can check for himself that \overline{1} is always in N (S). Moreover n ≠ 1 since we have n > 25000. Hence n ≥ a. □

The following Lemma will provide a useful check for our later calculations.

Lemma 10.6. With the notation of the above proposition, suppose that 4 | K(S). Then the residue classes of 1, −1, K(S)/2 + 1, K(S)/2 − 1 modulo K(S) all belong to the set N (S).

Proof. We note that H_{1} = H_{−1} = 1, and so E_{1} = E. It follows from the definition of N (l, p) that the residue classes of 1 and −1 modulo K(l) belong to N (l, q) for all pairs (l, q) ∈ S, and so residue classes of 1, −1 modulo K(S) belong to N (S).

Let us prove the same for n = K(S)/2 + 1; we will leave the other case to the reader. Suppose that (l, q) ∈ S. We would like to prove that the residue class of n modulo K(l) belongs to N (l, q). Write v_{2} : ℤ → ℤ_{≥0} ∪ {∞} for the 2-adic valuation.

Clearly (l − 1) divides K(S). If v_{2}(l − 1) < v_{2}(K(S)) then n ≡ 1 (mod K(l)) and we already know that \overline{1} ∈ N (l, q).

Thus suppose that v_{2}(l − 1) = v_{2}(K(S)). Since 4 divides K(S) we see that l ≡ 1 (mod 4). Further we can write

n = \frac{K(S)}{2} + 1 = k \frac{(l − 1)}{2} + 1

for some odd integer k. Note that

ω^{n} ≡ (ω^{\frac{l−1}{2}} )^{k} · ω ≡ ±ω (mod l),

and so

H_{n} ≡ ±L_{n} ≡ ±(ω^{n} − ω^{−n}) ≡ ±(ω − ω^{−1}) ≡ ±1 (mod l).

A glance at the definition of N (l, q) shows that we must prove that a_{l}(E_{n})−a_{l}(E) is divisible by some prime greater than q. Actually we will prove that a_{l}(E_{n}) = a_{l}(E). By comparing the equations for E and E_{n} we see that, modulo l, the two curves E and E_{n} are isomorphic when H(n) ≡ 1 (mod l). If H(n) ≡ −1 (mod l) then, modulo l, the curve E_{n} is the −1–twist of E. But (\frac{−1}{l}) = 1, and so again E and E_{n} are isomorphic modulo l. This proves that a_{l}(E_{n}) = a_{l}(E) and completes the proof. □

10.1. Proof of Proposition 10.1. Suppose that (n, y, p) is a solution to (17). Notice that Proposition 10.5 provides us with a way of obtaining lower bounds for the index n, and Proposition 9.2 provides us with a way of obtaining an upper bound for n (dependent on p). This gives us hope, given a particular prime p, that we may be able to obtain a contradiction using these two Propositions and so prove that there are no solutions for this particular p.

We wrote a PARI/GP program to carry out the above idea and derive the contradiction for the primes in the range 7 ≤ p ≤ 733.

We would like to give the reader the flavour of this computation by providing more for the proof that p > 7.

A priori, all we know about the exponent p is that p > 5, so we take q = 5. We let S = {(11, 5)}. Then

N (S) = N (11, 5) = \{\overline{1}, \overline{11}, \overline{19}, \overline{29}\} ⊂ ℤ/30,

where we used our program to calculate N (11, 5) from the definition of N (l, q). Next we look for primes l satisfying l ≡ ±1 (mod 5) and

(l − 1)|M, where M = 6983776800 = 2^{5} × 3^{3} × 5^{2} × 7 × 11 × ⋯ × 19

and for each such prime l we find we append (l, 5) to the set S, thus redefining N to be N (S)∩N (l, 5). We continue until N ⊂ ℤ/M and N (S) has four elements (we do not expect less than four elements by Lemma 10.6). The reader will no doubt expect that since most of our l − 1 are highly composite and have lots of common factors, the set N (S) will be a small set of congruences modulo a large modulus. After a few seconds we found that

N (S) = \{\overline{1}, \overline{3491888399}, \overline{3491888401}, \overline{6983776799}\} ⊂ ℤ/M.

We then replaced the value of M by M × 23 and continued until N (S) had exactly four elements and N ⊂ ℤ/M with this new value of M, etc. The entire computation took 42 seconds and proved that the the reduction of n belongs to a set

N = \{\overline{1}, \overline{a}, \overline{b}, \overline{c}\} ⊂ ℤ/M

where

a = 100704598854427777024179418273944411482999002799,
b = 100704598854427777024179418273944411482999002801,
c = 201409197708855554048358836547888822965998005599.

and the value of M is now

M = 2^{5} × 3^{3} × 5^{2} × 7 × 11 × ⋯ × 109.

Note that a ≈ 1.007 × 10^{47}.

By Proposition 10.5, we know that n ≥ a. However, if p = 7 then Proposition 9.2 implies that n < 2.639 × 10^{46}. This proves that p > 7. As a check on our computations, we note that a = M/2 − 1, b = M/2 + 1 and c = M − 1, which is entirely consistent with Lemma 10.6.

The next step is to prove that p > 11. We continue as above but now take q = 7. We note that N (l, 7) ⊆ N (l, 5) for any prime l, and that probably N (l, 7) is strictly smaller N (l, 5). Thus our sieve becomes more efficient.

The proof program took roughly 97 hours to run on a 1.7 GHz Intel Pentium 4. By the end of the proof the set S had 6262 pairs, and we have also shown that p > 733 and n ≥ 1.033 × 10^{8733}. To complete the proof we must show that log y ≥ 10^{8000}. However y^{p} = F_{n} = (ω^{n} − τ^{n})/\sqrt{5}. Taking logarithms and using Pethő’s result that p < 5.1×10^{17} (mentioned Section 2) we deduce that log y ≥ 10^{8000} with a huge margin.

10.2. Proof of Proposition 10.2. The proof of Proposition 10.2 is practically identical to the above proof of Proposition 10.1 and we omit almost all the details. We can take K(l) = l−1 in this case, and we let E_{n} and E be given by equations (24) and (25) respectively. If l ≡ ±1 (mod 5) and q ≥ 5 are primes we define N (l, q) to be the subset of all n ∈ (ℤ/K(l))^{∗} such that

• either 5F_{n}^{2} − 4 ≢ 0 (mod l), and the integer a_{l}(E_{n}) − a_{l}(E) is divisible by some prime p > q.

• or 5F_{n}^{2} − 4 ≡ 0 (mod l) and one of the two integers l + 1 ± a_{l}(E) is divisible

by some prime p > q. The other details are practically identical to the Fibonacci case. Since the lower bound for p that we are trying to establish is much smaller in the Lucas case our program runs much faster, and completes the proof on the same machine in about six hours.

11. A Refined Bound on p using Linear Form in two Logarithms

In the previous section we showed that if (n, y, p) is a solution to equation (18) then p > 283. In this section we will use the results of the paper of Laurent, Mignotte and Nesterenko [27] on linear forms in two logarithms to prove that p ≤ 283, thus completing the proof of Theorem 2.

The Fibonacci case still needs more work, since it yields a linear form in three logarithms. However, for now we are able to show the following.

Proposition 11.1. If (n, y, p) is a solution to equation (17) then p > 2 × 10^{8}.

Proof. Suppose that (n, y, p) is a solution to (17). The most obvious approach to obtain an upper bound for p is to consider

F_{n} = \frac{ω^{n} − ω^{−n}}{\sqrt{5}} = y^{p}

and the linear form in logarithms

Λ = n log ω − log \sqrt{5} − p log y.

Then a standard argument shows that

log |Λ| < −2p log y + 1.

We note that Λ is a linear form in three logarithms. In the remainder of this paper we will present a substantial improvement to the theory of linear form in three logarithms, and apply our result to show that p < 2 × 10^{8}.

For now, to prove the proposition, we argue by contradiction, assuming that p < 2 × 10^{8}. We then know from Proposition 7.3 that n ≡ ±1 (mod p) for primes p in this range. Write n = sp + ϵ, where ϵ = ±1. Note now that we can rewrite the expression Λ as

Λ = p log (ω^{s}/y) − log (\sqrt{5}ω^{−ϵ}),

which is now a linear form in two logarithms! We can apply Théorème 1 of [27] with

Λ = b_{1} log α_{1} − b_{2} log α_{2},

where

b_{1} = p, α_{1} = ω^{s}/y; b_{2} = 1, α_{2} = \sqrt{5} ω^{−ϵ}

and

log α_{2} = log \sqrt{5} − ϵ log ω, log α_{1} ≈ \frac{1}{p} log α_{2},

and

h(α_{2}) = \frac{log 10}{2}, h(α_{1}) ≤ log y + log 5.

Thus (with the notation of this result), we can take

a_{1} = (ρ − 1) log α_{1} + 4 (log y + log 5), a_{2} = (ρ − 1) log α_{2} + 2 log 10.

The case ϵ = −1

In this case, we choose (again with the notation of [27]) L = 8, ρ = 27.6, m = 0.209671121 and get

p ≤ 733.

The case ϵ = 1

In this case, we choose L = 7, ρ = 31.6, m = 0.218149476 and get

p ≤ 241.

In either case we have p ≤ 733 which contradicts Proposition 10.1. This completes the proof of the Proposition. □

As promised we also complete the resolution of the Lucas case by presenting the proof of Theorem 2.

Proof of Theorem 2. Suppose that (n, y, p) is a solution to equation (18). It is apparent, by Proposition 10.2, that all we have to do is to show that p ≤ 283, and to do this we apply [27].

Put

Λ = p log y − n log ω

where ω = (1 + \sqrt{5})/2. By Proposition 10.2 we know that

log y > 10^{6},

and indeed much more. Then (because L_{n} = ω^{n} + (−1/ω)^{n})

log |Λ| < −2p log y + 1.

Write n = sp + r with 0 ≤ r < p (notice that we do not use here the congruence n ≡ ±1 (mod p) proved above). This allows us to rewrite Λ as

Λ = p log(y/ω^{s}) − r log ω.

We apply [27, Proposition 1] with the notation D = 2 and

α_{1} = y/ω^{s}, α_{2} = ω, b_{1} = p, b_{2} = r, a_{1} = 2.00001 log(yω^{s}), a_{2} = (ρ + 1) log ω.

Here

b̃ = \frac{1}{ρ + 1} (\frac{p}{log ω} + \frac{r(1 + ρ)}{a_{1}}) ≈ \frac{1}{ρ + 1} \frac{p}{log ω} .

We get either

p ≤ μL(ρ + 1) log ω

or

log |Λ| > −KL log ρ − log(KL)

provided that

2K log θ + 2 log(2πK/e^{3/2}) − 3 log(KL) − \frac{c + log K}{3K} − \frac{a_{1}L}{3} − \frac{a_{2}L^{2}}{3} − \frac{2K}{μa_{1}} ≥ 0

and

μ((L − 1) log ρ + 2 log(2/θ) − 2(1.5 − log μ + log b̃)) ≥ \frac{L}{3}.

It is enough to take

log θ = \frac{1.01 × a_{1}L}{3 × 2μ^{2}a_{1}a_{2}L} = \frac{1.01}{6μ^{2}(ρ + 1) log ω} .

For ρ = 22.9, taking μ = 2/(3ω), working as above we first get p < 326 and then, after several iterations of the above argument,

p ≤ 283.

Remark: Using the congruence n ≡ ±1 (mod p) we could improve this estimate a little and get something like p ≤ 241. □

12. An Estimate on Linear Forms in Three Logarithms

12.1. Preliminaries.

Lemma 12.1. Let K, L, R, S, T be positive integers, put N = K^{2}L and assume N ≤ RST, put also

ℓ_{n} = ⌊\frac{n − 1}{K^{2}}⌋ , 1 ≤ n ≤ N,

and (r_{1}, …, r_{N}) ∈ {0, 1, …, R − 1}^{N}. Suppose that for each r ∈ {0, 1, …, R − 1} there are at most ST indices such that r_{j} = r. Then

|∑_{n=1}^{N} ℓ_{n}r_{n} − M| ≤ G_{R}

where

M = (\frac{L − 1}{2}) ∑_{n=1}^{N} r_{n}  and  G_{R} = \frac{NLR}{2} (\frac{1}{4} − \frac{N}{12RST} ) .

Proof. Apply [27, Lemme 4]. □

As in [3] or [52, page 192], for (k, m) ∈ ℕ^{2}, we put ∥(k, m)∥ = k + m. And we put

Θ(K_{0}, I) = min{∥(k_{1}, m_{1})∥ + ⋯ + ∥(k_{I}, m_{I})∥},

where the minimum is taken over if the I–tuples (k_{1}, m_{1}), …, (k_{I}, m_{I}) ∈ ℕ^{2} which are pairwise distinct and satisfy m_{1}, …, m_{I} ≤ K_{0}. Then, we have:

Lemma 12.2. Let K_{0}, L and I be positive integers with K_{0} ≥ 3, L ≥ 2 and I ≥ K_{0}(K_{0} + 1)/2. Then

Θ(K_{0}, I) ≥ (\frac{I^{2}}{2(K_{0} + 1)}) (1 + \frac{(K_{0} − 1)(K_{0} + 1)}{I} − \frac{K_{0}(K_{0} + 2)(K_{0} + 1)^{2}}{12I^{2}} ) .

Proof. Except for some details, this is [3, Lemma 1.4]. We follow more or less the proof of this result. The argument is elementary: the smallest value for the sum ∥(k_{1}, m_{1})∥+⋯+∥(k_{I}, m_{I})∥ is reached when we choose successively, for each integer n = 0, 1, … all the points in the domain

D_{n} = {(k, m) ∈ ℕ^{2}; m ≤ K_{0}, k + m = n},

and stop when the total number of points is I. Moreover,

Card(D_{n}) = \{ \begin{matrix}n + 1, & if n ≤ K_{0}, \\ K_{0} + 1, & if n ≥ K_{0}. \end{matrix}

With the notation of [3], the number I of points can be written as

I = (A − \frac{K_{0}}{2} ) (K_{0} + 1) + r, with 0 ≤ r ≤ K_{0},

provided that I ≥ K_{0}(K_{0} + 1)/2, which is a hypothesis of the Lemma. Then, the computation of [3] shows that

Θ(K_{0}, I) ≥ Θ̃(K_{0}, I) := \frac{K_{0} + 1}{2} (A(A − 1) − \frac{K_{0}(K_{0} − 1)}{3}) + rA.

In terms of I,

A = \frac{K_{0}}{2} + \frac{I − r}{K_{0} + 1}.

We have,

\frac{∂Θ̃}{∂r} = \frac{K_{0} + 1}{2} (2A − 1)\frac{∂A}{∂r} + A + r \frac{∂A}{∂r} = −\frac{2A − 1}{2} + A − \frac{r}{K_{0} + 1} = \frac{1}{2} − \frac{r}{K_{0} + 1},

which shows that the minimum of Θ̃ is reached either for r = 0 or r = K_{0}. It is easy to verify that Θ̃ takes the same value for r = 0 and r = K_{0} + 1 (which is indeed out of the range of r), this implies that the minimum is reached for r = 0. It follows that

\frac{2Θ(K_{0}, I)}{K_{0} + 1} ≥ (\frac{K_{0}}{2} + \frac{I}{K_{0} + 1}) (\frac{K_{0}}{2} + \frac{I}{K_{0} + 1} − 1) − \frac{K_{0}(K_{0} − 1)}{3}

= \frac{K_{0}^{2}}{4} + \frac{I^{2}}{(K_{0} + 1)^{2}} + \frac{K_{0}I}{K_{0} + 1} − \frac{K_{0}}{2} − \frac{I}{K_{0} + 1} − \frac{K_{0}^{2}}{3} + \frac{K_{0}}{3}

= \frac{I^{2}}{(K_{0} + 1)^{2}} + \frac{(K_{0} − 1)I}{K_{0} + 1} − \frac{K_{0}^{2}}{12} − \frac{K_{0}}{6}

= (\frac{I}{K_{0} + 1})^{2} (1 + \frac{(K_{0} − 1)(K_{0} + 1)}{I} − \frac{K_{0}(K_{0} + 2)(K_{0} + 1)^{2}}{12I^{2}} ) ,

which proves the lemma. □

The version of Liouville inequality that we use is the same as in [27, pages 298– 99]:

Lemma 12.3. Let α_{1}, α_{2}, α_{3} be non-zero algebraic numbers and f ∈ ℤ[X_{1}, X_{2}, X_{3}] such that f(α_{1}, α_{2}, α_{3}) ≠ 0, then

\begin{matrix}|f(α_{1}, α_{2}, α_{3})| ≥ & |f|^{−D+1}(α_{1}^{∗})^{d_{1}}(α_{2}^{∗})^{d_{2}}(α_{3}^{∗})^{d_{3}} \\ × exp\{−D(d_{1}h(α_{1}) + d_{2}h(α_{2}) + d_{3}h(α_{3}))\} \end{matrix}

where D = [ℚ(α_{1}, α_{2}, α_{3}) : ℚ] / [ℝ(α_{1}, α_{2}, α_{3}) : ℝ],

d_{i} = deg_{X_{i}} f, i = 1, 2, 3, |f| = max{|f(z_{1}, z_{2}, z_{3})|; |z_{i}| ≤ 1, i = 1, 2, 3},

and h(α) is the absolute logarithmic height of the algebraic number α, and α^{∗} = max{1, |α|}.

Lemma 12.4. let K > 1 be an integer, then

log ( ∏_{k=1}^{K−1} k!)^{\frac{4}{K(K−1)}} ≥ 2 log K − 3 + \frac{2 log(2πK/e^{3/2})}{K − 1} − \frac{2 + 6π^{−2} + log K}{3K(K − 1)} .

Proof. This is a consequence of a variant of the proof of [27, Lemme 8]. □

Now we present the type of linear forms in three logs that we shall study. For a while, we consider three non-zero algebraic numbers α_{1}, α_{2} and α_{3} and positive rational integers b_{1}, b_{2}, b_{3} with gcd(b_{1}, b_{2}, b_{3}) = 1, and the linear form

Λ = b_{2} log α_{2} − b_{1} log α_{1} − b_{3} log α_{3} ≠ 0,

without any loss in generality.

We restrict our study to the following cases, • the real case: α_{1}, α_{2} and α_{3} are real numbers > 1, and the logarithms of

the α_{i}’s are real (and > 0),

• the complex case: α_{1}, α_{2} and α_{3} are complex numbers of modulus one, and the logarithms of the α_{i}’s are arbitrary determinations of the logarithm.

This does not cause inconvenience in practice since in the general case we obviously always have

|Λ| ≥ max{|ℜ(Λ)|, |ℑ(Λ)|}.

Without loss of generality, we may assume that

b_{2}| log α_{2}| = b_{1}| log α_{1}| + b_{3}| log α_{3}| ± |Λ|.

We shall choose rational positive integers K, L, R, S, T, with K, L ≥ 2, we put N = K^{2}L and we assume RST ≥ N. Let a_{1}, a_{2}, a_{3} be positive real numbers.

The authors of [3] use Laurent’s method, and they consider a suitable interpolation determinant Δ. Let i be an index such that (k_{i}, m_{i}, ℓ_{i}) runs trough all triples of integers with 0 ≤ k_{i} ≤ K − 1, 0 ≤ m_{i} ≤ K − 1 and 0 ≤ ℓ_{i} ≤ L − 1. So each number 0, …, K − 1 occurs KL times as a k_{i}, and similarly as a m_{i}, and each number 0, …, L − 1 occurs K^{2} times as an ℓ_{i}. With the above definitions, let

Δ = det \{\binom{r_{j}b_{2} + s_{j}b_{1}}{k_{i}}\binom{t_{j}b_{2} + s_{j}b_{3}}{m_{i}}α_{1}^{ℓ_{i}r_{j}}α_{2}^{ℓ_{i}s_{j}}α_{3}^{ℓ_{i}t_{j}}\}

where r_{j}, s_{j}, t_{j} are non-negative integers less than R, S, T, respectively, such that (r_{j}, s_{j}, t_{j}) runs over N distinct triples. Put β_{1} = b_{1}/b_{2}, β_{3} = b_{3}/b_{2}. Let

λ_{i} = ℓ_{i} − \frac{L − 1}{2}, η_{0} = \frac{R − 1}{2} + β_{1} \frac{S − 1}{2}, ζ_{0} = \frac{T − 1}{2} + β_{3} \frac{S − 1}{2},

and

b = (b_{2}η_{0})(b_{2}ζ_{0}) ( ∏_{k=1}^{K−1} k!)^{− \frac{4}{K(K−1)}} .

Notice that, by Lemma 12.4,

log b ≤ log \frac{(R − 1)b_{2} + (S − 1)b_{1}}{2} + log \frac{(T − 1)b_{2} + (S − 1)b_{3}}{2}

− 2 log K + 3 − \frac{2 log(2πK/e^{3/2})}{K − 1} + \frac{2 + 6π^{−2} + log K}{3K(K − 1)} .

Then ∑_{i=0}^{N−1} λ_{i} = 0 and ([3, formula (2.1)])

α_{1}^{ℓ_{i}r_{j}}α_{2}^{ℓ_{i}s_{j}}α_{3}^{ℓ_{i}t_{j}} = α_{1}^{λ_{i}(r_{j}+s_{j}β_{1})}α_{3}^{λ_{i}(t_{j}+s_{j}β_{3})}(1 + θ_{ij}Λ′),

where

Λ′ = |Λ| · max \{\frac{LRe^{LR|Λ|/(2b_{1})}}{2b_{1}} , \frac{LSe^{LS|Λ|/(2b_{2})}}{2b_{2}} , \frac{LT e^{LT |Λ|/(2b_{3})}}{2b_{3}} \}

and where all |θ_{ij}| are ≤ 1.

CLASSICAL AND MODULAR APPROACHES 31

12.2. An upper bound for |Δ|. It is proved in [3] (last formula of page 111) that

Δ = α_{1}^{M_{1}}α_{2}^{M_{2}}α_{3}^{M_{3}} ∑_{I⊆N}(Λ′)^{N−|I|}Δ_{I}

where

M_{1} = \frac{L − 1}{2} ∑_{j=1}^{N} r_{j}, M_{2} = \frac{L − 1}{2} ∑_{j=1}^{N} s_{j}, M_{3} = \frac{L − 1}{2} ∑_{j=1}^{N} t_{j},

and where N = {0, 1, …, N − 1} and Δ_{I} is the determinant of a certain matrix M_{I} defined below. Let

ϕ_{j}(z, ζ) = \frac{b_{2}^{k_{i}+m_{i}}}{k_{i}! m_{i}} z^{k_{i}}ζ^{m_{i}}α_{1}^{λ_{i}z}α_{3}^{λ_{i}ζ},

[where α_{1}^{λ_{i}z} = exp(λ_{i}z log α_{1}) and similarly for α_{3}^{λ_{i}ζ}] and

Φ_{I}(x)_{ij} = \begin{cases}ϕ_{j}(xz_{j}, xζ_{j}) & if i ∈ I, \\ θ_{ij}ϕ_{j}(xz_{j}, xζ_{j}) & if i ∉ I. \end{cases}

Then, M_{I} = (Φ_{I}(1)_{ij}) and letting Ψ_{I}(x) = det(Φ_{I}(x)), gives

|Δ_{I}| = |det(Φ_{I}(1))| = |Ψ_{I}(1)|.

Now, let

J_{I} = order(Ψ, 0),

the maximum modulus principle implies

|Ψ_{I}(1)| ≤ ρ^{−J_{I}} · max_{|x|=ρ} |Ψ_{I}(x)|.

Since |z_{j}| ≤ η_{0} and |ζ_{j}| ≤ ζ_{0},

max_{|x|=ρ}|Ψ_{I}(x)| ≤N! \frac{b_{2}^{∑ k_{i}+∑ m_{i}}}{∏ k_{i}! ∏ m_{i}!} (ρη_{0})^{∑ k_{i}}(ρζ_{0})^{∑ m_{i}}

× max_{σ∈𝔖(N)} exp {ρ((∑ λ_{i}z_{σ(i)}) log α_{1} + (∑ λ_{i}ζ_{σ(i)}) log α_{2})} .

Put

g = \frac{1}{4} − \frac{N}{12RST} , G_{1} = \frac{NLR}{2} g, G_{2} = \frac{NLS}{2} g, G_{3} = \frac{NLT}{2} g,

then (see the proof of [3] p. 114 and use Lemma 12.1)

∑_{i=0}^{N−1} λ_{i}z_{σ(i)} ≤ G_{1} + β_{1}G_{2}, ∑_{i=0}^{N−1} λ_{i}ζ_{σ(i)} ≤ G_{3} + β_{3}G_{2}.

It follows that (recall that b_{2}| log α_{2}| = b_{1}| log α_{1}| + b_{3}| log α_{3}| ± |Λ|)

exp {ρ((∑ λ_{i}z_{σ(i)})| log α_{1}| + (∑ λ_{i}ζ_{σ(i)})| log α_{3}|)}
≤ exp {ρ((G_{1} + β_{1}G_{2})| log α_{1}| + (G_{3} + β_{3}G_{2})| log α_{3}|)}
≤ exp \{ρ (G_{1}| log α_{1}| + G_{2}(| log α_{2}| + \frac{|Λ|}{b_{2}}) + G_{3}| log α_{3}|)\} .

As in [3], we see that if

(46)  Λ′ < ρ^{−KL}

then

ρG_{2} \frac{|Λ|}{b_{2}} ≤ \frac{ρK^{2}L}{4ρ^{KL}} ≤ \frac{eK^{2}L}{4e^{KL}} ≤ \frac{K^{2}L^{2}}{e^{KL}} < 10^{−4}

for KL ≥ 15. Putting these estimates together, we get that condition (46) implies the upper bound

\begin{matrix}|Δ| ≤ 1.0001 α_{1}^{M_{1}+ρG_{1}} α_{2}^{M_{2}+ρG_{2}} α_{3}^{M_{3}+ρG_{3}} N! & × 2^{N} ρ^{∑(k_{i}+m_{i})} \\ ×\frac{(b_{2}η_{0})^{∑ k_{i}}}{∏ k_{i}!} × \frac{(b_{2}ζ_{0})^{∑ m_{i}}}{∏ m_{i}!} & × max_{σ∈𝔖(N)} \frac{|Λ′|^{N−|I|}}{ρ^{J_{I}}} \end{matrix}

where

J_{I} = order(Ψ_{I}, 0).

Under condition (46), we have

\frac{|Λ′|^{N−|I|}}{ρ^{J_{I}}} ≤ ρ^{−KL(N−|I|)−J_{I}}.

If |I| ≤ 0.5 N then

KL(N − |I|) ≥ 0.5 KLN ≥ \frac{NKL}{4} (1 + \frac{4}{L} + \frac{1}{2K − 1})

as soon as K ≥ 3 and L ≥ 5, conditions that we assume from now on. If |I| ≥ 0.5 N, then using [3, Lemma 1.3], we obtain

J_{I} ≥ Θ(K_{0}, |I|), for K_{0} = 2(K − 1) .

Now, |I| ≥ 0.5 K^{2}L implies |I| ≥ 2.5 K^{2} and using Lemma 12.2 we get (with the notation I = |I|)

KL(N − I) + J_{I} ≥ KL(N − I)

+ (\frac{I^{2}}{2(K_{0} + 1)}) (1 + \frac{(K_{0} − 1)(K_{0} + 1)}{I} − \frac{K_{0}(K_{0} + 2)(K_{0} + 1)^{2}}{12I^{2}} ) .

It is easy to verify that the right-hand side is a decreasing function of I in the range [N/2, N], since L ≥ 5, and we get (recall that N = K^{2}L and K_{0} = 2K − 2)

KL(N − |I|) + J_{I} ≥ \frac{N^{2}}{2(K_{0} + 1)} (1 + \frac{K_{0}^{2} − 1}{N} − \frac{K_{0}(K_{0} + 2)(K_{0} + 1)^{2}}{12N^{2}} )

= \frac{N^{2}}{4K} (\frac{2K}{K_{0} + 1} + \frac{2K(K_{0} − 1)}{N} − \frac{KK_{0}(K_{0} + 1)(K_{0} + 2)}{6N^{2}})

= \frac{N^{2}}{4K} (1 + \frac{1}{2K − 1} + \frac{2(2K − 3)}{KL} − \frac{2(K − 1)(2K − 1)}{3K^{2}L^{2}})

= \frac{N^{2}}{4K} (1 + \frac{4}{L} + \frac{1}{2K − 1} − \frac{4}{3L^{2}} − \frac{6}{KL} + \frac{2}{KL^{2}} − \frac{2}{3K^{2}L^{2}} )

≥ \frac{N^{2}}{4K} (1 + \frac{4}{L} + \frac{1}{2K − 1} − \frac{4}{3L^{2}} − \frac{6}{KL}) ,

because L ≥ 5, and this implies, in all cases,

KL(N − |I|) + J_{I} ≥ \frac{N^{2}}{4K} (1 + \frac{4}{L} + \frac{1}{2K − 1} − \frac{6}{KL} − \frac{4}{3L^{2}} ) .

CLASSICAL AND MODULAR APPROACHES 33

Thus, gathering all the previous estimates and using the relations

∑_{i=0}^{N−1} k_{i} = ∑_{i=0}^{N−1} m_{i} = \frac{(K − 1)K}{2} KL = \frac{N}{2} (K − 1),

and the definition of b, we obtain the following result. Proposition 12.5. With, the previous notation, if K ≥ 3, L ≥ 5 and Λ′ ≤ ρ^{−KL}, with ρ ≥ e, then

log |Δ| ≤ ∑_{i=1}^{3} M_{i} log |α_{i}| + ρ ∑_{i=1}^{3} G_{i}| log α_{i}| + log(N!) + N log 2 + \frac{N}{2} (K − 1) log b

− (\frac{NKL}{4} + \frac{NKL}{4(2K − 1)} − \frac{NK}{3L} − \frac{N}{2} ) log ρ + 0.0001.

12.3. A lower bound for |Δ|. Using our Liouville estimate (Lemma 12.3) and arguing as in [3], or [27, Lemme 6], we get the following. Proposition 12.6. If Δ ≠ 0 then

log |Δ| ≥ − \frac{D − 1}{2} N log N

+ ∑_{i=1}^{3}(M_{i} + G_{i}) log |α_{i}| − 2D ∑_{i=1}^{3} G_{i}h(α_{i}) − \frac{D − 1}{2}(K − 1) N log b.

Proof. We have Δ = P (α_{1}, α_{2}, α_{3}) where P ∈ ℤ[X_{1}, X_{2}, X_{3}] is given by P (X_{1}, X_{2}, X_{3}) =

∑_{σ∈𝔖_{N}} sg(σ) · ∏_{i=1}^{N} \binom{r_{σ(i)}b_{2} + s_{σ(i)}b_{1}}{k_{i}}\binom{t_{σ(i)}b_{2} + s_{σ(i)}b_{3}}{m_{i}}X_{1}^{n_{rσ}}X_{2}^{n_{sσ}}X_{3}^{n_{tσ}},

and where

n_{rσ} = ∑_{i=1}^{N} ℓ_{i}r_{σ(i)}, n_{sσ} = ∑_{i=1}^{N} ℓ_{i}s_{σ(i)}, n_{tσ} = ∑_{i=1}^{N} ℓ_{i}t_{σ(i)}.

By Lemma 12.1,

|deg_{X_{i}} P − M_{i}| ≤ G_{i}, i = 1, 2, 3.

Let

V_{i} = ⌊M_{i} + G_{i}⌋, U_{i} = ⌈M_{i} − G_{i}⌉, i = 1, 2, 3,

then

Δ = α_{1}^{V_{1}}α_{2}^{V_{2}}α_{3}^{V_{3}} P̃(α_{1}^{−1}, α_{2}^{−1}, α_{3}^{−1}),

where

deg_{X_{i}} P̃ ≤ V_{i} − U_{i}, i = 1, 2, 3.

By our Liouville estimate

log|P̃(α_{1}^{−1}, α_{2}^{−1}, α_{3}^{−1})| ≥ −(D − 1) log |P̃| − D ∑_{i=1}^{3}(V_{i} − U_{i}) h(α_{i}).

34 YANN BUGEAUD, MAURICE MIGNOTTE, SAMIR SIKSEK

Now we have to find an upper bound for |P̃| (or for |P | which is equal to |P̃|). By the multilinearity of the determinant, for all η, ζ ∈ ℂ,

P (z_{1}, z_{2}, z_{3}) = det (\frac{(r_{j}b_{2} + s_{j}b_{1} − η)^{k_{i}}}{k_{i}!} \frac{(t_{j}b_{2} + s_{j}b_{3} − ζ)^{m_{i}}}{m_{i}!} · z_{1}^{ℓ_{i}r_{j}} · z_{2}^{ℓ_{i}s_{j}} · z_{3}^{ℓ_{i}t_{j}}) .

Choose

η = \frac{(R − 1)b_{2} + (S − 1)b_{1}}{2} , ζ = \frac{(T − 1)b_{2} + (S − 1)b_{3}}{2}

and notice that, for 1 ≤ j ≤ N,

|r_{j}b_{2} + s_{j}b_{1} − η|^{k_{i}} ≤ (\frac{(R − 1)b_{2} + (S − 1)b_{1}}{2} )^{k_{i}} ,

|t_{j}b_{2} + s_{j}b_{3} − ζ|^{k_{i}} ≤ (\frac{(T − 1)b_{2} + (S − 1)b_{3}}{2} )^{m_{i}}

and that

∑_{i=0}^{N−1} k_{i} = ∑_{i=0}^{N−1} m_{i} = \frac{(K − 1)K}{2} KL = \frac{N}{2} (K − 1),

then Hadamard’s inequality implies

|P | ≤ N^{N/2} (\frac{(R − 1)b_{2} + (S − 1)b_{1}}{2} )^{\frac{(K−1)N}{2}} (\frac{(T − 1)b_{2} + (S − 1)b_{3}}{2} )^{\frac{(K−1)N}{2}}

× ( ∏_{i=0}^{K−1} k_{i}!)^{−1} ( ∏_{i=0}^{K−1} m_{i}!)^{−1} .

Recall that

b = (b_{2}η_{0})(b_{2}ζ_{0}) ( ∏_{k=1}^{K−1} k!)^{− \frac{4}{K(K−1)}} ,

where

η_{0} = \frac{R − 1}{2} + β_{1} \frac{S − 1}{2}, ζ_{0} = \frac{T − 1}{2} + β_{3} \frac{S − 1}{2}.

Thus we get,

|P | ≤ N^{N/2} b^{(K−1)N/2}.

Collecting all the above estimates, we find

log |Δ| ≥ − (D − 1) (log (N^{N/2}) + \frac{(K − 1)N}{2} log b)

− D ∑_{i=1}^{3}(V_{i} − U_{i})h(α_{i}) + ∑_{i=1}^{3} V_{i} log |α_{i}|.

The inequalities Dh(α_{i}) ≥ log |α_{i}| ≥ 0 imply

V_{i} log |α_{i}| − D(V_{i} − U_{i})h(α_{i}) ≥ (M_{i} + G_{i}) log |α_{i}| − 2DG_{i}h(α_{i})

and the result follows. □

12.4. Synthesis. Under the hypotheses of Proposition 12.5 and Proposition 12.6, we get

− \frac{D − 1}{2} N log N +∑_{i=1}^{3}(M_{i} +G_{i}) log |α_{i}|−2D ∑_{i=1}^{3} G_{i}h(α_{i})− \frac{D − 1}{2}(K −1) N log b

≤ ∑_{i=1}^{3} M_{i} log |α_{i}| + ρ ∑_{i=1}^{3} G_{i}| log α_{i}| + log(N!) + N log 2 + \frac{N}{2} (K − 1) log b

− (\frac{NKL}{4} + \frac{NKL}{4(2K − 1)} − \frac{NK}{3L} − \frac{N}{2} ) log ρ + 0.0001

Or, after some simplification,

− \frac{D − 1}{2} N log N ≤ ∑_{i=1}^{3} G_{i}(ρ| log α_{i}| − log |α_{i}| + 2Dh(α_{i})) + log(N!)

+N log 2+ \frac{K − 1}{2} DN log b−(\frac{NKL}{4} + \frac{NKL}{4(2K − 1)} − \frac{KN}{3L} − \frac{N}{2} ) log ρ+0.0001.

This result implies (divide by N/2 and use N! < N(N/e)^{N}, true for N > 7).

Proposition 12.7. With, the previous notation, if K ≥ 3, L ≥ 5, ρ ≥ e, and if Δ ≠ 0 then

Λ′ > ρ^{−KL}

provided that

(\frac{KL}{2} + \frac{L}{4} − 1 − \frac{2K}{3L} ) log ρ ≥ (D + 1) log N + gL(a_{1}R + a_{2}S + a_{3}T)
+ D(K − 1) log b − 2 log(e/2),

where the a_{i}’s satisfy

a_{i} ≥ ρ| log α_{i}| − log |α_{i}| + 2Dh(α_{i}), i = 1, 2, 3.

Remark. We notice that the statement of Proposition 12.7 is perfectly symmetric with respect to the b_{i}’s or the α_{i}’s, except for the choice of b. From now on we do not assume that b_{1} and b_{3} are positive, but we still suppose that b_{2} > 0 and that

b_{2}| log α_{2}| = |b_{1} log α_{1}| + |b_{3} log α_{3}| ± |Λ|.

12.5. Row rank. To conclude we need to find conditions under which one of our determinants Δ is non-zero, a so called zero lemma. We quote [3, Theorem 3] with some minor technical changes.

Proposition 12.8. Let K, L, R, R_{1}, R_{2}, S, S_{1}, S_{2}, T, T_{1}, T_{2} be rational integers all ≥ 3, with K ≥ 2L, R > R_{1} + R_{2}, S > S_{1} + S_{2}, T > T_{1} + T_{2} and T_{1} ≥ R_{1}. Let b_{1}, b_{2}, b_{3} and α_{1}, α_{2}, α_{3} as above and moreover assume that α_{1}, α_{2}, α_{3} are multiplicatively independent. If

(i)  4(R_{1} + 1)(S_{1} + 1) ≥ T_{1} + 1,
(i)  4(R_{1} + 1)(T_{1} + 1) ≥ S_{1} + 1,
(iii)  (R_{2} + 1)(S_{2} + 1)(T_{2} + 1) ≥ 12(K − 1)^{2}(L − 1),

and

(iv)  (R_{1} + 1)(S_{1} + 1)(T_{1} + 1) ≥ 8(2K + L − 2)^{2}

then either there exists a choice of Δ which is non-zero or at least one of the following conditions hold (C1)

∃r, s ∈ ℤ, rb_{2} = sb_{1} with 0 < r ≤ R_{i} and 0 < s ≤ S_{i} for some i = 1, 2,

(C2)

∃t, s ∈ ℤ, tb_{2} = sb_{3} with 0 < t ≤ T_{i} and 0 < s ≤ S_{i} for some i = 1, 2,

(C3): there exists r′, s′, t′, t′′ ∈ ℤ such that

s′t′b_{1} + r′t′′b_{2} + r′s′b_{3} = 0

which satisfy

0 < |r′| < min \{R_{1} + 1, (\frac{(R_{1} + 1)(S_{1} + 1)}{T_{1} + 1})^{1/2}\} ,

0 < |s′| < min \{S_{1} + 1, (\frac{(R_{1} + 1)(S_{1} + 1)}{T_{1} + 1})^{1/2}\}

and

0 < |t′| < min \{T_{1} + 1, (\frac{(S_{1} + 1)(T_{1} + 1)}{R_{1} + 1})^{1/2}\} ,

|t′′| < min \{T_{1} + 1, (\frac{(R_{1} + 1)(T_{1} + 1)}{S_{1} + 1})^{1/2}\} ,

which implies a non-trivial relation of the form

d_{1}b_{1} + d_{2}b_{2} + d_{3}b_{3} = 0 with |d_{1}| ≤ S_{1}, |d_{2}| ≤ R_{1}, |d_{3}| ≤ \frac{(R_{1} + 1)(S_{1} + 1)}{T_{1} + 1}.

12.6. A lower bound for the linear form. Now we have all the tools to conclude and we get at once the following result.

Theorem 12.9. We consider three non-zero algebraic numbers α_{1}, α_{2} and α_{3} which are multiplicatively independent and positive rational integers b_{1}, b_{2}, b_{3} with gcd(b_{1}, b_{2}, b_{3}) = 1, and the linear form

Λ = b_{2} log α_{2} − b_{1} log α_{1} − b_{3} log α_{3} ≠ 0.

Suppose that either α_{1}, α_{2} and α_{3} are real numbers > 1, and the logarithms of the α_{i}’s are real (and > 0), or α_{1}, α_{2} and α_{3} are complex numbers of modulus one, and the logarithms of the α_{i}’s are arbitrary determinations of the logarithm. Without loss of generality, we assume that

b_{2}| log α_{2}| = b_{1}| log α_{1}| + b_{3}| log α_{3}| ± |Λ|.

Let K, L, R, R_{1}, R_{2}, S, S_{1}, S_{2}, T, T_{1}, T_{2} be rational integers all ≥ 3, with K ≥ 2L, L ≥ 5, R > R_{1} + R_{2}, S > S_{1} + S_{2}, T > T_{1} + T_{2} and T_{1} ≥ R_{1}. Let ρ ≥ e be a real number. Assume first that

(o)  (\frac{KL}{2} + \frac{L}{4} − 1 − \frac{2K}{3L} ) log ρ ≥ (D + 1) log N + gL(a_{1}R + a_{2}S + a_{3}T)
+D(K − 1) log b − 2 log(e/2),

where N = K^{2}L, D = [ℚ(α_{1}, α_{2}, α_{3}) : ℚ] / [ℝ(α_{1}, α_{2}, α_{3}) : ℝ],

g = \frac{1}{4} − \frac{N}{12RST} , b = (b_{2}η_{0})(b_{2}ζ_{0}) ( ∏_{k=1}^{K−1} k!)^{− \frac{4}{K(K−1)}} ,

where

η_{0} = \frac{R − 1}{2} + \frac{b_{1}}{b_{2}} × \frac{S − 1}{2}, ζ_{0} = \frac{T − 1}{2} + \frac{b_{3}}{b_{2}} × \frac{S − 1}{2},

and

a_{i} ≥ ρ| log α_{i}| − log |α_{i}| + 2Dh(α_{i}), i = 1, 2, 3.

If

(i)  4(R_{1} + 1)(S_{1} + 1) ≥ T_{1} + 1,
(ii)  4(R_{1} + 1)(T_{1} + 1) ≥ S_{1} + 1,
(iii)  (R_{2} + 1)(S_{2} + 1)(T_{2} + 1) ≥ 12(K − 1)^{2}(L − 1),

and

(iv)  (R_{1} + 1)(S_{1} + 1)(T_{1} + 1) ≥ 8(2K + L − 2)^{2}

then either

Λ′ > ρ^{−KL}

where

Λ′ = |Λ| · max \{\frac{LRe^{LR|Λ|/(2b_{1})}}{2b_{1}} , \frac{LSe^{LS|Λ|/(2b_{2})}}{2b_{2}} , \frac{LT e^{LT |Λ|/(2b_{3})}}{2b_{3}} \}

or at least one of the conditions (C1), (C2), (C3) of Proposition 12.8 hold.

13. Proof of Theorem 1

We are now ready to complete the proof of Theorem 1. We argue by contradiction. Suppose that there is a perfect power in the Fibonacci sequence other than those listed in Theorem 1. By Propositions 6.1 and 11.1 there is a solution (n, y, p) to (17) with p > 2 × 10^{8}.

Recall that F_{n} = (ω^{n} − ω^{−n})/\sqrt{5}. Thus the linear form

Λ = n log ω − log \sqrt{5} − p log y

satisfies

log |Λ| < −2p log y + 1.

By Proposition 10.1

log y > 10^{20}

(and indeed much more). It seems very difficult to get good lower bounds for |Λ| when it is written in the previous form. We write

n = kp − q, where 0 ≤ q < p,

[notice that q is not necessarily a prime number, but we have some lack of letters!]. Then

Λ = p log(ω^{k}/y) − q log ω − log \sqrt{5}

and it is easy to see that it is now of the right form. We know that p > 2 × 10^{8} and we will obtain a contradiction by showing that p < 2×10^{8} using our Theorem 12.9.

The first step is to get an upper bound on p free of any condition. For this purpose our Theorem 12.9 is inconvenient to use: we have to deal with the conditions (C1), (C2) and (C3). This is the reason why we first apply Matveev’s estimate (Corollary 2.3): assume Λ ≠ 0, if real numbers A_{j} satisfy

A_{j} ≥ max{Dh(α_{j}), | log α_{j}|, 0.16}, 1 ≤ j ≤ 3,

and if

B = max{|b_{1}|, |b_{2}|, |b_{3}|}

then

log |Λ| > \frac{3e}{2}30^{6}3^{3.5}D^{2}A_{1}A_{2}A_{3} log(eD) log(eB),

where D = 2 and B = p in our case. This leads to

p < 2.4 × 10^{13}.

We can now apply Theorem 12.9 with

α_{1} = ω, α_{2} = ω^{k}/y, α_{3} = \sqrt{5}, D = 2

and

b_{1} = q, b_{2} = p, b_{3} = 1.

We can take

a_{1} = (ρ + 3) log \sqrt{5}, a_{2} = (ρ + 2p) log ω + 4 log y > 4 · 10^{20}, a_{3} = (ρ + 1) log ω,

where ρ > e. To apply the Theorem, we shall choose some rational integer

L ≥ 100

and put

K = ⌊mLa_{1}a_{2}a_{3}⌋, with 10 < m < 50,

and take

R_{1} = ⌊c_{1}L^{2/3}a_{2}a_{3}⌋, S_{1} = ⌊c_{1}L^{2/3}a_{1}a_{3}⌋, T_{1} = ⌊c_{1}L^{2/3}a_{1}a_{2}⌋,

with c_{1} = (32.001 m^{2})^{1/3}, and finally

R_{2} = ⌊c_{2}La_{2}a_{3}⌋, S_{2} = ⌊c_{2}La_{1}a_{3}⌋, T_{2} = ⌊c_{2}La_{1}a_{2}⌋, with c_{2} = (12 m^{2})^{1/3}.

We use the notation

R = R_{1} + R_{2} + 1, S = S_{1} + S_{2} + 1, T = T_{1} + T_{2} + 1.

With such a choice it is easy to check that the four conditions (i), (ii), (iii), (iv) hold. And we get either

log |Λ| > −KL log ρ − log(KL)

or at least one of the conditions (C1), (C2) and (C3) hold. First notice that, in our case (where b_{2} = p is prime)

((C1) or (C2)) ⇒ p ≤ max{S_{1}, S_{2}}.

Thus, if p > max{S_{1}, S_{2}} then (C1) and (C2) do not hold and then (C3) holds. If (C3) holds then recall that

s′t′b_{1} + r′t′′b_{2} + r′s′b_{3} = 0,

where the factors of the b_{i}’s are bounded above as in Proposition 12.8. In the previous relation we may assume that

gcd(s′, t′′) = gcd(r′, t′) = 1.

Moreover, since |s′| < p, we see that s′ and pt′′ are coprime, so that the above relation implies that s′ divides r′, say r′ = r′′s′. Then this relation is simplified into

t′b_{1} + r′′t′′b_{2} + r′′s′b_{3} = 0.

Then, since r′ and t′′ are coprime, gcd(r′′, t′) = 1 and r′′ divides b_{1}. In the present case, we get

t′q′ + t′′p + s′ = 0, with q = r′′q′,

where

|t′| ≤ 1 + (\frac{(S_{1} + 1)(T_{1} + 1)}{R_{1} + 1})^{1/2} < 1 + 1.0001 · (\frac{(S_{1} + 1)a_{1}}{a_{3}} )^{1/2}

and

0 < r′ < (\frac{(R_{1} + 1)(S_{1} + 1)}{T_{1} + 1})^{1/2} < 1.0001 · (\frac{(S_{1} + 1)a_{3}}{a_{1}} )^{1/2} .

Then we rewrite s′Λ as a linear form in two logarithms:

s′Λ = p log(α_{2}^{s′}α_{3}^{t′′}) − q′ log(ω^{r′}α_{3}^{−t′}),

where

ω = \frac{1 + \sqrt{5}}{2},  α_{2} = \frac{ω^{k}}{y} ,  α_{3} = \sqrt{5}.

This ends our preliminary discussion.

Now, after some computer search we see that we can apply Theorem 12.9 with the choices

L = 250, ρ = 11, m = 21.8432676837,

and then, in the first case, we get

p < 426 × 10^{6}.

With these choices, we have

max{S_{1}, S_{2}} = max{64049, 290961} < 10^{8}

so that neither condition (C1) nor condition (C2) hold. And, using the upper bounds obtained above thanks to Proposition 12.8, we get

|r′| ≤ 354, |t′| ≤ 182.

Moreover, the relation t′q′ + t′′p + s′ = 0, combined with 0 ≤ q < p, implies the inequality |t′′| ≤ |t′|, hence we also have

|t′′| ≤ 182.

Then we apply the main result (Théorème 1) of [27], with the choices (using the notation of this result)

L = 13, R_{1} = 1, S_{1} = 13, m = 0.138356081647, ρ = 22, …

and we get

n < 295 × 10^{6}.

Thus we have proved that p < 426 × 10^{6}. From this upper bound, if we use this process once more (taking now L = 180 and r = 11 in the first case, and keeping the same values L = 13 and ρ = 22 in the application of [27]), we get:

p < 197 × 10^{6},

which certainly shows that p < 2 × 10^{8} and we have obtained our contradiction. This completes the proof of Theorem 1.

References

[1] A. Baker and Wüsholz, Logarithmic forms and group varieties, J. reine angew. Math. 442 (1993), 19–62.

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

 version 2.1.1. (See also http://pari.math.u-bordeaux.fr/)

[3] C.D. Bennett, J. Blass, A.M.W. Glass, D.B. Meronk, R.P. Steiner, Linear forms in the logarithms of three positive rational numbers, J. Théor. Nombres Bordeaux 9 (1997), 97–136.

[4] M. A. Bennett, Rational approximation to algebraic number of small height: The Diophantine equation | ax^{n} − by^{n} |= 1, J. reine angew. Math. 535 (2001), 1–49.

[5] M. A. Bennett and C. M. Skinner, Ternary Diophantine equations via Galois representations and modular forms, Canad. J. Math. 56 (2004), 23–54.

[6] Yu. Bilu, G. Hanrot and P. M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers. With an appendix by M. Mignotte. J. reine angew. Math. 539 (2001), 75–122.

[7] 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/)

[8] C. Breuil, B. Conrad, F. Diamond, R. Taylor, On the modularity of elliptic curves over ℚ: wild 3-adic exercises, J. Amer. Math. Soc. 14 No.4 (2001), 843–939.

[9] Y. Bugeaud and K. Győry, Bounds for the solutions of unit equations, Acta Arith. 74 (1996), 67–80.

[10] Y. Bugeaud and K. Győry, Bounds for the solutions of Thue-Mahler equations and norm form equations, Acta. Arith. 74 (1996), 273–292.

[11] Y. Bugeaud and M. Mignotte, On integers with identical digits, Mathematika 46 (1999), 411–417.

[12] Y. Bugeaud, M. Mignotte, Y. Roy and T. N. Shorey, The equation (x^{n} − 1)/(x − 1) = y^{q} has no solutions with x square, Math. Proc. Cambridge Phil. Soc. 127 (1999), 353–372.

[13] Y. Bugeaud, M. Mignotte and S. Siksek, Classical and modular approaches to exponential Diophantine equations II. The Lebesgue–Nagell Equation, submitted for publication.

[14] J. H. E. Cohn, On square Fibonacci numbers, J. London Math. Soc. 39 (1964), 537–540.

[15] J. H. E. Cohn, Lucas and Fibonacci numbers and some Diophantine equations, Proc. Glasgow Math. Assoc. 7 (1965), 24–28.

[16] J. H. E. Cohn, Perfect Pell powers, Glasgow Math. J. 38 (1996), 19–20.

[17] J. E. Cremona, Algorithms for modular elliptic curves, 2nd edition, Cambridge University Press, 1996.

[18] H. Darmon and L. Merel, Winding quotients and some variants of Fermat’s Last Theorem J. reine angew. Math. 490 (1997), 81–100.

[19] G. Frey, Links between stable elliptic curves and certain Diophantine equations, Ann. Univ. Sarav. Ser. Math. 1 (1986), 1–40.

[20] G. Frey, Links between solutions of A − B = C and elliptic curves, in: Number Theory, Ulm 1987, Proceedings, Lecture Notes in Math. 1380, Springer-Verlag, New York, Berlin, Heidelberg, 1989, 31–62.

[21] E. Halberstadt and A. Kraus, Courbes de Fermat: résultats et problèmes, J. Reine Angew. Math. 548 (2002), 167–234.

[22] W. Ivorra, Sur les équations x^{p} + 2^{β}y^{p} = z^{2} et x^{p} + 2^{β}y^{p} = 2z^{2}, Acta Arith. 108.4 (2003), 327–338.

[23] A. Kraus, Sur l’équation a^{3} + b^{3} = c^{p}, Experimental Mathematics 7 (1998), No. 1, 1–13.

[24] A. Kraus and J. Oesterlé, Sur une question de B. Mazur, Math. Ann. 293 (1992), 259–275.

[25] E. Landau, Verallgemeinerung eines Pólyaschen Satzes auf algebraische Zahlkörper, Nachr. Kgl. Ges. Wiss. Göttingen, Math.-Phys. Kl. (1918), 478–488.

[26] M. Laurent, Linear form in two logarithms and the interpolation determinants, Acta Arith. 66 (1994), 181–199.

[27] M. Laurent, M. Mignotte and Y. Nesterenko, Formes linéares en deux logarithmes et déterminants d’interpolation, J. Number Theory 55 (1995), 255–265.

[28] H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. 26 (1992), 211-244.

[29] W. Ljunggren, Über die unbestimmte Gleichung Ax^{2} − By^{4} = C, Arch. f. Mat. og Naturvid. 41 (1938), No. 10, 18 pp.

[30] W. Ljunggren, On the diophantine equation x^{2} +4 = Ay^{2}, Det. Kgl. Norske Vid.-Selsk. Forh. 24 (1951), No. 18, 82–84.

[31] W. Ljunggren, On the diophantine equation Ax^{4} − By^{2} = C (C = 1, 4), Math. Scand. 21 (1967), 149–158.

[32] W. Ljunggren, Collected papers of Wilhelm Ljunggren. Vol. 1, 2. Edited by Paulo Ribenboim. Queen’s Papers in Pure and Applied Mathematics, 115. Queen’s University, Kingston, ON, 2003.

[33] H. London and R. Finkelstein, On Fibonacci and Lucas numbers which are perfect powers, Fibonacci Quart. 5 (1969), 476–481.

[34] J. McLaughlin, Small prime powers in the Fibonacci sequence, to appear.

[35] E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in logarithms of algebraic numbers. II, Izv. Ross. Akad. Nauk Ser. Mat. 64 (2000), 125–180. English transl. in Izv. Math. 64 (2000), 1217–1269.

[36] B. Mazur, Rational isogenies of prime degree, Invent. Math. 44 (1978), 129–162.

[37] M. Mignotte, Entiers algébriques dont les conjugués sont proches du cercle unité, Séminaire Delange–Pisot–Poitou, 19e année: 1977/78, Théorie des nombres, Fasc. 2, Exp. No. 39, 6 pp., Secrétariat Math., Paris, 1978.

[38] W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers, Springer-Verlag, Berlin, 1990.

[39] A. Pethő, Perfect powers in second order linear recurrences, J. Number Theory 15 (1982), no. 1, 5–13.

[40] A. Pethő, Full cubes in the Fibonacci sequence, Publ. Math. Debrecen 30 (1983), no. 1, 117–127.

[41] A. Pethő, Perfect powers in second order recurrences, in: Topics in Classical Number Theory, Proceedings of the Conference in Budapest 1981, Colloq. Math. Soc. János Bolyai 34, pp. 1217-1227, North–Holland, Amsterdam, 1984.

[42] A. Pethő, Diophantine properties of linear recursive sequences II, Acta Math. Paedagogicae Nyíregyháziensis 17 (2001), 81–96.

[43] K. Ribet, On modular representations of Gal(\overline{ℚ}/ℚ) arising from modular forms, Invent. Math. 100 (1990), 431–476.

[44] N. Robbins, On Fibonacci numbers which are powers. II. Fibonacci Quart. 21 (1983), no. 3, 215–218.

[45] T. N. Shorey and C. L. Stewart, On the Diophantine equation ax^{2t} + bx^{t}y + cy^{2} = d and pure powers in second order linear recurrences, Math. Scand. 52 (1983), 24–36.

[46] T. N. Shorey and R. Tijdeman, Exponential Diophantine equations, Cambridge Tracts in Mathematics 87, Cambridge University Press, Cambridge, 1986.

[47] C. L. Siegel, Abschätzung von Einheiten, Nachr. Akad. Wiss. Göttingen II, Math.-Phys. Kl., Nr. 9, (1969), 71–86.

[48] S. Siksek and J. E. Cremona, On the Diophantine equation x^{2} + 7 = y^{m}, Acta Arith. 109.2 (2003), 143–149.

[49] R.L. Taylor and A. Wiles, Ring theoretic properties of certain Hecke algebras, Annals of Math. 141 (1995), 553–572.

[50] P. M. Voutier, An effective lower bound for the height of algebraic numbers, Acta Arith. 74 (1996), 81–95.

[51] M. Waldschmidt, Minorations de combinaisons linéaires de logarithmes de nombres algébriques, Canadian J. Math. 45 (1993), 176-224.

[52] M. Waldschmidt, Diophantine approximation on linear algebraic groups, Springer, Berlin, [53] A. Wiles, Modular elliptic curves and Fermat’s Last Theorem, Annals of Math. 141 (1995), 443–551.

[54] O. Wyler, Solution to Problem 5080, Amer. Math. Monthly 71 (1964), 220–222.

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

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