Let , be Positive Integers. The Roots of

(1) |

(2) | |||

(3) |

where

(4) |

(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) |

(26) |

(27) |

**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.

© 1996-9

1999-05-25