词条 | Lucas sequence | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
释义 |
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 numbers, and a superset of Fermat numbers. Lucas sequences are named after the French mathematician Édouard Lucas. Recurrence relationsGiven 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 relations: and It is not hard to show that for , ExamplesInitial terms of Lucas sequences Un(P,Q) and Vn(P,Q) are given in the table: Explicit expressionsThe 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 rootsWhen , 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 rootThe case occurs exactly when for some integer S so that . In this case one easily finds that . PropertiesGenerating functionsThe ordinary generating functions are Sequences with the same discriminantIf the Lucas sequences and have discriminant , then the sequences based on and where have the same discriminant: . Pell equationsWhen , the Lucas sequences and satisfy certain Pell equations: Other relationsThe terms of Lucas sequences satisfy relations that are generalizations of those between Fibonacci numbers and Lucas numbers . For example: 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:[1]
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 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.[2] 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[3] shows that if n > 30, then has a primitive prime factor and determines all cases has no primitive prime factor. Specific namesThe Lucas sequences for some values of P and Q have specific names: {{math|Un(1,−1)}} : Fibonacci numbers {{math|Vn(1,−1)}} : Lucas numbers {{math|Un(2,−1)}} : Pell numbers {{math|Vn(2,−1)}} : Pell-Lucas numbers (companion Pell numbers) {{math|Un(1,−2)}} : Jacobsthal numbers {{math|Vn(1,−2)}} : Jacobsthal-Lucas numbers {{math|Un(3, 2)}} : Mersenne numbers 2n − 1 {{math|Vn(3, 2)}} : Numbers of the form 2n + 1, which include the Fermat numbers {{harv|Yabuta|2001}}. {{math|Un(6, 1)}} : The square roots of the square triangular numbers. {{math|Un(x,−1)}} : Fibonacci polynomials {{math|Vn(x,−1)}} : Lucas polynomials {{math|Un(2x, 1)}} : Chebyshev polynomials of second kind {{math|Vn(2x, 1)}} : Chebyshev polynomials of first kind multiplied by 2 {{math|Un(x+1, x)}} : Repunits base x {{math|Vn(x+1, x)}} : xn + 1 Some Lucas sequences have entries in the On-Line Encyclopedia of Integer Sequences:
Applications
See also
Notes1. ^For such relations and divisibility properties, see {{harv|Carmichael|1913}}, {{harv|Lehmer|1930}} or {{harv|Ribenboim|1996|loc=2.IV}}. 2. ^{{cite journal |last1=Yabuta |first1=M |title=A simple proof of Carmichael's theorem on primitive divisors |journal=Fibonacci Quarterly |date=2001 |volume=39 |pages=439–443 |url=http://www.fq.math.ca/Scanned/39-5/yabuta.pdf |accessdate=4 October 2018}} 3. ^{{cite journal | first1=Yuri | last1=Bilu | first2=Guillaume | last2=Hanrot | first3=Paul M. | last3=Voutier | first4=Maurice | last4=Mignotte | title=Existence of primitive divisors of Lucas and Lehmer numbers | journal = J. Reine Angew. Math. | year=2001 | volume=539 |pages= 75–122 | mr=1863855 | doi=10.1515/crll.2001.080}} 4. ^{{ cite journal|author=John Brillhart|author2=Derrick Henry Lehmer|author3=John Selfridge|title=New Primality Criteria and Factorizations of 2m ± 1|journal=Mathematics of Computation |volume=29|number=130|date=April 1975|pages=620–647|jstor=2005583|doi=10.1090/S0025-5718-1975-0384673-1}} 5. ^{{cite journal |author1=P. J. Smith |author2=M. J. J. Lennon |title=LUC: A new public key system |journal=Proceedings of the Ninth IFIP Int. Symp. on Computer Security |year=1993 |pages=103–117 |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.1835}} 6. ^{{cite journal |author1=D. Bleichenbacher |author2=W. Bosma |author3=A. K. Lenstra |title=Some Remarks on Lucas-Based Cryptosystems |journal=Lecture Notes in Computer Science |volume=963 |year=1995 |pages=386–396 |doi=10.1007/3-540-44750-4_31 |url=http://www.math.ru.nl/~bosma/pubs/CRYPTO95.pdf}} References
| last = Carmichael | first = R. D. | author-link = Robert Daniel Carmichael | doi = 10.2307/1967797 | issue = 1/4 | journal = Annals of Mathematics | pages = 30–70 | title = On the numerical factors of the arithmetic forms αn±βn | volume = 15 | year = 1913 | jstor = 1967797 |ref=harv}}
|title=An extended theory of Lucas' functions |journal=Annals of Mathematics |year=1930 |volume=31 | number=3 |jstor=1968235 |pages=419–448 |bibcode=1930AnMat..31..419L | doi=10.2307/1968235 |ref=harv}}
|title=Prime divisors of second order recurring sequences |journal = Duke Math. J. | year=1954 | volume=21 | number=4 |pages=607–614 | mr=0064073 |doi=10.1215/S0012-7094-54-02163-8 |ref=harv}}
|title=The divisibility properties of primary Lucas Recurrences with respect to primes |year=1980 | journal=Fibonacci Quarterly | pages=316 | volume=18 | url=http://www.fq.math.ca/Scanned/18-4/somer.pdf |ref=harv}}
|journal=Pac. J. Math. | title=The set of primes dividing Lucas Numbers has density 2/3 |year=1985 | volume=118 | number=2 | pages=449–461 | mr=789184 | doi=10.2140/pjm.1985.118.449 |ref=harv}}
|title=The square terms in Lucas Sequences | journal=J. Number Theory |year=1996 | volume=58 | number=1 | pages=104–123 | doi=10.1006/jnth.1996.0068 |ref=harv}}
|title=Perfect Fibonacci and Lucas numbers | year=2000 |journal = Rend. Circ Matem. Palermo |doi=10.1007/BF02904236 | volume=49 | number=2 | pages=313–318 |ref=harv}}
| last = Yabuta | first = M. | journal = Fibonacci Quarterly | pages = 439–443 | title = A simple proof of Carmichael's theorem on primitive divisors | url = http://www.fq.math.ca/Scanned/39-5/yabuta.pdf | volume = 39 | year = 2001 | ref=harv}}
| title = Proofs that Really Count: The Art of Combinatorial Proof | first1 = Arthur T. | last1 = Benjamin | author1-link = Arthur T. Benjamin | first2 = Jennifer J. | last2 = Quinn | author2-link = Jennifer Quinn | page = 35 | publisher = Mathematical Association of America | series = Dolciani Mathematical Expositions | volume = 27 | year = 2003 | isbn = 978-0-88385-333-7 | ref=harv}}
2 : Recurrence relations|Integer sequences |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。