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.
Author(s): Christian J.-C. Ballot; Hugh C. Williams
Series: CMS/CAIMS Books in Mathematics
Edition: 1
Publisher: Springer Nature Switzerland
Year: 2023
Language: English
Pages: xviii; 301
City: Cham
Tags: Number Theory
List of Symbols
1 Introduction
References
2 Basic Theory of the Lucas Sequences
2.1 Definition
2.2 Most Common Identities
2.3 General Divisibility Properties
2.4 Divisibility of Un by Powers of an Odd Prime
2.5 Divisibility of Un by Powers of 2
2.6 Composite Integers Dividing U and Their Rank
2.7 Divisibility of Vn by Powers of an Odd Prime
2.8 Divisibility of Vn by Powers of 2
2.9 Composite Integers Dividing V
2.10 Euler's Criterion for Lucas Sequences
2.11 Degenerate Lucas Sequences
2.12 Divisibility by Powers of a Special Prime
References
3 Applications
3.1 Mersenne Primes
3.2 Primality Testing
3.3 Fast Computation of Un and Vn8mu(mod6mum)
3.4 Solving Quadratic and Cubic Congruences
3.5 Integer Factoring
3.6 Diophantine Equations
3.7 Cryptography
References
4 Further Properties
4.1 Connection with the Circular Functions
4.2 The Chebyshev and Dickson Polynomials
4.3 Additional Arithmetic Properties
4.4 The Lehmer Sequences
4.5 The Primitive Divisor Theorem
4.6 Moduli with a Full Set of Residues
References
5 Some Properties of Lucasnomials
5.1 Definition. Connection with q-Binomial Coefficients
5.2 Integrality
5.3 Ten Basic Identities
5.4 Combinatorial Interpretations
5.4.1 Square-and-Domino-Tiling Interpretations
5.4.2 An Interpretation Coming from q-Binomial Coefficients
5.5 Lucasnomial Catalan Numbers
5.5.1 Introduction
5.5.2 Definition and Integrality
5.5.3 Interpretation of Lucasnomial Catalan Numbers
5.5.4 The Search for Catalan-Like Triples
5.6 The p-Adic Valuation of Lucasnomials
5.6.1 A Generalized Kummer Rule
5.6.2 A Generalized Legendre Formula
5.6.3 Explicit Valuations
5.7 Lucas' Congruence
5.8 Wolstenholme's Congruence
5.9 A Word on Lehmernomials
References
6 Cubic Extensions of the Lucas Sequences
6.1 Lucas' Attempts to Generalize His Sequences
6.2 Cubic Linear Recurrences
6.3 Bell's Contribution
6.4 The Cubic Pell Equation
6.5 Williams's Sequences
6.6 Roettger's Sequences
References
7 Linear Recurrence Sequences and Further Generalizations
7.1 Linear Recurrence Sequences
7.2 Impulse Sequences
7.3 A Return to the Lehmer Sequences
7.4 Primality
References
8 Divisibility Sequences and Further Generalizations
8.1 Another Suggestion of Lucas for Generalizing His Sequences
8.2 Elliptic Divisibility Sequences
8.3 Linear Divisibility Sequences
8.4 Extended Lucas Sequences
8.5 Odd and Even Extensions of the Lucas Sequences
References
9 Prime Density of Companion Lucas Sequences
9.1 How Do We Measure the Size of a Set of Primes?
9.2 The Classic Density Theorems
9.3 Polynomial Modulo p and Cebotarev
9.4 Initial Inquiries of Sierpiński, Brauer, and Ward
9.5 The Hasse-Lagarias Method
9.6 A Heuristic View
9.7 The Laxton Group and Its Generalizations
9.7.1 The Laxton Group
9.7.2 Generalizations of the Laxton Group
9.8 The Density of Maximal Prime Divisors
9.9 Irreducible Polynomials Dividing (Xn+1)
References
10 Epilogue and Open Problems
10.1 Epilogue
10.2 Some Unsolved Problems
References
Appendix: A Short Biography of Lucas
References
Subject Index
Name Index
