Primitive divisors of Lucas and Lehmer sequences, II

Voutier, Paul M.

Journal de théorie des nombres de Bordeaux, Tome 8 (1996) no. 2, pp. 251-274.

Soit $\alpha$ et $\beta$ deux entiers algébriques complexes conjugués. On propose un algorithme dont l’objet est de découvrir des éléments des suites de Lucas ou de Lehmer associées à $\alpha$ et $\beta$, n’ayant pas de diviseurs primitifs. On utilise cet algorithme pour démontrer que pour tout $\alpha$ et $\beta$ tel que $h(\beta /\alpha )\le 4$, le $n$-ième terme des suites de Lucas et de Lehmer admet un diviseur primitif dès que $n>30$. Nous donnons en outre une amélioration d’un résultat de Stewart se rapportant à des suites plus générales.

Let $\alpha$ and $\beta$ are conjugate complex algebraic integers which generate Lucas or Lehmer sequences. We present an algorithm to search for elements of such sequences which have no primitive divisors. We use this algorithm to prove that for all $\alpha$ and $\beta$ with h$(\beta /\alpha )\le 4$, the $n$-th element of these sequences has a primitive divisor for $n>30$. In the course of proving this result, we give an improvement of a result of Stewart concerning more general sequences.

[1] P.T. Bateman, C. Pomerance and R.C. Vaughan,, On the size of the coefficients of the cyclotomic polynomial, Topics in Classical Number Theory,, (Budapest, 1981), Colloquia Mathematica Societatis Janos Bolyai, 34, North-Holland, New York, 1984. | MR | Zbl

[2] G.D. Birkhoff and H.S. Vandiver, On the integral divisors of an - bn, Ann. of Math. (2) 5 (1904), 173-180. | JFM | MR

[3] L. Carlitz, On the coefficients of the cyclotomic polynomials, Amer. Math. Monthly 75 (1968), 372-377. | MR | Zbl

[4] R.D. Carmichael, On the numerical factors of the arithmetic forms an ±βn, Ann. of Math. (2) 15 (1913), 30-70. | JFM

[5] L. K. Durst Exceptional real Lehmer sequences, Pacific J. Math. 9 (1959), 437-441. | MR | Zbl

[6] G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 5th edition, 1978. | MR | Zbl

[7] G. Karpilovsky, Field Theory: Classical Foundations and Multiplicative Groups, Marcel Dekker, New York, 1988. | MR | Zbl

[8] M. Laurent, M. Mignotte and Y. Nesterenko, Formes Linéaires en deux logarithmes et déterminants d'interpolation, J. Number Theory, to appear. | Zbl

[9] D.H. Lehmer, The distribution of totatives, Canadian J. Math. 7 (1955), 347-357. | MR | Zbl

[10] P. Philippon and M. Waldschmidt, Lower bounds for linear forms in logarithms, New Advances in Transcendence Theory (A. Baker, ed.), Cambridge University Press, Cambridge, 1988. | MR

[11] G. Robin, Estimation de la fonction de Tchebychef θ sur le k-ième nombre premier et grandes valeurs de la fonction w(n) nombre de diviseurs premiers de n, Acta Arith. XLII (1983), 367-389. | EuDML | Zbl

[12] J.B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94. | MR | Zbl

[13] A. Schinzel, Primitive divisors of the expression An - Bn in algebraic number fields, J. Reine Angew. Math. 268/269 (1974), 27-33. | EuDML | MR | Zbl

[14] C.L. Stewart, Primitive divisors of Lucas and Lehmer sequences, Transcendence Theory: Advances and Applications (A. Baker and D.W. Masser, eds.), Academic Press, New York, 1977. | MR

[15] C.L. Stewart, On divisors of Fermat, Fibonacci, Lucas and Lehmer numbers, Proc. London Math. Soc. (3) 35 (1977), 425-447. | MR | Zbl

[16] P.M. Voutier, Primitive divisors of Lucas and Lehmer sequences, Math. Comp. 64 (1995), 869-888. | MR | Zbl

[17] P.M. Voutier, An effective lower bound for the height of algebraic numbers, Acta Arith., (to appear). | MR | Zbl

[18] M. Waldschmidt, Linear Independence of Logarithms of Algebraic Numbers, IMSc Report No 116 (1992), The Institute of Mathematical Sciences, Madras. | Zbl

[19] M. Ward, The intrinsic divisors of Lehmer numbers, Ann. of Math. (2) 62 (1955), 230-236. | MR | Zbl

[20] K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math. 3 (1892), 265-284. | JFM | MR