PERFECT POWERS FROM PRODUCTS OF TERMS IN LUCAS SEQUENCES

YANN BUGEAUD, FLORIAN LUCA, MAURICE MIGNOTTE, SAMIR SIKSEK

Abstract. Suppose that {U_{n}}_{n≥0} is a Lucas sequence, and suppose that l_{1}, …, l_{t} are primes. We show that the equation

U_{n_{1}} ⋯ U_{n_{m}} = ±l_{1}^{x_{1}} ⋯ l_{t}^{x_{t}}y^{p}, p prime, m < p, has only finitely many solutions. Moreover, we explain a practical method of solving these equations. For example, if {F_{n}}_{n≥0} is the Fibonacci sequence, then we solve the equation

F_{n_{1}} ⋯ F_{n_{m}} = 2^{x_{1}} · 3^{x_{2}} · 5^{x_{3}} ⋯ 541^{x_{100}}y^{p}

under the restrictions: p is prime and m < p.

1. Introduction and Results

The problem of proving that 0, 1, 8, 144 are the only perfect powers in the Fibonacci sequence was a classical problem that attracted much attention during the past 40 years. It was finally solved [8] in 2003 using a combination of tools from Wiles’ proof of Fermat’s Last Theorem and Baker’s theory of linear forms in logarithms. In [3] it is explained that the method used in [8] can be applied to a wide range of Lucas sequences (defined below).

The last 40 years have also seen many ad hoc techniques applied to the problem of determining perfect powers in Lucas sequences, as well as several theoretical finiteness results. In this paper, we systematise, generalise and extend the many tricks and theorems appearing in the literature into a coherent theory. One novelty of this paper is that we deal systematically with the problem of determining the perfect powers arising as products of finitely many terms in a Lucas sequence. We prove a finiteness-type result (the Finiteness Theorem); moreover, we show that this problem—roughly speaking—reduces to the problem of determining the perfect powers in the Lucas sequence (the Reduction Theorem), which as we indicated above can be solved by the method of [8]. As an illustration, writing {F_{n}}_{n≥0} for the Fibonacci sequence, we show that the only solutions of the equation F_{m}F_{n} = y^{p} in integers 2 ≤ m < n and p ≥ 2 are given by F_{2}F_{6} = 8, F_{3}F_{6} = 16 and F_{2}F_{12} = 144. This extends a result of Cohn [10], who solved this equation for the case p = 2.

We now state our results precisely. Let r, s be non-zero integers with Δ = r^{2} + 4s ≠ 0. Let α, β be the roots of the equation x^{2} − rx − s = 0 with the convention that |α| ≥ |β|. We define the Lucas sequence {U_{n}}_{n≥0} with parameters r, s to be the sequence

Date: July 10, 2006.

Y. Bugeaud is supported by the Austrian Science Fundation FWF, grant M822-N12. S. Siksek is supported by a grant from the UK Engineering and Physical Sciences Research Council.

U_{n} = \frac{α^{n} − β^{n}}{α − β} .

This is also the sequence given by U_{0} = 0, U_{1} = 1 and U_{n+2} = rU_{n+1} + sU_{n} for all n ≥ 0. We say that the sequence {U_{n}}_{n≥0} is non-degenerate if α/β is not a root of unity. Throughout we suppose, often implicitly, that the Lucas sequence under consideration is non-degenerate. The case r = s = 1 corresponds to the Fibonacci sequence {F_{n}}_{n≥0}.

In what follows, we repeatedly use the following notation. If T = {l_{1}, …, l_{t}} is a finite set of primes, we write \overline{T} for the set of integers of the form

±l_{1}^{x_{1}}l_{2}^{x_{2}} ⋯ l_{t}^{x_{t}}, x_{i} ≥ 0.

Theorem 1. (The Finiteness Theorem) Suppose that {U_{n}}_{n≥0} is a non-degenerate Lucas sequence, and that T is a finite set of primes. There exists an effectively computable constant c depending only on the sequence {U_{n}}_{n≥0} and the set T such that if

(1)  ∏_{i=1}^{m} U_{n_{i}} = μy^{p},  μ ∈ \overline{T} , m, n_{i}, y ∈ ℤ^{+}, p prime, m < p,

then n_{i} < c for i = 1, …, m.

Our Finiteness Theorem does give an algorithm for solving equation (1), but it is by no means a practical one, since the computable constant c mentioned in the theorem is astronomical. We do however explain a method that should work in practice. Our method is based on the following result, which is also used in the proof of the Finiteness Theorem.

Theorem 2. (The Reduction Theorem) Suppose that {U_{n}}_{n≥0} is a non-degenerate Lucas sequence, and T is a finite set of primes. Suppose n_{1}, …, n_{m} satisfy (1), and let q be the greatest prime divisor of n_{1} ⋯ n_{m}. Then, there exists a computable positive integer A, and a finite computable set 𝔔, both depending only on the sequence {U_{n}}_{n≥0} and the set T, such that either q ∈ 𝔔 or

(2)  U_{q} = ±A^{(q−1)/2}z^{p}

for some z ∈ ℤ^{+}.

Later on we give a precise and practical recipe for writing down the integer A and set 𝔔 appearing in the statement of the Reduction Theorem. Thus, applying the method of [8] and [3] to equation (2), we should be able to obtain an upper bound for the prime divisors of n_{1} … n_{m} in equation (1). Once this is done, we explain a completely practical algorithm for solving (1): we call this the Distillation Algorithm. In essence the Reduction Theorem reduces (1) to (2); when r and s are coprime it turns out that A = 1 and so we reduce to the equation

U_{q} = z^{p}.

When applied to the Fibonacci sequence, our Distillation Algorithm gives the following results.

Theorem 3. Let {F_{n}}_{n≥0} be the Fibonacci sequence. If

(3)  ∏_{i=1}^{m} F_{n_{i}} = y^{p},  n_{i}, m, y ∈ ℤ^{+}, p prime, m < p,

then the indices n_{i} belong to the set {1, 2, 3, 4, 6, 12}. Moreover, the solutions to the equation F_{m}F_{n} = y^{p} with 1 ≤ m ≤ n and p ≥ 2 are given by

• m = n,

• m, n = 1, 2,

• n = 6, m = 1, 2, 3,

• n = 12, m = 1, 2.

In fact, if we maintain the assumption m < p, then we can be far more ambitious as the following theorem shows.

Theorem 4. Let {F_{n}}_{n≥0} be the Fibonacci sequence. Let T be the set of primes l satisfying 2 ≤ l < 541; this is the set of the first hundred primes. If

(4)  ∏_{i=1}^{m} F_{n_{i}} = μy^{p},  μ ∈ \overline{T} , n_{i}, m, y ∈ ℤ^{+}, p prime, m < p,

then the indices n_{i} belong to the set

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19,

20, 21, 22, 24, 26, 27, 28, 30, 36, 42, 44} .

Our last application is to unidigital numbers: we call a positive integer unidigital if all the digits of its base 10 representation are the same.

Theorem 5. Let U_{n} = (10^{n} − 1)/(10 − 1). The only pairs of unidigital numbers whose products are perfect powers are as follows:

• d U_{n} × d U_{n} where n ≥ 1 and d = 1, 2, …, 9, or

• U_{n} × 4 U_{n} where n ≥ 1, or

• U_{n} × 9 U_{n} where n ≥ 1, or

• 1 × 8 or 2 × 4 or 3 × 9 or 4 × 8.

The present paper is organised as follows. In Section 2, we outline the links between the current paper and other papers appearing in the literature. Sections 3 and 5 are devoted to some preliminary results about Lucas sequences that are needed in the proofs of the Theorems. The Reduction Theorem is proved in three stages: A weak version is proved in Section 4, an intermediate version in Section 6, and a full-strength version in Section 7. In particular, the version of the Reduction Theorem in Section 7 gives completely explicit recipes for the set 𝔔 and the integer A appearing in the statement of the theorem. The Finiteness Theorem is established in Section 8. The Distillation Algorithm, which concerns the practical resolution of equation (1) once equation (2) had been solved, is discussed in Section 9. The proofs of Theorems 3, 4 and 5 are given in Sections 10 and 11. Finally, the last section is devoted to a few concluding remarks. In particular, in the last section, we present a conjecture which if proven would allow us to remove the restriction m < p in the above theorems.

We are grateful to Professor Paulo Ribenboim for suggesting to us to study the equation F_{n}F_{m} = y^{p} which was the starting point of this work. We are also grateful to Mihai Cipu and the referee who suggested corrections to previous versions.

2. Links to Previous Works

In this section, we explain the link between this paper and previous works on Lucas sequences.

The Reduction Theorem is present behind the scenes in many papers concerning Lucas sequences. In a few of these papers, some explicit, though weak, version of the Reduction Theorem appears.

For example, Pethő [15] and Robbins [23], independently, established that if p is prime, p ≥ 3 and F_{n} = y^{p} for some integer y, then either n = 0, 1, 2, 6, or there exists a prime q | n such that F_{q} = y_{1}^{p} for some integer y_{1}. Clearly, this result can be regarded as a weak version of the Reduction Theorem for the Fibonacci sequence.

In [11] Inkeri solved the equation a\frac{x^{n}−1}{x−1} = y^{p} for 1 < a < x ≤ 10. This was extended by Bugeaud [2] to 1 ≤ a < x ≤ 100. Lemma 1 of Bugeaud’s paper is again a weak version of the Reduction Theorem for the Lucas sequence \frac{x^{n}−1}{x−1}. That paper also features an argument similar in spirit to our Distillation Algorithm, and relies on the fact that the equation \frac{x^{n}−1}{x−1} = y^{p} was solved previously by Bugeaud and Mignotte [5] for x = z^{t} with 2 ≤ z ≤ 10^{4} and t ≥ 1. The results of [2] can now be easily deduced using our Reduction Theorem and Distillation Algorithm.

In [19, 20], Ribenboim gave an algorithm for determining terms of the form Cx^{h} in Lucas sequences, under various restrictions: for example, for h ≥ 3 he supposes that the discriminant Δ is positive, and the integers r, s appearing in the definition of the Lucas sequence are coprime. The algorithm is similar in spirit to ours but no version of the Reduction Theorem is made explicit. Even under these restrictions it is somewhat weaker than our algorithm. For example, if we want to solve the equation F_{n} = q^{m}y^{p} for some prime q with the algorithm in [20], we must know the solutions to F_{n} = 2^{k}y^{p}. By contrast, our Reduction Theorem and Distillation Algorithm only demand knowledge of the solutions of F_{n} = y^{p}.

In many other papers one finds tortuous arguments that would have been circumvented using the Reduction Theorem and the Distillation Algorithm. To save other authors the embarrassment, we mention only one example of this which involves some of the authors of this paper. In [7], the equation F_{n} = 2^{k}y^{p} is solved using the previous result on F_{n} = y^{p}. The ad hoc (one page) argument can now be replaced with a trivial (one line) calculation. The reader is invited to perform this calculation after reading this paper.

The equation U_{n}U_{m} = y^{2} was studied—in various degrees of generality—by several authors: for example by Cohn in [10], by Ribenboim in [16, 17, 18], and by Ribenboim and McDaniel [21, 22]. Notice that this equation is not covered by our Theorems 1, 2, which however do cover the equation U_{n}U_{m} = y^{p} for a prime p ≥ 3. Thus, our results nicely complement those of Cohn, Ribenboim and McDaniel.

Very recently, Luca and Shorey [12] considered the equation

U_{n}U_{n+d} ⋯ U_{n+(k−1)d} = y^{p}, gcd(n, d) = 1,

which they showed has finitely many solutions. They also established that the product of consecutive Fibonacci numbers is never a positive perfect power except for the trivial case F_{1}F_{2} = 1.

Moreover, independently, Pethő [14] and Shorey and Stewart [24] established that every binary recurrence sequence contains at most finitely many perfect powers. This is more general than our Finiteness Theorem for m = 1. However, we find in the literature no result comparable with our Finiteness Theorem for m > 1.

3. Preliminaries I

We keep the notation from the Introduction. Throughout, we denote by S the set of prime factors of 2Δ, by S_{1} the set of prime factors of gcd(r, s), and by S_{2} the set of prime factors of Δ not belonging to S_{1}. We write K = ℚ(α) = ℚ(β); this is either ℚ or a quadratic extension of it. We write O for the ring of integers of K.

Notation. If k | n are positive integers, we write

U_{n,k} = \frac{U_{n}}{U_{k}} .

Clearly, U_{n,k} is a rational integer.

Lemma 1. If m, n are positive integers, and k = gcd(m, n), then

gcd(U_{m}, U_{n}) = A U_{k},

where A ∈ \overline{S_{1}}.

Proof. It is clear that U_{k} divides both U_{m} and U_{n}. Hence, A = gcd(U_{m}, U_{n})/U_{k} is an integer. It remains to check that A is in \overline{S_{1}}.

We work with polynomials in a variable X. Using induction on max{m, n} as well as the formula

(X^{m} − 1) − X^{m−n}(X^{n} − 1) = X^{m−n} − 1 whenever m > n,

one proves the existence of polynomials u(X) and v(X) in ℤ[X] such that (^{1})

u(X)(X^{m} − 1) + v(X)(X^{n} − 1) = X^{k} − 1.

Homogenising the above relation, it follows that there exists an integer t ≥ 1 and homogeneous polynomials u(X, Y) and v(X, Y) with integer coefficients such that

(5)  u(X, Y) (X^{m} − Y^{m}) + v(X, Y) (X^{n} − Y^{n}) = Y^{t} (X^{k} − Y^{k}) .

Specialising relation (5) in (X, Y) = (α, β), we get the relation

u(α, β) U_{m,k} + v(α, β) U_{n,k} = β^{t}, where u(α, β), v(α, β) ∈ O.

Assume now that q is a prime dividing A. Let 𝔮 be a prime ideal of O dividing q. Then 𝔮 divides both U_{n,k} and U_{m,k} and by the above relation 𝔮 | β^{t}. Since 𝔮 is prime, we get that 𝔮 | β. Since α and β can be interchanged, we get that 𝔮 divides α as well, therefore it also divides r = α+β and s = αβ, which completes the proof of the lemma. □

Lemma 2. Suppose that n = kq where n, k and q are positive integers. Then gcd(U_{k}, U_{n,k}) divides qϵ for some ϵ ∈ \overline{S}.

1One knows from cyclotomy that X^{k} − 1 is the greatest common divisor of X^{m} − 1 and X^{n} − 1. Thus the existence of u(X), v(X) ∈ ℚ[X] satisfying the given relation follows from Euclid’s Algorithm. Here we need a stronger result, namely that we can take u(X), v(X) ∈ ℤ[X].

Proof. We note that

U_{k} = \frac{α^{k} − β^{k}}{α − β} ,

and

U_{n,k} = α^{k(q−1)} + α^{k(q−2)}β^{k} + ⋯ + β^{k(q−1)}.

Let g = gcd(U_{k}, U_{n,k}). Since g | U_{k}, we see that

α^{k} ≡ β^{k} (mod gO).

But g | U_{n,k}, so

0 ≡ α^{k(q−1)} + α^{k(q−2)}β^{k} + ⋯ + β^{k(q−1)} ≡ qα^{k(q−1)} (mod gO).

Thus, gO divides the ideal qα^{k(q−1)}O and similarly the ideal qβ^{k(q−1)}O. The Lemma follows since the greatest common divisor of the ideals αO and βO divides Δ. □

Lemma 3. Suppose that k ≥ 1 is an integer and q ∉ S is prime. If q | U_{k}, then gcd(k, q^{2} − 1) > 1.

Proof. We may suppose that k > 1. Let 𝔮 be a prime ideal of O dividing q. Then

α^{k} ≡ β^{k} (mod 𝔮).

We see that if 𝔮 divides either α or β, then it divides both, and hence q | Δ, which contradicts our assumption that q ∉ S. We deduce that 𝔮 divides neither α, nor β. Moreover, again since q ∤ Δ, we see that α − β is not divisible by 𝔮. We deduce that

\frac{α}{β} ≢ 1, (\frac{α}{β})^{k} ≡ 1,

in the finite field O/𝔮. However, the group (O/𝔮)^{∗} has order either q − 1 or q^{2} − 1. Thus,

gcd(k, q^{2} − 1) > 1.
□

Lemma 4. Suppose that k is odd and q ∉ S is prime. Suppose that for every prime l | k, we have l ≥ q. Then q ∤ U_{k}.

Proof. Suppose that k is odd, q ∉ S and q | U_{k}. By Lemma 3,

gcd(k, q^{2} − 1) > 1.

Since k is odd, there is some odd prime l satisfying l | k and l | (q^{2} − 1). But all odd prime divisors of q^{2} − 1 are strictly smaller than q. The Lemma follows. □

Lemma 5. Suppose that n is an integer and let q be its smallest prime factor. Write n = kq. Then gcd(U_{k}, U_{n,k}) ∈ \overline{S}.

Proof. By Lemma 2, gcd(U_{k}, U_{n,k}) divides qϵ, where ϵ ∈ \overline{S}. If n is even, then q = 2 is in S and there is nothing more to prove. Likewise, there is nothing more to prove if q ∈ S.

Thus, suppose that n is odd and that q ∉ S. Now Lemma 4 immediately gives q ∤ U_{k}, and this completes the proof. □

Lemma 6. Let n > 1 be an integer and let q be its greatest prime factor. Then

gcd(U_{q}, U_{n,q}) ∈ \overline{S}.

Proof. Write n = q_{1}q_{2} ⋯ q_{t} with q_{1} ≤ q_{2} ≤ … ≤ q_{t} = q, all prime. Let k_{i} = q_{t}q_{t−1} ⋯ q_{i}. We use induction to show, for i = 2, …, t, that

(6)  gcd(U_{k_{i}}, U_{n,k_{i}}) ∈ \overline{S}.

The lemma follows at once from this by observing that k_{t} = q.

For i = 2, we have n = k_{2}q_{1} and q_{1} is the smallest prime factor of n. Thus, the case i = 2 follows from Lemma 5.

Now suppose 2 ≤ i < t and that (6) holds. Observe that U_{k_{i+1}} | U_{k_{i}}, so we get

gcd(U_{k_{i+1}}, U_{n,k_{i}}) ∈ \overline{S}.

Moreover, q_{i} is the smallest prime factor of k_{i}, and k_{i} = k_{i+1}q_{i}. Hence, by Lemma 5, we have

gcd(U_{k_{i+1}}, U_{k_{i},k_{i+1}}) ∈ \overline{S}.

From the last two inclusions and the fact that

U_{n,k_{i+1}} = U_{n,k_{i}}U_{k_{i},k_{i+1}},

we deduce that

gcd(U_{k_{i+1}}, U_{n,k_{i+1}}) ∈ \overline{S}.

This completes the proof. □

4. A Weak Version of the Reduction Theorem

We now prove the following weak version of the Reduction Theorem.

Lemma 7. Suppose that {U_{n}}_{n≥0} is a non-degenerate Lucas sequence and T is a finite set of primes. Suppose n_{1}, …, n_{m} satisfy (1). Let q be the greatest prime divisor of n_{1} ⋯ n_{m}. Then

(7)  U_{q} = ηz^{p}

for some η ∈ \overline{S ∪ T} and z ∈ ℤ^{+}.

Proof. Suppose that n_{1}, …, n_{m} satisfy (1). Let q be the greatest prime divisor of n_{1} ⋯ n_{m}. Reorder the indices so that q divides n_{1}, …, n_{m′} and q does not divide the others. By Lemma 6, we can, for i = 1, …, m′, write

U_{n_{i}} = U_{q}U_{n_{i},q}

with gcd(U_{q}, U_{n_{i},q}) ∈ \overline{S}. Moreover, for i > m′, Lemma 1 gives gcd(U_{q}, U_{n_{i}}) ∈ \overline{S}. It follows from (1) that there exists an integer G with

U_{q}^{m′}G = μy^{p},

where the greatest common divisor of U_{q} and G is in \overline{S}. Hence,

U_{q}^{m′} = η′z′^{p}

for some η′ ∈ \overline{S ∪ T} and z′ ∈ ℤ^{+}. Now recall the assumption m < p made in (1). Thus, m′ ≤ m < p. So,

U_{q} = ηz^{p},

where η ∈ \overline{S ∪ T} and z ∈ ℤ^{+}. This completes the proof of the Lemma. □

5. Preliminaries II

Let S_{1} and S_{2} be as in Section 3; namely S_{1} is set of primes dividing gcd(r, s), and S_{2} is the set of primes dividing Δ but not gcd(r, s).

Lemma 8. Suppose that l ∉ S_{1} is a prime.

(i) If l | s then l ∤ U_{n} for all n ≥ 1.

(ii) If l ∈ S_{2} then l | U_{n} if and only if l | n.

Proof. For (i), suppose l | s. Then l ∤ r. It is straightforward to show that U_{n} ≡ r^{n−1} (mod l) and so (i) follows.

For (ii), suppose l ∈ S_{2}. Let ℚ_{l} be the l-adic completion of ℚ and K_{π} be a completion of K with π | l. Write O_{π} for the π-adic integers. Since l ∈ S_{2}, we see that π ∤ αβ but π^{t} || (α − β) for some t ≥ 1. Hence,

\frac{α}{β} = 1 + ωπ^{t}

for some ω ∈ O_{π} with π ∤ ω. Then

(\frac{α}{β})^{n} ≡ 1 + nωπ^{t} (mod π^{2t}),

which shows that

α^{n} − β^{n} ≡ nωβ^{n}π^{t} (mod π^{2t}).

It follows that

U_{n} ≡ nβ^{n−1} (mod π^{t}),

which proves (ii). □

Lemma 9. Suppose that l ∤ sΔ is a prime. Then there exists an integer m_{l} > 1 such that l^{t} || U_{m_{l}} for some t ≥ 1 and l ∤ U_{m} for all 1 ≤ m < m_{l}. Moreover, for n ≥ 1

(i) if l | U_{n}, then m_{l} | n;

(ii) l^{t} || U_{n} if and only if m_{l} | n and l ∤ n; (iii) l^{t+1} | U_{n} if and only if l m_{l} | n.

Remark. The integer m_{l} defined above is called the rank of first appearance of the prime l for the Lucas sequence {U_{n}} (see [20]).

Proof. Suppose that l ∤ sΔ and let ℚ_{l}, K_{π} and O_{π} be as in the proof of Lemma 8. Then π ∤ αβ(α − β) and

α^{l^{2}−1} ≡ β^{l^{2}−1} ≡ 1 (mod π).

It follows that l | U_{l^{2}−1}. Thus, there is certainly an m > 1 such that l | U_{m}, and we let m_{l} be the least such m, and t ≥ 1 be such that l^{t} || U_{m_{l}}.

For (i), suppose that n > 1 and l | U_{n}. By assumption, l ∤ s and so l ∉ S_{1}; it follows from Lemma 1 that l | U_{m} where m = gcd(n, m_{l}). From the minimality of m_{l}, we deduce that m = m_{l} and so m_{l} | n as desired.

Let us now prove (ii) and (iii). Note that

(\frac{α}{β})^{m_{l}} = 1 + ωπ^{t}

for some ω ∈ O_{π} and π ∤ ω. Suppose now that n = km_{l}. Then

(\frac{α}{β})^{n} ≡ 1 + kωπ^{t} (mod π^{2t}).

The lemma follows immediately. □

Finally, for the proof of Theorem 1 we will need the following theorem, which is a restatement of Theorem 9.6 from [25].

Theorem 6. Suppose that {U_{n}}_{n≥0} is a non-degenerate Lucas sequence, and T is a finite set of primes. There is an effectively computable constant c depending only on the sequence {U_{n}}_{n≥0} and the set T such that if

U_{n} = μy^{p}, μ ∈ \overline{T} , n, y ∈ ℤ^{+}, p ≥ 2,

then n < c.

6. An Intermediate Version of the Reduction Theorem

In Section 4 we proved a weak version of the Reduction Theorem. We now prove a stronger version of that result—though one which is still weaker than the Reduction Theorem itself. Later on we will deduce the Reduction Theorem from the version we prove here.

We introduce another Lucas sequence {U′_{n}} associated to {U_{n}} whose arithmetic is somewhat simpler. For l ∈ S_{1} let

(8)  ξ_{l} = min (ord_{l}(r), ⌊\frac{ord_{l}(s)}{2}⌋) ,

and

(9)  g = ∏_{l∈S_{1}} l^{ξ_{l}},  r′ = \frac{r}{g} ,  s′ = \frac{s}{g^{2}} .

Clearly r′ and s′ are integers. We let {U′_{n}}_{n≥0} be the Lucas sequence with parameters r′ and s′. It is easy to see that

(10)  U_{n} = g^{n−1}U′_{n}

for positive integers n. We define Δ′, S′, S′_{1}, S′_{2} for sequence {U′_{n}} in exactly the same way as we defined the corresponding quantities for {U_{n}}. If l is prime, we write m′_{l} for the rank of first appearance of the prime l for the Lucas sequence {U′_{n}}.

Now we introduce some terminology and notation that will be helpful in this section and the rest of the paper. Suppose H is a finite set of primes and B is a non-zero integer. We say that B is a perfect power up to H if B = ηx^{p} for some η ∈ \overline{H}, positive integer x and prime p.

As for the notation, we define

𝔔′ = S′_{2} ∪ {m′_{l} : l ∈ S ∪ T, l ∤ s′Δ′ and m′_{l} is prime} ,

and

(11)  𝔔 = {q ∈ 𝔔′ ∪ {2} : U_{q} is a perfect power up to S ∪ T } .

Lemma 10. Let 𝔔 be as above. Suppose that the n_{i} satisfy (1), and let q be the largest prime divisor of n_{1} ⋯ n_{m}. Then either q ∈ 𝔔 or q is odd and

(12)  U′_{q} = ϵz^{p}

for some ϵ ∈ \overline{S′_{1}} and z ∈ ℤ^{+}.

Proof. From the weak version of the Reduction Theorem (Lemma 7), we know that q satisfies (7) for some η ∈ \overline{S ∪ T} and z ∈ ℤ^{+}. If q = 2 then we see that q ∈ 𝔔 and we are finished. Suppose from now on that q is odd.

From the relation (10) and the fact that g ∈ \overline{S_{1}} ⊂ \overline{S ∪ T} we see that U′_{q} satisfies (12) for some ϵ ∈ \overline{S ∪ T} and z ∈ ℤ^{+}. To prove the lemma, it is clearly sufficient to show that if ϵ ∉ \overline{S′_{1}} then q ∈ 𝔔, or equivalently here that q ∈ 𝔔′.

Suppose that ϵ ∉ \overline{S′_{1}}. Then ϵ is divisible by some prime l ∈ S ∪ T such that l ∉ S′_{1}. But ϵ | U′_{q} and so l | U′_{q}. We now utilise Lemma 8 with the sequence {U′_{n}} instead of {U_{n}}. First we see that l ∤ s′. If l ∈ S′_{2} then l | q and so q = l ∈ S′_{2} ⊆ 𝔔′ and we are finished.

From now on, we may suppose that l ∤ s′ and l ∉ S′_{1} ∪ S′_{2}; in other words l ∤ s′Δ′. Now part (i) of Lemma 9 gives that m′_{l} | q. But q is prime, and so m′_{l} = q. Hence, q ∈ 𝔔′ as required. □

7. Proof of the Reduction Theorem

In this section we finally prove the Reduction Theorem in its full strength. We continue with the notation of the previous section; in particular ξ_{l} is given by (8). For l ∈ S_{1} we define

ζ_{l} = \begin{cases}2ξ_{l} + 1 & if l ∈ S′_{1}, \\ 2ξ_{l} & if l ∉ S′_{1}. \end{cases}

Let

A = ∏_{l∈S_{1}} l^{ζ_{l}}.

We are now ready to state and prove the following totally explicit version of the Reduction Theorem.

Lemma 11. Let 𝔔 be as in (11) and A be as above. Suppose that the n_{i} satisfy (1), and let q be the largest prime divisor of n_{1} ⋯ n_{m}. Then either q ∈ 𝔔 or q is odd and

(13)  U_{q} = ±A^{(q−1)/2}z^{p}

for some z ∈ ℤ^{+}.

Proof. Suppose that q ∉ 𝔔. Lemma 10 tells us that q is odd and U′_{q} = ϵz^{p} for some ϵ ∈ \overline{S′_{1}} and z ∈ ℤ^{+}. Moreover, we know that U_{q} = g^{q−1}U′_{q} with g given by (9). To prove the Lemma it is sufficient to show, for l ∈ S_{1} that

ord_{l}(U′_{q}) = \begin{cases}(q − 1)/2, & if l ∈ S′_{1}. \\ 0, & if l ∉ S′_{1}. \end{cases}

Suppose first that l ∈ S′_{1}; in other words l | r′ and l | s′. Pondering the definitions (8) and (9) we convince ourselves that l || s′. A straightforward induction enables us to deduce that

ord_{l}(U′_{n}) = \frac{n − 1}{2} if n is odd, ord_{l}(U′_{n}) ≥ \frac{n}{2} if n is even.

This establishes the result we want if l ∈ S′_{1}.

Suppose finally that l ∉ S′_{1}. We would like to show that ord_{l}(U′_{q}) = 0; to this end we suppose that l | U′_{q} and deduce a contradiction. Now from l ∉ S′ and l ∈ S_{1} ⊂ S ⊂ S ∪ T it is easy to deduce, as in the proof of Lemma 10, that q ∈ 𝔔. This gives the desired contradiction and completes the proof. □

8. Proof of the Finiteness Theorem

We now come to prove the Finiteness Theorem. Suppose that n_{i} satisfy (1). Using the Reduction Theorem and Theorem 6, we see that there exists a finite computable set R containing all of the prime divisors q of n_{1}, …, n_{m}. Now the Finiteness Theorem follows immediately from Theorem 6 and the following lemma.

Lemma 12. Let R be a set of primes containing all the prime divisors of n_{1},…, n_{m}. If k ≥ 1 divides at least one of the n_{i}, then

U_{k} = ζw^{p}

for some ζ ∈ \overline{R ∪ S ∪ T} and w ∈ ℤ^{+}. In other words, U_{k} is a perfect power up to R ∪ S ∪ T.

Proof. We prove the lemma by contradiction. Suppose that k > 1 is the smallest positive integer dividing one of the n_{i}’s for which the lemma fails. Thus, there is some prime l ∉ R ∪ S ∪ T such that l^{t} || U_{k} and p ∤ t.

As l ∉ S, we see that l ∤ Δ. From Lemma 8, we know that l ∤ s. Now part (i) of Lemma 9 tells us that m_{l} | k. Moreover, l ∤ k since l ∉ R and all the prime divisors of k (which are among the prime divisors of some n_{i}) belong to R. Now parts (ii) and (iii) of Lemma 9 give l^{t} || U_{m_{l}}.

There are two possibilities. The first is that m_{l} < k. By the minimality of k, we see that p | t giving a contradiction.

The second possibility is that m_{l} = k. Rearrange the n_{i} so that m_{l} divides n_{1}, …, n_{m′} and does not divide the others. By Lemma 9 again, l^{t} || U_{n_{i}} for i = 1, …, m′, and l ∤ U_{n_{i}} for i > m′. From equation (1), we see that p | tm′, where we know that 1 ≤ m′ ≤ m < p. Hence p | t, again giving a contradiction. □

9. The Distillation Algorithm

In this section, we study the practical resolution of equation (1). The first step is to solve the equation

(14)  U_{q} = ±A^{(q−1)/2}z^{p},  p prime, q odd prime, z ∈ ℤ^{+}.

Until recently, solving such an equation has been a formidable task in most cases, but is now relatively practical (see [3] as well as [8], [9] and the remarks in Section 12). The method of [3] combines the classical approach via estimates for linear forms in two or three logarithms (to bound the exponent p), with the modular approach via Frey curves and Ribet’s level-lowering theorem. This method is not an algorithm in the strict sense of the word, but is a practical and reliable strategy that should solve this equation.

We suppose equation (14) has been solved. We now explain an algorithm— which we call the Distillation Algorithm—that enables us to write down a finite set containing all the possibilities for the indices n_{i} appearing in equation (1). For readability we will not write up the algorithm in a very formal way.

Step 1: Let

Q = {q : q is a solution to (14)} ∪ 𝔔,

where 𝔔 is as in Section 6. By Lemma 11, the greatest prime divisor of n_{1} ⋯ n_{m} belongs to Q. Let q^{∗} = max(Q) and

R = {q : q is prime and q ≤ q^{∗}} .

Thus, all the prime divisors of n_{1}, …, n_{m} belong to R.

Step 2: Our second step is to refine R using Lemma 12; our objective is to replace R by a subset that still contains all the possible prime divisors of the n_{i}. We loop through the primes q ∈ R and eliminate all those such that U_{q} is not a perfect power up to R ∪ S ∪ T. We repeat this until we have looped through all of the elements of R without eliminating a single element. Now write

R = {q_{1}, …, q_{t}} .

Step 3: Our third step is to determine, for each q_{j} ∈ R, an upper bound for the power of q_{j} dividing the n_{i}. Fix q in R and let a ≥ 1 be the smallest value such that U_{q^{a}} is not a power up to R ∪ S ∪ T. By Lemma 12, we know that q^{a} does not divide any of the n_{i}. Write a_{j} for the a that corresponds to q_{j}, and let b_{j} = a_{j} − 1. Thus, the exponents of q_{j} in the factorisations of the n_{i} are at most b_{j}.

Step 4: We now let N be the set of integers n such that

• n is of the form ∏ q_{j}^{x_{j}} with 0 ≤ x_{j} ≤ b_{j}.

• U_{k} is a perfect power up to R ∪ S ∪ T for all positive divisors k of n. It follows from the above and Lemma 12 again that the n_{i} belong to this finite set N.

Step 5: We refine N in a way that it will still contain all of the possible n_{i}. We loop through n ∈ N. Suppose there is some prime l ∈ R ∪ S\T such that l || U_{n}, but l ∤ U_{n′} for all n′ ≠ n in N. We deduce from (1) that n_{i} ≠ n for all i (here we need again the hypothesis m < p), and so n can be eliminated from the set of possible indices N. We repeat this until we have looped through all of the elements of N once without eliminating any elements.

The set N produced by Step 5 is algorithm’s output.

10. Powers from Products of Unidigital Numbers

In this section, we prove Theorem 5 concerning unidigital numbers. We leave the proofs of Theorems 3 and 4 until the next section.

Proof of Theorem 5. Let U_{n} = (10^{n} −1)/(10−1). A unidigital number is a positive integer of the form dU_{n} for some n ≥ 1 and d = 1, 2, …, 9. Thus, we want to solve the equation

d_{1}d_{2}U_{n}U_{m} = x^{p}, d_{1}, d_{2} = 1, 2, …, 9, p is prime.

We will show that m = n = 1 if p > 2 and m = n if p = 2, which immediately gives the theorem.

It is clear that

U_{n}U_{m} = 2^{a}3^{b}5^{c}7^{d}y^{p}.

Now 2, 5 cannot divide the product U_{n}U_{m}. Hence, we reduce to

U_{n}U_{m} = 3^{b}7^{d}y^{p}.

Suppose first that p > 2. We note here that the two sequences {U_{n}} and {U′_{n}} are identical. In the usual notation, r = 11, s = −10, Δ = 81, S = {2, 3}, S_{1} = ∅, S_{2} = {3} and T = {3, 7}. Write q for the greatest prime dividing mn. From Lemma 11, we have that q ∈ 𝔔 or U_{q} = z^{p}. But the equation U_{q} = z^{p} has no solutions (see [4]). Hence, q ∈ 𝔔. Now we apply the recipes in Section 6 to compute 𝔔′ and 𝔔. We find that 𝔔′ = {3}; for this, we need m_{7} = 6 which is not a prime. Furthermore, U_{2} = 11 and U_{3} = 3 × 37 which are not perfect powers up to S ∪ T, and hence 𝔔 = ∅. We deduce that the largest prime divisor of mn does not exist. In other words, m = n = 1 as required.

We now turn our attention to the case p = 2. In this case,

(15)  U_{m}U_{n} = 3^{b}7^{d}y^{2}.

We assume that b, d ∈ {0, 1}.

We first treat the case b = d = 0 and show that m = n. Writing D = gcd(m, n), we get that both U_{m}/U_{D} and U_{n}/U_{D} are squares. With x = 10^{D}, these equations show that (x^{m/D} − 1)/(x − 1) and (x^{n/D} − 1)/(x − 1) are perfect squares. The equation

\frac{x^{t} − 1}{x − 1} = y^{2}

was solved by Ljunggren (see [13]); its only solutions with x > 1 and t > 2 are given by (x, t) = (3, 5), (7, 4). Hence, m/D and n/D are 1 or 2, which shows that m = n or m = 2n. In the latter case, we get that U_{2n}/U_{n} = 10^{n} + 1 is a perfect square, which is impossible modulo 3. Hence, m = n as desired.

We now assume that b, d ∈ {0, 1} are not both zero, and deduce a contradiction. Consider equation (15) modulo 5. Clearly, U_{m}U_{n} ≡ 1 (mod 5) and y^{2} ≡ ±1 (mod 5). We deduce that b = d = 1. Furthermore, U_{n} is 1, 3, and −1 modulo 8 according to whether n = 1, n = 2, and n ≥ 3, respectively. But 3^{b}7^{d}y^{2} = 21y^{2} ≡ 5 (mod 8). Assuming without loss of generality that m ≤ n, we see that m = 2 and n ≥ 3. Since U_{2} = 11, we can rewrite equation (15) as

(16)  U_{n} = 3 × 7 × 11 × y_{1}^{2}.

Let q be the largest prime factor of n. We may now apply Lemma 11 with S, S_{1}, S_{2} as before, and T = {3, 7, 11}. We deduce that U_{q} = z^{2} or q ∈ 𝔔. Again U_{q} = z^{2} has no solutions by Ljunggren’s result. Moreover, 𝔔′ = {2, 3} (for this we need m_{11} = 2) and 𝔔 = {2}. Hence, the only possible prime divisor of n is 2. Moreover, U_{4} = 11 × 101, so Lemma 12 implies that 4 ∤ n. Hence, n = 1 or 2. This contradicts (16). □

11. Powers from Products of Fibonacci Numbers

We now come to the proofs of Theorems 3 and 4. We give the proof of Theorem 3 first because it is simpler and the reader will be able to verify all the calculations without the need for any programming.

Proof of Theorem 3. Here, r = s = 1, Δ = 5, S = {2, 5}, S_{1} = ∅, S_{2} = {5} and T = ∅.

Now note that we have m_{2} = 3. In the notation of Section 6, we see that 𝔔′ = {3, 5} and 𝔔 = {2, 3, 5}. As indicated in the introduction, the only solutions to F_{n} = y^{p} and given by n = 0, 1, 2, 6, 12. We now go through the steps of the Distillation Algorithm.

Step 1: This step tells us the greatest prime divisor q of the n_{i} belongs to the set Q = {2, 3, 5}, and so all the divisors of the n_{i} belong to the set R = {2, 3, 5}.

Step 2: This step does not change R which is not surprising as R is already very small.

Step 3: Now note the prime factorisations

F_{8} = 3 × 7, F_{9} = 2 × 17, F_{25} = 5 × 3001.

Thus, the exponents of 2, 3, 5 in the factorisations of the n_{i} are bounded respectively by 2, 1, 1.

Step 4: We deduce that the n_{i} belong to the set

{1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} .

We eliminate from this set all the elements n such that there is some k | n for which F_{k} is not a perfect power up to R ∪ S ∪ T = {2, 3, 5}. Thus, since F_{10} = 55 and F_{15} = 610, we can eliminate 10, 15, 20, 30, 60. It turns out that we cannot eliminate any other n in this step. Hence, the n_{i} belong to N = {1, 2, 3, 4, 5, 6, 12}.

Step 5 Applying the last step of the algorithm eliminates 5 from N. This is because F_{5} = 5 and 5 ∤ F_{n} for n ≠ 5 in the set N. Thus the n_{i} belong to N = {1, 2, 3, 4, 6, 12} as required in the first part of the theorem.

To prove the last assertion of the theorem, it only remains to solve the equation F_{m}F_{n} = y^{2}. This has been done by Cohn in [10], and independently but much later by Ribenboim in [16, Proposition 2]. They showed that either m, n ∈ {1, 2, 3, 6, 12}, or m = n. □

We point out that the set of possible indices {1, 2, 3, 4, 6, 12} in Theorem 3 cannot be reduced further. Indeed, F_{1} = F_{2} = 1. Thus, equation (3) reduces to

(17)  F_{3}^{a} · F_{4}^{b} · F_{6}^{c} · F_{12}^{d} = y^{p}

where a, b, c, d ≥ 0 satisfy a+b+c+d < p because of the condition m < p. We want to show that there is, for large enough p, a solution with a, b, c, d > 0; this certainly shows that the set of possible indices cannot be reduced further. By considering the prime-power factorisation, we deduce that equation (17) is equivalent to

(18)  a + 3c + 4d ≡ b + 2d ≡ 0 (mod p).

Thus, a quadruple of integers (a, b, c, d) is a solution to equation (17) if and only if it belongs to the lattice (18). The conditions a + b + c + d < p and a, b, c, d > 0 are equivalent to saying that the quadruple belongs to the convex set

(19)  {(δ_{1}, …, δ_{4}) ∈ ℝ^{4} : δ_{1}, …, δ_{4} > 0, δ_{1} + ⋯ + δ_{4} < p} .

The convex set has volume p^{4}/24, whilst the lattice has determinant p^{2}. Hence, the expected number of solutions is roughly p^{2}/24.

We finally turn to the proof of Theorem 4.

Proof of Theorem 4. We programmed our Distillation Algorithm using pari/gp. The theorem follows from applying our algorithm to the Fibonacci sequence with T being the set of the first hundred primes: T = {2, 3, 5, …, 541}. We give only the output at each stage of the algorithm. Before applying the algorithm we have

𝔔′ = {3, 5, 7, 11, 13, 19, 37, 59, 67, 79, 97, 139, 157, 199, 229} ,

and

𝔔 = {2, 3, 5, 7, 11, 13, 19} .

Step 1: Q = {2, 3, 5, 7, 11, 13, 19} and R = {2, 3, 5, 7, 11, 13, 17, 19}.

Step 2: R = {2, 3, 5, 7, 11, 13, 19}.

Step 3: The bounds for the exponents of the primes in the prime factorisations of the n_{i} are all 1 except for the exponents of 2 and 3 where these bounds are 4 and 3, respectively.

Steps 4 and 5: These steps both give

N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18,

19, 20, 21, 22, 24, 26, 27, 28, 30, 36, 42, 44} ,

as required in the statement of the theorem. □

12. Concluding Remarks

The essence of this paper is the Reduction Theorem. To be able to apply the Reduction Theorem one needs to solve equations of the form (2). The papers [3],

[8] are primarily concerned with the equation U_{n} = y^{p}. The purpose in this section is to convince the reader who is familiar with [3], [8] that the techniques of those papers are applicable to (2).

An equation of the form (2) yields a linear form in logarithms and this can be used to bound the exponent p. With current bounds for linear forms in logarithms we know the following:

• If the linear form involves 4 or more logarithms then the bound obtained for p will be hopelessly large and of no practical use in solving (2).

• If the linear form involves 3 logarithms then the bound for p will be quite reasonable—say around 10^{9}.

• If the linear form involves 2 logarithms then the bound for p will be small—

say around 1000. Since we want to bound p we may assume that p is odd. Equation (2) can be

rewritten as

(20)  \frac{α^{q} − β^{q}}{α − β} = A^{(q−1)/2}z^{p};

here we absorbed the ± into the z^{p}. Let us assume that α and β are real numbers. We deduce that

(21)  \frac{α}{α − β} (\frac{α^{2}}{A} )^{(q−1)/2} z^{−p} − 1 = O(|z|^{−p}).

This clearly results in a linear form in 3 logarithms, and so yields a reasonable bound for p.

Now the modular approach should be used. In particular ‘the method of predicting exponents’ [26] should, for large enough p, predict q modulo p. At this stage we need the bound for p obtained from the linear form in 3 logarithms. This method of predicting exponents should show that q ≡ q_{1}, …, q_{t} (mod p) for some finite list of congruence classes q_{1}, …, q_{t} that does not depend on p. Assuming that q ≡ q_{i} (mod p) we can rewrite (21) as

B_{i} (\frac{C_{i}^{k_{i}}}{z} )^{p} − 1 = O(|z|^{−p})

for a suitable algebraic constants B_{i}, C_{i} and integer k_{i}. This now results in a linear form in 2 logarithms which gives a very good bound for p.

Once these two steps are over and we have a very good bound for p the rest of the techniques in [3], [8] should enable us to complete the resolution of (2).

When α and β are complex non-real numbers, we use estimates for linear forms in 3 non-Archimedean logarithms to derive from (20) a reasonable upper bound for p. Then, applying as above ‘the method of predicting exponents’ enables us to use estimates for linear forms in 2 non-Archimedean logarithms, thus to get a very good bound for p.

We finally make a remark about the condition m < p in Theorems 1 and 2. The situation is much more complicated without this condition, since otherwise equation (1) has obviously infinitely many solutions (recall that the indices n_{i} are not assumed to be distinct). We present a conjecture that allows us to predict that apart from finitely many solutions, the solutions are essentially diagonal.

If n is a positive integer then a primitive divisor of U_{n} is a prime l dividing U_{n} but not dividing U_{m} for all 1 ≤ m < n. A celebrated theorem of Bilu, Hanrot and Voutier [1] states that if U_{n} is a non-degenerate Lucas sequence and n > 30 then U_{n} has a primitive divisor (under the additional assumption that associated parameters r, s are coprime). We shall call l a primary divisor of U_{n} if it is a primitive divisor and l || U_{n}.

Conjecture 7. Suppose that {U_{n}}_{n≥0} is a non-degenerate Lucas sequence. There exists a constant C such that for all n ≥ C the Lucas term U_{n} has a primary divisor.

The above conjecture is based on extensive computational experience with Lucas sequences. It appears to be hopelessly out-of-reach, but it does allow us to deduce the following.

Theorem 8. Assume that Conjecture 7 holds. Suppose that {U_{n}}_{n≥0} is a nondegenerate Lucas sequence and T is a finite set of primes. Let C be the constant appearing in the conjecture above, and let

C′ = max(C, max_{q∈T}(m_{q} + 1)),

where as usual m_{q} denotes the rank of the first appearance of the prime q for the sequence {U_{n}}. Suppose that

∏_{i=1}^{m} U_{n_{i}} = μy^{p}, μ ∈ \overline{T} , m, y ∈ ℤ^{+}, p prime, n_{1} ≥ n_{2} ≥ ⋯ ≥ n_{m} ≥ 1.

Then there is an integer k ≥ 0 such that

n_{kp+1}, …, n_{m} < C′

and

n_{1} = n_{2} = … = n_{p}, n_{p+1} = … = n_{2p}, … n_{(k−1)p+1} = … = n_{kp}.

Proof. If n_{1} < C′ then there is nothing to prove. Thus suppose that n_{1} ≥ C′. By the conjecture above, there is a prime l that is a primitive divisor of U_{n_{1}} and l || U_{n_{1}}. Moreover, since n_{1} > m_{q} for q ∈ T we see that l ∉ T. Thus the exponent to which l divides the term μy^{p} is at least p. Since l || U_{n_{1}} and l ∤ U_{n} for n < n_{1} we see that n_{1} = n_{2} = … = n_{p}. We now divide both sides of the equation ∏_{n_{i}} U_{n_{i}} = μy^{p} with U_{n_{1}}^{p} and repeat the argument. □

References

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

[2] Y. Bugeaud, On the Diophantine equation a \frac{x^{n}−1}{x−1} = y^{q}, Proceedings of the Number Theory Conference held in Turku, ed. M. Jutila and T. Metsänkylä, 19–24, De Gruyter, 2001.

[3] Y. Bugeaud, F. Luca, M. Mignotte and S. Siksek, On perfect powers in Lucas sequences, International Journal of Number Theory 1 (2005), no. 3, 309–332.

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

[5] Y. Bugeaud and M. Mignotte, Sur l’équation diophantienne \frac{x^{n}−1}{x−1} = y^{q}, II, C. R. Acad. Sci. Paris, Ser. I 328 (1999), 741–744.

[6] Y. Bugeaud and M. Mignotte, L’Équation de Nagell-Ljunggren \frac{x^{n}−1}{x−1} = y^{q}, Enseign. Math. 48 (2002), 147–168.

[7] Y. Bugeaud, M. Mignotte and S. Siksek, Sur les nombres de Fibonacci de la forme q^{k}y^{p}, C. R. Acad. Sci. Paris, Ser. I 339 (2004), 327–330.

[8] Y. Bugeaud, M. Mignotte and S. Siksek, Classical and modular approaches to exponential Diophantine equations I. Fibonacci and Lucas perfect powers, Ann. of Math. 163 (2006), no. 3, 969–1018.

[9] Y. Bugeaud, M. Mignotte and S. Siksek, Classical and modular approaches to exponential Diophantine equations II. The Lebesgue-Nagell equation, Compos. Math. 142 (2006), no. 1, 31–62.

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

[11] K. Inkeri, On the diophantine equation a(x^{n} − 1)/(x − 1) = y^{m}, Acta Arith. 21 (1972), 299–311.

[12] F. Luca and T. N. Shorey, Diophantine equations with products of consecutive terms in Lucas sequences, J. Number Theory 114 (2005), no. 2, 298–311.

[13] W. Ljunggren, Some theorems on indeterminate equations of the form (x^{n} − 1)/(x − 1) = y^{q}. (Norwegian) Norsk Mat. Tidsskr. 25, (1943). 17–20.

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

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

[16] P. Ribenboim, Square classes of Fibonacci and Lucas numbers, Portugal. Math. 46 (1989), Fasc. 2, 159–175.

[17] P. Ribenboim, Square classes of (a^{n} − 1)/(a − 1) and a^{n} + 1, Sichuan Daxue Xuebao 26 (1989), Special Issue, 196–199.

[18] P. Ribenboim, Pell numbers, squares and cubes, Publ. Math. Debrecen 54/1-2 (1999), 131– 152.

[19] P. Ribenboim, An algorithm to determine points with integral coordinates on certain elliptic curves, J. Number Theory 74 (1999), 19–38.

[20] P. Ribenboim, The terms Cx^{h} (h ≥ 3) in Lucas sequences: an algorithm and applications to Diophantine equations, Acta Arith. 106.2 (2003), 105–114.

[21] P. Ribenboim and W. L. McDaniel, Square classes of Lucas sequences, Portugal. Math. 48 (1991), no. 4, 469–473.

[22] P. Ribenboim and W. L. McDaniel, The square classes in Lucas sequences with odd parameters, C. R. Math. Rep. Acad. Sci. Canada XVIII (1996), no. 5, 223–227.

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

[24] 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.

[25] T. N. Shorey and R. Tijdeman, Exponential Diophantine equations, Cambridge University Press, 1986.

[26] S. Siksek Level lowering and Diophantine equations, in Explicit Methods in Number Theory, Ed. K. Belabas, Panoramas et Synthèses, Société Mathématique De France, to appear.

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

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

Florian Luca, Instituto de Matemáticas, Universidad Nacional Autónoma de México, C.P. 58180, Morelia, Michoacán, México

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

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

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

Samir Siksek, Mathematics Institute, University of Warwick, Coventry, CV4 7AL, United Kingdom

   E-mail address: siksek@maths.warwick.ac.uk