In
mathematics, the Lucas sequences
and
are certain
constant-recursive integer sequences that satisfy the
recurrence relation
:
where
and
are fixed integers. Any sequence satisfying this recurrence relation can be represented as a
linear combination of the Lucas sequences
and
.
More generally, Lucas sequences
and
represent sequences of
polynomials in
and
with integer coefficients.
Famous examples of Lucas sequences include the
Fibonacci numbers,
Mersenne numbers,
Pell numbers,
Lucas numbers,
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(P,Q) for which ''P'' = 1, and ''Q' ...
s, and a superset of
Fermat numbers . Lucas sequences are named after the
French mathematician Édouard Lucas
__NOTOC__
François Édouard Anatole Lucas (; 4 April 1842 – 3 October 1891) 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
Luc ...
.
Recurrence relations
Given two integer parameters
and
, the Lucas sequences of the first kind
and of the second kind
are defined by the
recurrence relations:
:
and
:
It is not hard to show that for
,
:
The above relations can be stated in matrix form as follows:
:
:
:
Examples
Initial terms of Lucas sequences
and
are given in the table:
:
Explicit expressions
The characteristic equation of the recurrence relation for Lucas sequences
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.
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
:
:
.
Properties
Generating functions
The ordinary
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
s are
:
:
Pell equations
When
, the Lucas sequences
and
satisfy certain
Pell equations:
:
:
:
Relations between sequences with different parameters
*For any number ''c'', the sequences
and
with
::
::
:have the same discriminant as
and
:
::
*For any number ''c'', we also have
::
::
Other relations
The terms of Lucas sequences satisfy relations that are generalizations of those between
Fibonacci numbers
and
Lucas numbers
. For example:
:
Divisibility properties
Among the consequences is that
is a multiple of
, i.e., the sequence
is a
divisibility sequence. This implies, in particular, 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''.
Moreover, if
, then
is a strong divisibility sequence.
Other divisibility properties are as follows:
* If ''n'' / ''m'' is odd, then
divides
.
* Let ''N'' be an integer relatively prime to 2''Q''. If the smallest positive integer ''r'' for which ''N'' divides
exists, then the set of ''n'' for which ''N'' divides
is exactly the set of multiples of ''r''.
* If ''P'' and ''Q'' are even, then
are always even except
.
* If ''P'' is even and ''Q'' is odd, then the parity of
is the same as ''n'' and
is always even.
* If ''P'' is odd and ''Q'' is even, then
are always odd for
.
* If ''P'' and ''Q'' are odd, then
are even if and only if ''n'' is a multiple of 3.
* If ''p'' is an odd prime, then
(see
Legendre symbol).
* If ''p'' is an odd prime and divides ''P'' and ''Q'', then ''p'' divides
for every
.
* If ''p'' is an odd prime and divides ''P'' but not ''Q'', then ''p'' divides
if and only if ''n'' is even.
* If ''p'' is an odd prime and divides not ''P'' but ''Q'', then ''p'' never divides
for
.
* If ''p'' is an odd prime and divides not ''PQ'' but ''D'', then ''p'' divides
if and only if ''p'' divides ''n''.
* If ''p'' is an odd prime and does not divide ''PQD'', then ''p'' divides
, where
.
The last fact generalizes
Fermat's little theorem. These facts are used in the
Lucas–Lehmer primality test.
The converse of the last fact does not hold, as the converse of Fermat's little theorem does not hold. There exists a composite ''n'' relatively prime to ''D'' and dividing
, where
. Such a composite is called a
Lucas pseudoprime.
A
prime factor of a term in a Lucas sequence that does not divide any earlier term in the sequence is called primitive.
Carmichael's theorem states that all but finitely many of the terms in a Lucas sequence have a primitive
prime factor.
Indeed, Carmichael (1913) showed that if ''D'' is positive and ''n'' is not 1, 2 or 6, then
has a primitive prime factor. In the case ''D'' is negative, a deep result of Bilu, Hanrot, Voutier and Mignotte shows that if ''n'' > 30, then
has a primitive prime factor and determines all cases
has no primitive prime factor.
Specific names
The Lucas sequences for some values of ''P'' and ''Q'' have specific names:
: :
Fibonacci numbers
: :
Lucas numbers
: :
Pell numbers
: :
Pell–Lucas numbers
In mathematics, the Pell numbers are an infinite sequence of integers, known since ancient times, that comprise the denominators of the closest rational approximations to the square root of 2. This sequence of approximations begins , , , , ...
(companion Pell numbers)
: :
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(P,Q) for which ''P'' = 1, and ''Q' ...
s
: :
Jacobsthal–Lucas numbers 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(P,Q) for which ''P'' = 1, and '' ...
: :
Mersenne numbers 2
''n'' − 1
: : Numbers of the form 2
''n'' + 1, which include the
Fermat numbers
[
: : The square roots of the square triangular numbers.
: : Fibonacci polynomials
: : Lucas polynomials
: : ]Chebyshev polynomials
The Chebyshev polynomials are two sequences of polynomials related to the cosine and sine functions, notated as T_n(x) and U_n(x). They can be defined in several equivalent ways, one of which starts with trigonometric functions:
The Chebyshe ...
of second kind
: : Chebyshev polynomials
The Chebyshev polynomials are two sequences of polynomials related to the cosine and sine functions, notated as T_n(x) and U_n(x). They can be defined in several equivalent ways, one of which starts with trigonometric functions:
The Chebyshe ...
of first kind multiplied by 2
: : Repunit
In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for repeated unit and was coined in 1966 by Albert H. Beiler in his book ''Recreat ...
s base ''x''
: : ''xn'' + 1
Some Lucas sequences have entries in the On-Line Encyclopedia of Integer Sequences:
:
Applications
* Lucas sequences are used in probabilistic Lucas pseudoprime tests, which are part of the commonly used Baillie–PSW primality test The Baillie–PSW primality test is a probabilistic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.
The Baill ...
.
* Lucas sequences are used in some primality proof methods, including the Lucas–Lehmer–Riesel test
In mathematics, the Lucas–Lehmer–Riesel test is a primality test for numbers of the form ''N'' = ''k'' ⋅ 2''n'' − 1 (Riesel numbers) with odd ''k'' < 2''n''. The test was developed by Hans Rie ...
, and the N+1 and hybrid N-1/N+1 methods such as those in Brillhart-Lehmer-Selfridge 1975
* LUC is a public-key cryptosystem
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
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 exponentiation
Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys.
Modular ...
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.
See also
* Lucas pseudoprime
* Frobenius pseudoprime
* Somer–Lucas pseudoprime
Notes
References
*
*
*
*
*
*
*
*
*
*
*
*
*
''Lucas sequence''
at Encyclopedia of Mathematics.
*
* {{cite web, url = http://weidai.com/lucas.html, author=Wei Dai, title= Lucas Sequences in Cryptography, author-link=Wei Dai
Recurrence relations
Integer sequences