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

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. NEWLINENEWLINENEWLINEThere 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). NEWLINENEWLINENEWLINEMain result of the paper: Every integer \(N> 30\) is totally non-defective. NEWLINENEWLINENEWLINEBased, 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. NEWLINENEWLINENEWLINEThe solution is, of course, too complicated to be described in a short review. We only mention a few important ingredients of the proof: NEWLINENEWLINENEWLINE(i) The cyclotomic criterion for Lehmer pairs due to C. Stewart. NEWLINENEWLINENEWLINE(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. NEWLINENEWLINENEWLINE(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. NEWLINENEWLINENEWLINE(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''.