Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2023 | Book

Introduction Read chapter Read first chapter

The Lucas Sequences

Theory and Applications

Authors: Christian J.-C. Ballot, Hugh C. Williams

Publisher: Springer International Publishing

Book Series : CMS/CAIMS Books in Mathematics

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

Although the Lucas sequences were known to earlier investigators such as Lagrange, Legendre and Genocchi, it is because of the enormous number and variety of results involving them, revealed by Édouard Lucas between 1876 and 1880, that they are now named after him. Since Lucas’ early work, much more has been discovered concerning these remarkable mathematical objects, and the objective of this book is to provide a much more thorough discussion of them than is available in existing monographs. In order to do this a large variety of results, currently scattered throughout the literature, are brought together. Various sections are devoted to the intrinsic arithmetic properties of these sequences, primality testing, the Lucasnomials, some associated density problems and Lucas’ problem of finding a suitable generalization of them. Furthermore, their application, not only to primality testing, but also to integer factoring, efficient solution of quadratic and cubic congruences, cryptography and Diophantine equations are briefly discussed. Also, many historical remarks are sprinkled throughout the book, and a biography of Lucas is included as an appendix.Much of the book is not intended to be overly detailed. Rather, the objective is to provide a good, elementary and clear explanation of the subject matter without too much ancillary material. Most chapters, with the exception of the second and the fourth, will address a particular theme, provide enough information for the reader to get a feel for the subject and supply references to more comprehensive results. Most of this work should be accessible to anyone with a basic knowledge of elementary number theory and abstract algebra. The book’s intended audience is number theorists, both professional and amateur, students and enthusiasts.

Table of Contents

Frontmatter
Chapter 1. Introduction
Abstract
As this is a book about number sequences, we begin by defining a number sequence to be an ordered set of numbers.
Christian J.-C. Ballot, Hugh C. Williams
Chapter 2. Basic Theory of the Lucas Sequences
Abstract
This chapter discusses the fundamental properties of Lucas sequences. Those who have worked with, or who have had an interest in, Lucas sequences will be aware of a good part of the material in the chapter, but we hope to bring about a degree of precision and completeness concerning these basic properties along with proofs. Regular, standard, degenerate, as well as general Lucas sequences are defined. Their most basic and important identities are reviewed; divisibility properties and the p-adic valuation of their terms are studied for all primes p, whether regular or special. The notion of the rank and rank exponent of a prime, the Lucas laws of appearance and repetition, the lifting-the-exponent lemma, as well as the Euler criterion for Lucas sequences are encountered along the way. We did not seek the most concise exposition, but rather one that brings some insight and is strewn with remarks. In fact, we often give several proofs of the same result, providing elementary ones always, but occasionally also proofs that use basic algebraic number-theoretic concepts. Of course, these results are of use, in particular, in all chapters of the book.
Christian J.-C. Ballot, Hugh C. Williams
Chapter 3. Applications
Abstract
The purpose of this chapter is to review several diverse applications of the Lucas functions, particularly in the area of computational number theory. We will begin with a largely historical description of the Mersenne primes and then examine how the Lucas functions have been applied to the problem of primality testing. As this requires that we be able to compute Un and/or Vn for large values of n, we provide in Sect. 3.3 some algorithms by which this can be done. We next describe several subjects, such as solving congruences, integer factorization, Diophantine equations, and cryptography in which the Lucas functions have been applied.
Christian J.-C. Ballot, Hugh C. Williams
Chapter 4. Some Further Properties of the Lucas Sequences
Abstract
This chapter is a compilation of some miscellaneous results involving the Lucas sequences. We begin with a discussion of the relationship of the Lucas sequences to the sine and cosineCosine functions and then describe the periodicity properties of U and V  modulo an integer m. This is followed by a section devoted to the relationship of the Lucas sequences to the Chebyshev and the Dickson polynomials. We then review some additional arithmetic properties of the Lucas sequences that are not covered in Chap. 2 and establish what Lucas called his fundamental theorem. Subsequently, we provide some insights on the factorization of the terms of U. Next, we describe Lehmer’s extension of Lucas’ sequences and examine some of their properties. The following section makes use of our earlier factorization results to prove an old theorem of Carmichael on primitive divisors of (Un) and of the Lehmer sequences. We conclude with a brief treatment of the topic of when the Lucas sequence U can contain a complete set of residues modulo an integer m.
Christian J.-C. Ballot, Hugh C. Williams
Chapter 5. Some Properties of Lucasnomials
Abstract
Lucasnomials, or Lucasnomial coefficients, are a generalization of the usual binomial coefficients \(\binom {n}{k}\), when n and k are integers. Lucasnomials \(\binom {n}{k}_U\) are associated with every nondegenerate fundamental Lucas sequence U. Their definition includes ordinary binomial coefficients which we get when U = U(2, 1), i.e., if U is the sequence of natural numbers. Remarkably, various arithmetic properties of binomial coefficients hold in a more general form in this context.
Christian J.-C. Ballot, Hugh C. Williams
Chapter 6. Cubic Extensions of the Lucas Sequences
Abstract
This is the first of three chapters devoted to the question of how to generalize the Lucas sequences. We begin with a detailed discussion of Lucas’s thoughts concerning this problem, one which he regarded as being of very great importance. This is followed by some historical commentary. As LucasLucas, É. regarded linear recurrences as being key to providing an answer to this question, we first discuss the possible application of cubic linear recurrences to it. We then move on to several proposals for solutions, including Bell’s ideas and Williams’s suggestions and concluding with Roettger’s remarkable sequences.
Christian J.-C. Ballot, Hugh C. Williams
Chapter 7. Linear Recurrence Sequences and Further Generalizations
Abstract
In this chapter we examine the problem of generalizing Lucas’ sequences from the perspective of linear recurrences. We first derive a number of features of such recurrences, culminating in a generalization of Lucas’ law of appearance. We follow this with an investigation of the properties of impulse sequences, particular cases of the more general linear recurrence. It turns out that the impulse sequences have many characteristics in common with the Lucas sequences. We next turn to the problem of generalizing the Lehmer sequencesLehmer sequences and how they may be used to produce necessary and sufficient tests of primality for numbers N of the form N = Apn + γ, where p is an odd prime, 2∣A, \(p\nmid A\), γ ∈{1, −1} and A < pn.
Christian J.-C. Ballot, Hugh C. Williams
Chapter 8. Divisibility Sequences and Further Generalizations
Abstract
In this chapter we consider, starting with some early observations of Lucas, the problem of generalizing the Lucas sequences (Un) and (Vn), by making use of certain divisibility sequences. We provide a brief discussion of Ward’s elliptic divisibility sequence and its remarkable attributes. This is followed by a discussion of the properties of divisibility sequences which satisfy linear recurrences. We use these observations and the basic properties of the Lucas sequences to derive some extended Lucas sequences and list their properties in certain special cases. These sequences have features very much in common with those of (Un) and (Vn). Finally, we discuss odd and even extensions of the Lucas sequences.
Christian J.-C. Ballot, Hugh C. Williams
Chapter 9. Prime Density of Companion Lucas Sequences
Abstract
It seems to me that the poet has to perceive that which others do not perceive, to look deeper than others look. And the mathematician must do the same thing (Sofia Kovalevskaya)
Christian J.-C. Ballot, Hugh C. Williams
Chapter 10. Epilogue and Open Problems
Abstract
We conclude with a brief review of the topics introduced in this book and Lucas’ connection to them. This is followed by an eclectic assortment of unsolved problems.
Christian J.-C. Ballot, Hugh C. Williams
Backmatter
Metadata
Title
The Lucas Sequences
Authors
Christian J.-C. Ballot
Hugh C. Williams
Copyright Year
2023
Electronic ISBN
978-3-031-37238-4
Print ISBN
978-3-031-37237-7
DOI
https://doi.org/10.1007/978-3-031-37238-4

Premium Partner

    Image Credits