Primitive Divisors of Lucas and Lehmer sequences
by
Guillaume Hanrot
LORIA - INRIA Lorraine
Coauthors: Yuri Bilu (Basel), Paul Voutier (London)

Let \alpha and \beta be algebraic numbers such that \alpha+\beta and \alpha\beta are non-zero coprime rational integers, and \alpha/\beta is not a root of unity. The sequence

un = un(\alpha, \beta) =  \alphan -\betan \alpha-\beta        (n=1, 2, ... )

is called the Lucas sequence associated to the pair (\alpha, \beta).

A prime divisor p dividing u_n is a primitive divisor if p does not divide (\alpha-\beta)² u₁ ... u_n-1.

I shall outline the solution of an old problem: finding all the terms of Lucas sequences (and also for Lehmer sequences) without a primitive divisor. In particular, if u_n has no primitive divisor, then n <= 30.

Part of the argument is based on heavy (but rigorous) computations to solve Diophantine equations of extremely high degree (higher than 500).

PS version of the paper

Date received: March 23, 1999