Products of Prime Powers in Binary Recurrence Sequences Part I: The Hyperbolic Case, with an Application to the Generalized Ramanujan-Nagell Equation

We show how the Gelfond-Baker theory and diophantine approximation techniques can be applied to solve explicitly the diophantine equation G, = wp" ... p', (where (G,, }I='o is a binary recurrence sequence with positive discriminant), for arbitrary values of the parameters.We apply this to the equation x2 + k = ... ps', which is a generalization of the Ramanujan-Nagell equation x2 + 7 = 2Z.We present algorithms to reduce upper bounds for the solutions of these equations.The algorithms are easy to translate into computer programs.We present an example which shows that in practice the method works well. Introduction. The Gelfond-Baker method is one of the most useful tools in the theory of diophantine equations. It has been used to prove effectively computable upper bounds for the solutions of many diophantine problems (cf. Baker [1], Shorey and Tijdeman [17]).However, the derived upper bounds are so large that in many cases it is hopeless to compute all solutions, even with the fastest present-day computers.It seems likely that refinements of the Gelfond-Baker method will not be able to change this situation essentially in the near future.In those cases where this method has been applied successfully to find all solutions of a certain equation, this has been achieved by reducing the upper bounds considerably, using diophantine approximation techniques (cf.Stroeker and Tijdeman [19]), or by making use of special properties of the diophantine problem (cf.Petho [12], [13]).These reduced bounds are in practice always small enough to admit enumeration of the remaining possibilities.In this paper we present such a reduction algorithm for the following problem.Let A, B, Go, G1 be integers, and let the recurrence sequence { GQ }X=0 be defined by Gn+1 = AGn -BGn-, (n = 19 2, . . . ) .Put A = 2 -4B, and assume that A > 0, and that the sequence is not degenerate.Let w be a nonzero integer, and let Pl, ... p,1 be distinct prime numbers.We study the diophantine equation (1.1) G =wpMI ... pt'