The Top Twenty: Generalized Lucas Number

In a problem in his text Liber Abbaci (published in 1202), Fibonacci introduced his now famous sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ....

Each term is the sum of the two proceeding terms. Lucas [Lucas1878] generalized this by defining pairs of sequences {U₀, U₁, U₂, ...} and {V₀, V₁, V₂, ...} for which the next term is P times the current term minus Q times the previous one:

U_n+1 = P*U_n - Q*U_n-1 and V_n+1 = P*V_n - Q*V_n-1.

We usually require that P and Q be non-zero integers and that (the discriminant) D = P²-4Q is also not zero.

To define the Lucas sequences, let a and b be the zeros of the polynomial x²-Px+Q, then define the two companion sequences as follows:

U_n(P,Q) = (aⁿ - bⁿ)/(a - b), and V_n(P,Q) = aⁿ + bⁿ.

So U₀=0, U₁=1,V₀=2, and V₁=P; and the sequences follow the recurrence relations given above. These sequences are both called Lucas sequences, and the numbers in them are the generalized Lucas numbers.

These sequences have many useful properties such as: U_2n=U_nV_n; and if p is and odd prime, then p divides U_p-(D/p) where (D/p) is the Legendre symbol. Ribenboim's book (pp. 54--83) gives an excellent review.

The role of Lucas sequences in primality proving was begun by Lucas and cemented by [Morrison75]. Their primitive parts (also known as Sylvester's cyclotomic numbers) were studied in [Ward1959]. Prime generalized Lucas numbers are clearly a particular case of prime primitive parts, occurring when n is also a prime. As Ribenboim indicates, there is an extensive literature on primitive prime Lucas factors, from [Carmichael1913] to [Voutier1995], via, for example, [Schinzel1974] and [Stewart1977].