Lucas sequence
Encyclopedia
In mathematics
, the Lucas sequences Un(P,Q) and Vn(P,Q) are certain integer sequence
s that satisfy the recurrence relation
where P and Q are fixed integers. Any other sequence satisfying this recurrence relation can be represented as a linear combination
of the Lucas sequences Un(P,Q) and Vn(P,Q).
Famous examples of Lucas sequences include the Fibonacci number
s, a superset of the Fermat numbers, Mersenne numbers, Pell number
s, Lucas number
s and Jacobsthal number
s. Lucas sequences are named after the French
mathematician
Édouard Lucas
.
s:
and
It is not hard to show that for
,
and 
is:
It has the discriminant
and the roots:
Thus:
Note that the sequence
and the sequence 
also satisfy the recurrence relation. However these might not be integer sequences.
, a and b are distinct and one quickly verifies that
.
It follows that the terms of Lucas sequences can be expressed in terms of a and b as follows
occurs exactly when 
for some integer S so that 
. In this case one easily finds that
.
s
and Lucas number
s
. For example:
Among the consequences is that
is a multiple of 
, implying that 
can be prime only when n is prime.
Another consequence is an analog of exponentiation by squaring
that allows fast computation of
for large values of n.
These facts are used in the Lucas–Lehmer primality test.
Carmichael's theorem
states that, in a Lucas sequence, all but finitely many of the numbers have a prime factor
that does not divide any earlier number in the sequence .
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Lucas sequences Un(P,Q) and Vn(P,Q) are certain integer sequence
Integer sequence
In mathematics, an integer sequence is a sequence of integers.An integer sequence may be specified explicitly by giving a formula for its nth term, or implicitly by giving a relationship between its terms...
s that satisfy the recurrence relation
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
- xn = Pxn-1 - Qxn-2
where P and Q are fixed integers. Any other sequence satisfying this recurrence relation can be represented as a linear combination
Linear combination
In mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
of the Lucas sequences Un(P,Q) and Vn(P,Q).
Famous examples of Lucas sequences include the Fibonacci number
Fibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
s, a superset of the Fermat numbers, Mersenne numbers, Pell number
Pell number
In mathematics, the Pell numbers are an infinite sequence of integers that have been known since ancient times, the denominators of the closest rational approximations to the square root of 2. This sequence of approximations begins 1/1, 3/2, 7/5, 17/12, and 41/29, so the sequence of Pell numbers...
s, Lucas number
Lucas number
The Lucas numbers are an integer sequence named after the mathematician François Édouard Anatole Lucas , who studied both that sequence and the closely related Fibonacci numbers...
s and Jacobsthal number
Jacobsthal number
In mathematics, the Jacobsthal numbers are an integer sequence named after the German mathematician Ernst Jacobsthal. Like the related Fibonacci numbers, they are a specific type of Lucas sequence U_n for which P = 1, and Q = −2—and are defined by a similar recurrence...
s. Lucas sequences are named after the French
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Édouard Lucas
Edouard Lucas
François Édouard Anatole Lucas was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him.-Biography:...
.
Recurrence relations
Given two integer parameters P and Q, the Lucas sequences of the first kind Un(P,Q) and of the second kind Vn(P,Q) are defined by the recurrence relationRecurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
s:
and
It is not hard to show that for
,Formula for values
 |  |  |
|---|---|---|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Algebraic relations
The characteristic equation of the recurrence relation for Lucas sequences and is:It has the discriminant
Discriminant
In algebra, the discriminant of a polynomial is an expression which gives information about the nature of the polynomial's roots. For example, the discriminant of the quadratic polynomialax^2+bx+c\,is\Delta = \,b^2-4ac....
and the roots:Thus:
Note that the sequence
and the sequence also satisfy the recurrence relation. However these might not be integer sequences.Distinct roots
When, a and b are distinct and one quickly verifies that.It follows that the terms of Lucas sequences can be expressed in terms of a and b as follows
Repeated root
The case occurs exactly when for some integer S so that . In this case one easily finds that.Other relations
The terms of Lucas sequences satisfy relations that are generalizations of those between Fibonacci numberFibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
s
and Lucas numberLucas number
The Lucas numbers are an integer sequence named after the mathematician François Édouard Anatole Lucas , who studied both that sequence and the closely related Fibonacci numbers...
s
. For example:| General | P = 1, Q = -1 |
|---|---|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
Among the consequences is that
is a multiple of , implying that can be prime only when n is prime.Another consequence is an analog of exponentiation by squaring
Exponentiation by squaring
Exponentiating by squaring is a general method for fast computation of large integer powers of a number. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add...
that allows fast computation of
for large values of n.These facts are used in the Lucas–Lehmer primality test.
Carmichael's theorem
Carmichael's theorem
Carmichael's theorem, named after the American mathematician R.D. Carmichael, states that for n greater than 12, the nth Fibonacci number F has at least one prime factor that is not a factor of any earlier Fibonacci number. The only exceptions for n up to 12 are:Carmichael's theorem, named after...
states that, in a Lucas sequence, all but finitely many of the numbers have a prime factor
Prime factor
In number theory, the prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder. The process of finding these numbers is called integer factorization, or prime factorization. A prime factor can be visualized by understanding Euclid's...
that does not divide any earlier number in the sequence .
Specific names
The Lucas sequences for some values of P and Q have specific names:- Un(1,−1) : Fibonacci numberFibonacci numberIn mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
s - Vn(1,−1) : Lucas numberLucas numberThe Lucas numbers are an integer sequence named after the mathematician François Édouard Anatole Lucas , who studied both that sequence and the closely related Fibonacci numbers...
s - Un(2,−1) : Pell numberPell numberIn mathematics, the Pell numbers are an infinite sequence of integers that have been known since ancient times, the denominators of the closest rational approximations to the square root of 2. This sequence of approximations begins 1/1, 3/2, 7/5, 17/12, and 41/29, so the sequence of Pell numbers...
s - Vn(2,−1) : Companion Pell numbers or Pell-Lucas numbers
- Un(1,−2) : Jacobsthal numberJacobsthal numberIn mathematics, the Jacobsthal numbers are an integer sequence named after the German mathematician Ernst Jacobsthal. Like the related Fibonacci numbers, they are a specific type of Lucas sequence U_n for which P = 1, and Q = −2—and are defined by a similar recurrence...
s - Un(3, 2) : Mersenne numbers 2n − 1
- Vn(3, 2) : Numbers of the form 2n + 1, which include the Fermat numbers .
Applications
- LUC is a public-key cryptosystem based on Lucas sequences that implements the analogs of ElGamal (LUCELG), Diffie-Hellman (LUCDIF), and RSA (LUCRSA). The encryption of the message in LUC is computed as a term of certain Lucas sequence, instead of using modular exponentiationModular exponentiationModular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography....
as in RSA or Diffie-Hellman. However, a paper by Bleichenbacher et al. shows that many of the supposed security advantages of LUC over cryptosystems based on modular exponentiation are either not present, or not as substantial as claimed.