Az Eszterházy Károly Tanárképző Főiskola Tudományos Közleményei. 2004. Sectio Mathematicae. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 31)

LUCA, F., Primitive divisors of Lucas sequences and prime factors of ... and ...

Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae 31 (2004) 19-24 PRIMITIVE DIVISORS OF LUCAS SEQUENCES AND PRIME FACTORS OF x

2 + ] AND x

4 + 1 Florian Luca (Michoacán, Mexico) Abstract. In this paper, we show that 24208144

3+l=29

3-37

2-53-61

2-89 is the largest instance in which n

2+ I does not have any prime factor >100. 1. Introduction For any integer n let, P(n) be the largest prime factor of n with the convention that P(0) = P{± 1) = I. In [8], it is shown that if x is an integer, then + 1) > 17 once > 240. The method presented in [8] is elementary, and the computations were done using congruences with respect, to small moduli. The purpose of this note is two fold. First of all, we improve the lower bound from [8] by showing that P(x

2 + 1) > 101 once \x\ > 24208145. Secondly, our method is entirely different from the one presented in [8] in the sense that it uses the existence of primitive prime divisors for the Lucas sequences associated to certain Pell equations. This method has been used previously by Lehmer in [6] to compute all the positive integer solutions x of the inequality P(x(x + 1)) < 41. The method is completely general and, in practice, armed with a good computer, one can employ it to find all the integer solutions x of the inequality P(x

2 + 1) < A', where A is any given reasonable constant. We also use the same method to show that P(x

A + \) > 233 for x > 11, which extends the range of computations described in [7] and [9] where it was shown that P(x

4 + 1) > 73 if x > 3. We recall that explicit lower bounds for P(x

3 + 1) appear in [1]. This note is organized as follows. In the second section, we present our algorithm and computational findings. In the third section, we make an analysis of the running time of our algorithm for computing all positive integer solutions x of the inequality P(x

2 + 1) < A in terms of A. 2. Computational Results Theorem 2.1. (i) The largest positive integer solution x of the inequality P(x

2 + 1) < 101