Existence of primitive divisors of Lucas and Lehmer numbers (with an appendix by M. Mignotte). (English) Zbl 0995.11010

Bilu, Yu.; Hanrot, G.; Voutier, P. M.

J. Reine Angew. Math. 539, 75-122 (2001).

A Lucas pair of algebraic numbers \((\alpha,\beta)\) is defined by the condition: \(\alpha+\beta\) and \(\alpha\beta\) are nonzero coprime rational integers and \(\alpha/\beta\) is not a root of unity. To such a pair \((\alpha,\beta)\) there corresponds a Lucas sequence defined by \(u_n(\alpha,\beta)= \frac{\alpha^n-\beta^n} {\alpha-\beta}\), \(n=0,1,2,\dots\;\). A Lehmer pair of algebraic numbers \((\alpha,\beta)\) is defined by the condition: \((\alpha+\beta)^2\) and \(\alpha\beta\) are nonzero coprime rational integers and \(\alpha/\beta\) is not a root of unity. The corresponding Lehmer sequence is defined by \(\widetilde{u}_n (\alpha,\beta)= \frac{\alpha^n-\beta^n} {\alpha-\beta}\) if \(n\) is odd and \(\widetilde{u}_n (\alpha,\beta)= \frac{\alpha^n-\beta^n} {\alpha^2-\beta^2}\) if \(n\) is even. Obviously, a Lucas pair is also a Lehmer pair with \(u_n= \widetilde{u}_n\) if \(n\) is odd and \(u_n= (\alpha+\beta) \widetilde{u}_n\) if \(n\) is even.
There is a vast literature on Lucas and Lehmer sequences. One difficult question is the existence of primitive divisors for such sequences. A prime number \(p\) is a primitive divisor for the term \(u_N\) of a Lucas sequence \((u_n)\) if \(p\) divides \(u_n\) but does not divide \((\alpha-\beta)^2 u_1u_2\cdots u_{N-1}\). Analogously, a prime number \(p\) is a primitive divisor for the term \(\widetilde{u}_N\) of a Lehmer sequence \((\widetilde{u}_n)\) if \(p\) divides \(\widetilde{u}_N\) but does not divide \((\alpha^2-\beta^2)^2 \widetilde{u}_1 \widetilde{u}_2\cdots \widetilde{u}_{N-1}\). A Lucas (respectively, Lehmer) pair \((\alpha,\beta)\) is called \(N\)-defective Lucas (respectively, Lehmer) pair if \(u_N (\alpha,\beta)\) (respectively, \(\widetilde{u}_N (\alpha,\beta)\)) has no primitive divisor. A positive integer \(N\) is called totally non-defective if no \(N\)-defective Lehmer pair exists, i.e. if the \(N\)th term of every Lehmer sequence has a primitive divisor (hence, also, the \(N\)th term of every Lucas sequence has a primitive divisor).
Main result of the paper: Every integer \(N> 30\) is totally non-defective.
Based, on the other hand, on previous work of P. Voutier and an idea of C. Stewart, the authors explicitly classify all Lucas and Lehmer pairs which are \(N\)-defective for some \(N\leq 30\). As a result, the problem of listing explicitly all triples \((\alpha,\beta,N)\), where \((\alpha,\beta)\) is a Lucas (respectively, Lehmer) pair and \(N\) is a positive integer, is now completely solved due to this significant paper.
The solution is, of course, too complicated to be described in a short review. We only mention a few important ingredients of the proof:
(i) The cyclotomic criterion for Lehmer pairs due to C. Stewart.
(ii) The method for explicitly solving by Baker’s method Thue equations of very high degree, due to the first two authors of this paper. It is important to mention here that the method is adapted so that the knowledge of the full unit group is not necessary, but only a full rank subgroup of it.
(iii) A variant by M. Mignotte of a theorem of M. Laurent, M. Mignotte and Y. Nesterenko on homogeneous forms in two logarithms of algebraic numbers. This variant deals with the more special linear form \(b_1i\pi- b_2\log\alpha\) and is given a separate 10 pages appendix.
(iv) Heavy use of the computer and the computer package PARI for solving very many Thue equations, where the reduction of the very large upper bounds obtained by Baker’s method is mainly achieved by the “lemma of Baker and Davenport”.

Reviewer: Nikos Tzanakis (Iraklion)

MSC:

11B39	Fibonacci and Lucas numbers and polynomials and generalizations
11D59	Thue-Mahler equations
11J86	Linear forms in logarithms; Baker’s method
11Y50	Computer solution of Diophantine equations
11R18	Cyclotomic extensions

Keywords:

Thue equations of high degree; linear forms in two logarithms; \(n\)-defective Lucas and Lehmer pairs; Lucas pair; Lucas sequence; Lehmer pair; Lehmer sequence; primitive divisors; PARI

References:

[1]	Phil. Trans. Roy. Soc. London 263 pp 173– (1968)
[2]	A. Baker, H. Davenport, The equations 3x2- 2 = y2and 8x2- 7 = z2, Quat. J. Math. Oxford (2) 20 (1969), 129-137.
[3]	Baker A., Math. 442 pp 19– (1993)
[4]	A. S. Bang, Taltheoretiske Undersugelser, Tidsskrift Mat. (5) 4 (1886), 70-80, 130-137.
[5]	Yu, Univ. Bordeaux pp 2– (1994)
[6]	Bilu Yu., J. Number Th. 60 pp 373– (1996)
[7]	Bilu Yu., Compos. Math. 112 pp 273– (1998)
[8]	Bilu Yu., Acta Arith. 88 pp 311– (1999)
[9]	G. D. Birkho , H. S. Vandiver, On the integral divisors of an- bn, Ann. Math. (2) 5 (1904), 173-180.
[10]	Progr. Math. 91 pp 27– (1990)
[11]	P. D. Carmichael, On the numerical factors of the arithmetic forms ?nq ?n, Ann. Math. (2) 15 (1913), 30-70. · JFM 44.0216.01
[12]	Cohen H., Grad. Texts Math. pp 138– (1993)
[13]	Cohen H., J. Symbolic Comput. 24 pp 433– (1997)
[14]	L. K. Durst, Exceptional real Lehmer sequences, Paci c J. Math. 9 (1959), 437-441. · Zbl 0091.04204
[15]	L. K. Durst, Exceptional real Lucas sequences, Paci c J. Math. 11 (1961), 489-494. · Zbl 0112.26905
[16]	Inv. Math. 98 pp 599– (1989)
[17]	G. Hanrot, ReAsolution e ective d’eAquations diophantiennes: algorithmes et applications, TheAse, UniversiteA Bordeaux 1, 1997.
[18]	Math. Comp. 69 pp 395– (2000)
[19]	A. Ya. Khintchine, Continued fractions (in Russian), Nauka, Moscow1978.
[20]	S. Lang, Fundamentals of Diophantine Geometry, Springer, 1983. · Zbl 0528.14013
[21]	Laurent M., J. Number Th. 55 pp 285– (1995)
[22]	D., Ann. Math. 31 pp 419– (1930)
[23]	DOI: 10.1007/BF01457454 · Zbl 0488.12001
[24]	van der Linden F. J., Math. Comp. 39 pp 693– (1982)
[25]	Amer. J. Math. 1 (1878) pp 184–
[26]	J., Compos. Math. 37 pp 297– (1978)
[27]	A. PethoI, Computational Methods For the Resolution of Diophantine Equations, in: R. A. Mollin (ed.), Number Theory: Proc. First Conf. Can. Number Th. Ass., Ban 1988, de Gruyter (1990), 477-492.
[28]	Pohst M. E., Abh. Math. Sem. Hamburg 47 pp 95– (1978)
[29]	M. E. Pohst, Computational Algebraic Number Theory, DMV Seminar21, BirkhaEuser, Basel 1993.
[30]	M. E. Pohst, H. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge Univ. Press, 1989. · Zbl 0685.12001
[31]	Postnikova L. P., Mat. Sbornik 75 pp 171– (1968)
[32]	Proceedings of the International Congress of Mathematicians, ZuErich 1994, Volume 1, BirkhaEuser, 1995.
[33]	P. Ribenboim, The Fibonacci numbers and the Arctic Ocean, in: Behara, Fritsch and Lintz (eds.), Symposia Gaussiana, Conf. A, de Gruyter (1995), 41-83. · Zbl 0858.11011
[34]	Ark. Mat. 4 pp 413– (1962)
[35]	Acta Arith. 8 pp 213– (1968)
[36]	Math. 268 pp 27– (1974)
[37]	C. Stewart, Primitive divisors of Lucas and Lehmer numbers, in: A. Baker and D. W. Masser (eds.), Transcendence Theory: Advances and Applications, Academic Press (1977), 79-92. · Zbl 0366.12002
[38]	C. Stewart, On divisors of Fermat, Fibonacci, Lucas and Lehmer numbers, Proc. London Math. Soc. (3) 35 (1977), 425-447. · Zbl 0389.10014
[39]	Tzanakis N., J. Number Th. 31 pp 99– (1989)
[40]	Voutier P. M., Math. Comp. 64 pp 869– (1995)
[41]	Voutier P. M., J. Th. Nombres Bordeaux 8 pp 251– (1996)
[42]	Voutier P. M., Math. Proc. Cambridge Phil. Soc. 123 pp 407– (1998)
[43]	M. Ward, The intrinsic divisors of Lehmer numbers, Ann. Math. (2) 62 (1955), 230-236. · Zbl 0065.27102
[44]	L., Springer Grad. Texts Math. pp 83– (1982)
[45]	Zimmert R., Invent. Math. 62 pp 367– (1981)
[46]	Zsigmondy K., Monatsh. Math. 3 (1892) pp 265–