## Lucas Sequence

Let , be Positive Integers. The Roots of

 (1)

are
 (2) (3)

where
 (4)

so
 (5) (6) (7)

Then define
 (8) (9)

The first few values are therefore
 (10) (11) (12) (13)

The sequences
 (14) (15)

are called Lucas sequences, where the definition is usually extended to include
 (16)

For , the are the Fibonacci Numbers and are the Lucas Numbers. For , the Pell Numbers and Pell-Lucas numbers are obtained. produces the Jacobsthal Numbers and Pell-Jacobsthal Numbers.

The Lucas sequences satisfy the general Recurrence Relations

 (17) (18)

Taking then gives
 (19) (20)

Other identities include
 (21) (22) (23) (24)

These formulas allow calculations for large to be decomposed into a chain in which only four quantities must be kept track of at a time, and the number of steps needed is . The chain is particularly simple if has many 2s in its factorization.

The s in a Lucas sequence satisfy the Congruence

 (25)

if
 (26)

where
 (27)

This fact is used in the proof of the general Lucas-Lehmer Test.

See also Fibonacci Number, Jacobsthal Number, Lucas-Lehmer Test, Lucas Number, Lucas Polynomial Sequence, Pell Number, Recurrence Sequence, Sylvester Cyclotomic Number

References

Dickson, L. E. Recurring Series; Lucas' , .'' Ch. 17 in History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Chelsea, pp. 393-411, 1952.

Ribenboim, P. The Little Book of Big Primes. New York: Springer-Verlag, pp. 35-53, 1991.