Editing Lucas sequence

{{Short description|Certain constant-recursive integer sequences}}
{{distinguish|text=the sequence of [[Lucas number]]s, which is a particular Lucas sequence}}

In [[mathematics]], the '''Lucas sequences''' <math>U_n(P,Q)</math> and <math>V_n(P, Q)</math> are certain [[constant-recursive sequence|constant-recursive]] [[integer sequence]]s that satisfy the [[recurrence relation]]

: <math>x_n = P \cdot x_{n - 1} - Q \cdot x_{n - 2}</math>

where <math>P</math> and <math>Q</math> are fixed [[integer]]s. Any sequence satisfying this recurrence relation can be represented as a [[linear combination]] of the Lucas sequences <math>U_n(P, Q)</math> and <math>V_n(P, Q).</math>

More generally, Lucas sequences <math>U_n(P, Q)</math> and <math>V_n(P, Q)</math> represent sequences of [[polynomial]]s in <math>P</math> and <math>Q</math> with integer [[coefficient]]s.

Famous examples of Lucas sequences include the [[Fibonacci number]]s, [[Mersenne number]]s, [[Pell number]]s, [[Lucas number]]s, [[Jacobsthal number]]s, and a superset of [[Fermat number]]s (see below). Lucas sequences are named after the [[France|French]] mathematician [[Édouard Lucas]].

== Recurrence relations ==

Given two integer parameters <math>P</math> and <math>Q</math>, the Lucas sequences of the first kind <math>U_n(P,Q)</math> and of the second kind <math>V_n(P,Q)</math> are defined by the [[recurrence relation]]s:

:<math>\begin{align}
U_0(P,Q)&=0, \\
U_1(P,Q)&=1, \\
U_n(P,Q)&=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q) \mbox{  for }n>1,
\end{align}</math>

and

:<math>\begin{align}
V_0(P,Q)&=2, \\
V_1(P,Q)&=P, \\
V_n(P,Q)&=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q) \mbox{  for }n>1.
\end{align}</math>

It is not hard to show  that for <math>n>0</math>,

:<math>\begin{align}
U_n(P,Q)&=\frac{P\cdot U_{n-1}(P,Q) + V_{n-1}(P,Q)}{2},  \\
V_n(P,Q)&=\frac{(P^2-4Q)\cdot U_{n-1}(P,Q)+P\cdot V_{n-1}(P,Q)}{2}.  
\end{align}</math>

The above relations can be stated in [[matrix (mathematics)|matrix]] form as follows:
: <math>\begin{bmatrix} U_n(P,Q)\\ U_{n+1}(P,Q)\end{bmatrix} = \begin{bmatrix} 0 & 1\\ -Q & P\end{bmatrix}\cdot \begin{bmatrix} U_{n-1}(P,Q)\\ U_n(P,Q)\end{bmatrix},</math>
<br>
: <math>\begin{bmatrix} V_n(P,Q)\\ V_{n+1}(P,Q)\end{bmatrix} = \begin{bmatrix} 0 & 1\\ -Q & P\end{bmatrix}\cdot \begin{bmatrix} V_{n-1}(P,Q)\\ V_n(P,Q)\end{bmatrix},</math>
<br>
: <math>\begin{bmatrix} U_n(P,Q)\\ V_n(P,Q)\end{bmatrix} = \begin{bmatrix} P/2 & 1/2\\ (P^2-4Q)/2 & P/2\end{bmatrix}\cdot \begin{bmatrix} U_{n-1}(P,Q)\\ V_{n-1}(P,Q)\end{bmatrix}.</math>

== Examples ==

Initial terms of Lucas sequences <math>U_n(P,Q)</math> and <math>V_n(P,Q)</math> are given in the table:
:<math>
\begin{array}{r|l|l}
n & U_n(P,Q) & V_n(P,Q)
\\
\hline
0 & 0 & 2
\\
1 & 1 & P
\\
2 & P & {P}^{2}-2Q
\\
3 & {P}^{2}-Q & {P}^{3}-3PQ
\\
4 & {P}^{3}-2PQ & {P}^{4}-4{P}^{2}Q+2{Q}^{2}
\\
5 & {P}^{4}-3{P}^{2}Q+{Q}^{2} & {P}^{5}-5{P}^{3}Q+5P{Q}^{2}
\\
6 & {P}^{5}-4{P}^{3}Q+3P{Q}^{2} & {P}^{6}-6{P}^{4}Q+9{P}^{2}{Q}^{2}-2{Q}^{3}
\end{array}
</math>

== Explicit expressions ==

The characteristic equation of the recurrence relation for Lucas sequences <math>U_n(P,Q)</math> and <math>V_n(P,Q)</math> is:
:<math>x^2 - Px + Q=0 \,</math>
<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.-->
It has the [[discriminant]] <math>D = P^2 - 4Q</math> and the [[root of a polynomial|roots]]:
:<math>a = \frac{P+\sqrt{D}}2\quad\text{and}\quad b = \frac{P-\sqrt{D}}2. \,</math>

Thus:
:<math>a + b = P\, ,</math>
:<math>a b = \frac{1}{4}(P^2 - D) = Q\, ,</math>
:<math>a - b = \sqrt{D}\, .</math>

Note that the sequence <math>a^n</math> and the sequence <math>b^n</math> also satisfy the recurrence relation. However these might not be integer sequences.

=== Distinct roots ===
When <math>D\ne 0</math>, ''a'' and ''b'' are distinct and one quickly verifies that

:<math>a^n = \frac{V_n + U_n \sqrt{D}}{2}</math>

:<math>b^n = \frac{V_n - U_n \sqrt{D}}{2}.</math>

It follows that the terms of Lucas sequences can be expressed in terms of ''a'' and ''b'' as follows

:<math>U_n = \frac{a^n-b^n}{a-b} = \frac{a^n-b^n}{ \sqrt{D}}</math>

:<math>V_n = a^n+b^n \,</math>
<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.-->

=== Repeated root ===

The case <math> D=0 </math> occurs exactly when <math> P=2S \text{ and }Q=S^2</math> for some integer ''S'' so that <math>a=b=S</math>. In this case one easily finds that

:<math>U_n(P,Q)=U_n(2S,S^2) = nS^{n-1}\,</math>

:<math>V_n(P,Q)=V_n(2S,S^2)=2S^n.\,</math>

== Properties ==

=== Generating functions ===

The ordinary [[generating function]]s are
:<math>
\sum_{n\ge 0} U_n(P,Q)z^n = \frac{z}{1-Pz+Qz^2};
</math>
:<math>
\sum_{n\ge 0} V_n(P,Q)z^n = \frac{2-Pz}{1-Pz+Qz^2}.
</math>

=== Pell equations ===

When <math>Q=\pm 1</math>, the Lucas sequences <math>U_n(P, Q)</math> and <math>V_n(P, Q)</math> satisfy certain [[Pell equation]]s:
:<math>V_n(P,1)^2 - D\cdot U_n(P,1)^2 = 4,</math>
:<math>V_n(P,-1)^2 - D\cdot U_n(P,-1)^2 = 4(-1)^n.</math>

=== Relations between sequences with different parameters ===

*For any number ''c'', the sequences <math>U_n(P', Q')</math> and <math>V_n(P', Q')</math> with
::<math> P' = P + 2c  </math>
::<math> Q' = cP + Q + c^2  </math>
:have the same discriminant as <math>U_n(P, Q)</math> and <math>V_n(P, Q)</math>: 
:: <math>P'^2 - 4Q' = (P+2c)^2 - 4(cP + Q + c^2) = P^2 - 4Q = D.</math>

*For any number ''c'', we also have
:: <math>U_n(cP,c^2Q) = c^{n-1}\cdot U_n(P,Q),</math>
:: <math>V_n(cP,c^2Q) = c^n\cdot V_n(P,Q).</math>

=== Other relations ===

The terms of Lucas sequences satisfy relations that are generalizations of those between [[Fibonacci number]]s <math>F_n=U_n(1,-1)</math> and [[Lucas number]]s <math>L_n=V_n(1,-1)</math>. For example:
:<math>
\begin{array}{r|l}
\text{General case} & (P,Q) = (1,-1), D = P^2 - 4Q = 5
\\
\hline
D U_n = {V_{n+1} - Q V_{n-1}}=2V_{n+1}-P V_n  & 5F_n = {L_{n+1} + L_{n-1}}=2L_{n+1} - L_{n} 
\\
V_n = U_{n+1} - Q U_{n-1}=2U_{n+1}-PU_n  & L_n = F_{n+1} + F_{n-1}=2F_{n+1}-F_n 
\\
U_{m+n} = U_n U_{m+1} - Q U_m U_{n-1} = U_mV_n-Q^nU_{m-n} & F_{m+n} = F_n F_{m+1} + F_m F_{n-1} =F_mL_n-(-1)^nF_{m-n}
\\
U_{2n} = U_n (U_{n+1} - QU_{n-1}) = U_n V_n  & F_{2n} = F_n (F_{n+1} + F_{n-1}) = F_n L_n 
\\
U_{2n+1} = U_{n+1}^2 - Q U_n^2 & F_{2n+1} = F_{n+1}^2 + F_n^2
\\
V_{m+n} = V_m V_n - Q^n V_{m-n} = D U_m U_n + Q^n V_{m-n} & L_{m+n} = L_m L_n - (-1)^n L_{m-n} = 5 F_m F_n + (-1)^n L_{m-n} 
\\
V_{2n} = V_n^2 - 2Q^n = D U_n^2 + 2Q^n & L_{2n} = L_n^2 - 2(-1)^n = 5 F_n^2 + 2(-1)^n
\\
U_{m+n} = \frac{U_mV_n+U_nV_m}{2} & F_{m+n} = \frac{F_mL_n+F_nL_m}{2} 
\\
V_{m+n}=\frac{V_mV_n+DU_mU_n}{2} & L_{m+n}=\frac{L_mL_n+5F_mF_n}{2} 
\\
V_n^2-DU_n^2=4Q^n & L_n^2-5F_n^2=4(-1)^n 
\\
U_n^2-U_{n-1}U_{n+1}=Q^{n-1} & F_n^2-F_{n-1}F_{n+1}=(-1)^{n-1} 
\\
V_n^2-V_{n-1}V_{n+1}=DQ^{n-1} & L_n^2-L_{n-1}L_{n+1}=5(-1)^{n-1} 
\\
2^{n-1}U_n={n \choose 1}P^{n-1}+{n \choose 3}P^{n-3}D+\cdots & 2^{n-1}F_n={n \choose 1}+5{n \choose 3}+\cdots
\\
2^{n-1}V_n=P^n+{n \choose 2}P^{n-2}D+{n \choose 4}P^{n-4}D^2+\cdots & 2^{n-1}L_n=1+5{n \choose 2}+5^2{n \choose 4}+\cdots
\end{array}
</math>

=== Divisibility properties ===

Among the consequences is that <math>U_{km}(P,Q)</math> is a multiple of <math>U_m(P,Q)</math>, i.e., the sequence <math>(U_m(P,Q))_{m\ge1}</math>
is a [[divisibility sequence]]. This implies, in particular, that <math>U_n(P,Q)</math> can be [[prime number|prime]] only when ''n'' is prime.
Another consequence is an analog of [[exponentiation by squaring]] that allows fast computation of <math>U_n(P,Q)</math> for large values of ''n''. 
Moreover, if <math>\gcd(P,Q)=1</math>, then <math>(U_m(P,Q))_{m\ge1}</math> is a [[divisibility sequence|strong divisibility sequence]].

Other divisibility properties are as follows:<ref>For such relations and divisibility properties, see {{harv|Carmichael|1913}}, {{harv|Lehmer|1930}} or {{harv|Ribenboim|1996|loc=2.IV}}.</ref>
* If ''n'' is an [[parity (mathematics)|odd]] multiple of ''m'', then <math>V_m</math> divides <math>V_n</math>.
* Let ''N'' be an integer [[relatively prime]] to 2''Q''.  If the smallest positive integer ''r'' for which ''N'' divides <math>U_r</math> exists, then the set of ''n'' for which ''N'' divides <math>U_n</math> is exactly the set of multiples of ''r''.
* If ''P'' and ''Q'' are [[parity (mathematics)|even]], then <math>U_n, V_n</math> are always even except <math>U_1</math>.
* If ''P'' is odd and ''Q'' is even, then <math>U_n, V_n</math> are always odd for every <math>n > 0</math>.
* If ''P'' is even and ''Q'' is odd, then the [[parity (mathematics)|parity]] of <math>U_n</math> is the same as ''n'' and <math>V_n</math> is always even.
* If ''P'' and ''Q'' are odd, then <math>U_n, V_n</math> are even if and only if ''n'' is a multiple of 3.
* If ''p'' is an odd prime, then <math>U_p\equiv\left(\tfrac{D}{p}\right), V_p\equiv P\pmod{p}</math> (see [[Legendre symbol]]).
* If ''p'' is an odd prime which divides ''P'' and ''Q'', then ''p'' divides <math>U_n</math> for every <math>n>1</math>.
* If ''p'' is an odd prime which divides ''P'' but not ''Q'', then ''p'' divides <math>U_n</math> if and only if ''n'' is even.
* If ''p'' is an odd prime which divides ''Q''  but not ''P'', then ''p'' never divides <math>U_n</math> for any <math>n > 0</math>.
* If ''p'' is an odd prime which divides ''D'' but not ''PQ'', then ''p'' divides <math>U_n</math> if and only if ''p'' divides ''n''.
* If ''p'' is an odd prime which does not divide ''PQD'', then ''p'' divides <math>U_l</math>, where <math>l=p-\left(\tfrac{D}{p}\right)</math>.

The last fact generalizes [[Fermat's little theorem]].  These facts are used in the [[Lucas–Lehmer primality test]].
Like Fermat's little theorem, the [[converse (logic)|converse]] of the last fact holds often, but not always; there exist [[composite number]]s ''n'' relatively prime to ''D'' and dividing <math>U_l</math>, where <math>l=n-\left(\tfrac{D}{n}\right)</math>.  Such composite numbers are called [[Lucas pseudoprime]]s.

A [[prime factor]] of a term in a Lucas sequence which 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.<ref name=Yabuta>{{cite journal |last1=Yabuta |first1=M |title=A simple proof of Carmichael's theorem on primitive divisors |journal=Fibonacci Quarterly |date=2001 |volume=39 |issue=5 |pages=439–443 |doi=10.1080/00150517.2001.12428701 |url=http://www.fq.math.ca/Scanned/39-5/yabuta.pdf |access-date=4 October 2018}}</ref>  Indeed, [[Robert Daniel Carmichael|Carmichael]] (1913) showed that if ''D'' is positive and ''n'' is not 1, 2 or 6, then <math>U_n</math> has a primitive prime factor.  In the case ''D'' is negative, a deep result of Bilu, Hanrot, Voutier and Mignotte<ref>{{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=2001 | issue=539 | pages=75–122 | mr=1863855 | doi=10.1515/crll.2001.080 | s2cid=122969549 | url=https://hal.inria.fr/inria-00072867/file/RR-3792.pdf }}
</ref> shows that if ''n'' > 30, then <math>U_n</math> has a primitive prime factor and determines all cases <math>U_n</math> has no primitive prime factor.

== Specific names ==

The Lucas sequences for some values of ''P'' and ''Q'' have specific names:

:{{math|''U<sub>n</sub>''(1, −1)}} : [[Fibonacci number]]s
:{{math|''V<sub>n</sub>''(1, −1)}} : [[Lucas number]]s
:{{math|''U<sub>n</sub>''(2, −1)}} : [[Pell number]]s
:{{math|''V<sub>n</sub>''(2, −1)}} : [[Pell–Lucas numbers]] (companion Pell numbers)
:{{math|''U<sub>n</sub>''(1, −2)}} : [[Jacobsthal number]]s
:{{math|''V<sub>n</sub>''(1, −2)}} : [[Jacobsthal–Lucas numbers]]
:{{math|''U<sub>n</sub>''(3, 2)}} : [[Mersenne number]]s 2<sup>''n''</sup>&nbsp;−&thinsp;1
:{{math|''V<sub>n</sub>''(3, 2)}} : Numbers of the form 2<sup>''n''</sup>&nbsp;+&thinsp;1, which include the [[Fermat number]]s<ref name=Yabuta/>
:{{math|''U<sub>n</sub>''(6,&thinsp;1)}} : The square roots of the [[square triangular number]]s.
:{{math|''U<sub>n</sub>''(''x'', −1)}} : [[Fibonacci polynomials]]
:{{math|''V<sub>n</sub>''(''x'', −1)}} : [[Lucas polynomials]]
:{{math|''U<sub>n</sub>''(2''x'',&thinsp;1)}} : [[Chebyshev polynomials]] of second kind
:{{math|''V<sub>n</sub>''(2''x'',&thinsp;1)}} : [[Chebyshev polynomials]] of first kind multiplied by 2
:{{math|''U<sub>n</sub>''(''x''+1, ''x'')}} : [[Repunit]]s in base ''x''
:{{math|''V<sub>n</sub>''(''x''+1, ''x'')}} : ''x<sup>n</sup>''&nbsp;+&thinsp;1

Some Lucas sequences have entries in the [[On-Line Encyclopedia of Integer Sequences]]:

:{|class="wikitable" style="background: #fff"
|-
!<math>P\,</math>!!<math>Q\, </math>!!<math>U_n(P,Q)\, </math>!! <math>V_n(P,Q)\,</math>
|- 
| −1 || 3 || {{OEIS2C|A214733}}
|-
| 1 || −1 || {{OEIS2C|A000045}} || {{OEIS2C|A000032}}
|-
| 1 || 1 || {{OEIS2C|A128834}} || {{OEIS2C|A087204}}
|-
| 1 || 2 || {{OEIS2C|A107920}} || {{OEIS2C|A002249}}
|-
| 2 || −1 || {{OEIS2C|A000129}} || {{OEIS2C|A002203}}
|-
| 2 || 1 || {{OEIS2C|A001477}} || {{OEIS2C|A007395}}
|-
| 2 || 2 || {{OEIS2C|A009545}} 
|-
| 2 || 3 || {{OEIS2C|A088137}}
|-
| 2 || 4 || {{OEIS2C|A088138}}
|-
| 2 || 5 || {{OEIS2C|A045873}}
|-
| 3 || −5 || {{OEIS2C|A015523}} || {{OEIS2C|A072263}}
|-
| 3 || −4 || {{OEIS2C|A015521}} || {{OEIS2C|A201455}}
|-
| 3 || −3 || {{OEIS2C|A030195}} || {{OEIS2C|A172012}}
|-
| 3 || −2 || {{OEIS2C|A007482}} || {{OEIS2C|A206776}}
|-
| 3 || −1 || {{OEIS2C|A006190}} || {{OEIS2C|A006497}}
|-
| 3 || 1 || {{OEIS2C|A001906}} || {{OEIS2C|A005248}}
|-
| 3 || 2 || {{OEIS2C|A000225}} || {{OEIS2C|A000051}}
|-
| 3 || 5 || {{OEIS2C|A190959}}
|-
| 4 || −3 || {{OEIS2C|A015530}} || {{OEIS2C|A080042}}
|-
| 4 || −2 || {{OEIS2C|A090017}}
|-
| 4 || −1 || {{OEIS2C|A001076}} || {{OEIS2C|A014448}}
|-
| 4 || 1 || {{OEIS2C|A001353}} || {{OEIS2C|A003500}}
|-
| 4 || 2 || {{OEIS2C|A007070}}  || {{OEIS2C|A056236}}
|-
| 4 || 3 || {{OEIS2C|A003462}} || {{OEIS2C|A034472}}
|-
| 4 || 4 || {{OEIS2C|A001787}}
|-
| 5 || −3 || {{OEIS2C|A015536}}
|-
| 5 || −2 || {{OEIS2C|A015535}}
|-
| 5 || −1 || {{OEIS2C|A052918}} || {{OEIS2C|A087130}}
|-
| 5 || 1 || {{OEIS2C|A004254}} || {{OEIS2C|A003501}}
|-
| 5 || 4 ||{{OEIS2C|A002450}} || {{OEIS2C|A052539}}
|-
| 6 || 1 ||{{OEIS2C|A001109}} || {{OEIS2C|A003499}}
|}

==Applications==
* Lucas sequences are used in probabilistic [[Lucas pseudoprime]] tests, which are part of the commonly used [[Baillie–PSW primality test]].
* Lucas sequences are used in some primality proof methods, including the [[Lucas–Lehmer–Riesel test]], and the N+1 and hybrid N−1/N+1 methods such as those in Brillhart-Lehmer-Selfridge 1975.<ref name="BLS75">{{ cite journal|author=John Brillhart|author2=Derrick Henry Lehmer|author3-link=John Selfridge|author3=John Selfridge|title=New Primality Criteria and Factorizations of 2<sup>m</sup> ± 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|author-link=John Brillhart|author2-link=Derrick Henry Lehmer|doi-access=free}}</ref>
* LUC is a [[public-key cryptosystem]] based on Lucas sequences<ref>{{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 |citeseerx=10.1.1.32.1835 }}</ref> that implements the analogs of [[ElGamal]] (LUCELG), [[Diffie–Hellman]] (LUCDIF), and [[RSA (algorithm)|RSA]] (LUCRSA). The encryption of the message in LUC is computed as a term of certain Lucas sequence, instead of using [[modular exponentiation]] as in RSA or Diffie–Hellman. However, a paper by Bleichenbacher et al.<ref>{{cite book |author1=D. Bleichenbacher |author2=W. Bosma |author3=A. K. Lenstra |title=Advances in Cryptology — CRYPT0' 95 |chapter=Some Remarks on Lucas-Based Cryptosystems |series=Lecture Notes in Computer Science |volume=963 |year=1995 |pages=386–396 |doi=10.1007/3-540-44750-4_31 |isbn=978-3-540-60221-7 |chapter-url=http://www.math.ru.nl/~bosma/pubs/CRYPTO95.pdf|doi-access=free }}</ref> 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.

== Software ==
Sagemath implements <math>U_n</math> and <math>V_n</math> as  <code>lucas_number1()</code> and <code>lucas_number2()</code>, respectively.<ref>{{Cite web |title=Combinatorial Functions - Combinatorics |url=https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/combinat.html |access-date=2023-07-13 |website=doc.sagemath.org}}</ref>

==See also==
* [[Lucas pseudoprime]]
* [[Frobenius pseudoprime]]
* [[Somer–Lucas pseudoprime]]

==Notes==
{{reflist}}

==References==
<!--These appear to be in chronological order, please maintain.-->
*{{citation
 | 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 α<sup>''n''</sup>±β<sup>''n''</sup>
 | volume = 15
 | year = 1913
 | jstor = 1967797 }}
* {{cite journal| first1=D. H. | last1=Lehmer
|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
}}
* {{cite journal| first1=Morgan | last1=Ward
|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
| hdl=10338.dmlcz/137477
| hdl-access=free}}
* {{cite journal|first1=Lawrence | last1=Somer
|title=The divisibility properties of primary Lucas Recurrences with respect to primes
|year=1980 | journal=Fibonacci Quarterly | pages=316–334 | volume=18 | issue=4
| doi=10.1080/00150517.1980.12430140
| url=http://www.fq.math.ca/Scanned/18-4/somer.pdf
}}
* {{cite journal|first1=J. C. | last1=Lagarias
|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
| citeseerx=10.1.1.174.660 }}
* {{cite book | title=Prime Numbers and Computer Methods for Factorization | edition=2nd | author=Hans Riesel | author-link=Hans Riesel | series=Progress in Mathematics | volume=126 | publisher=Birkhäuser | year=1994 | isbn=0-8176-3743-5 | pages=107–121 }}
* {{ cite journal|first1=Paulo | last1=Ribenboim | first2=Wayne L. |last2=McDaniel
|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
| doi-access=free }}
* {{cite journal | first1=M. | last1=Joye | first2=J.-J. | last2=Quisquater | title=Efficient computation of full Lucas sequences | journal=Electronics Letters | year=1996 | volume=32 | number=6 | pages=537–538 | url=http://www.joye.site88.net/papers/JQ96lucas.pdf | doi=10.1049/el:19960359 | bibcode=1996ElL....32..537J | url-status=dead | archive-url=https://web.archive.org/web/20150202074230/http://www.joye.site88.net/papers/JQ96lucas.pdf | archive-date=2015-02-02 }}
* {{cite book |first= Paulo |last= Ribenboim |title=The New Book of Prime Number Records | publisher=[[Springer-Verlag]], New York | edition=eBook | isbn=978-1-4612-0759-7 | doi=10.1007/978-1-4612-0759-7 | year=1996}}
* {{cite book | first=Paulo | last=Ribenboim | author-link=Paulo Ribenboim | year=2000 | title=My Numbers, My Friends: Popular Lectures on Number Theory | publisher=[[Springer-Verlag]] | location=New York | isbn=0-387-98911-0 | pages=1–50 }}
* {{cite journal | first1=Florian | last1=Luca
|title=Perfect Fibonacci and Lucas numbers | year=2000
|journal = Rend. Circ Matem. Palermo 
|doi=10.1007/BF02904236 | volume=49 | number=2 | pages=313–318
| s2cid=121789033
}}
* {{cite journal
 | 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
 | issue = 5
 | doi = 10.1080/00150517.2001.12428701
 }}
*{{cite book
 | 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 = [https://archive.org/details/proofsthatreally0000benj/page/35 35]
 | publisher = [[Mathematical Association of America]]
 | series = Dolciani Mathematical Expositions
 | volume = 27
 | year = 2003
 | isbn = 978-0-88385-333-7
 | title-link = Proofs That Really Count
 }}
* [https://www.encyclopediaofmath.org/index.php/Lucas_sequence ''Lucas sequence''] at [[Encyclopedia of Mathematics]].
* {{MathWorld | urlname=LucasSequence | title=Lucas Sequence}}
* {{cite web| url = http://weidai.com/lucas.html|author=Wei Dai|title= Lucas Sequences in Cryptography|author-link=Wei Dai}}

[[Category:Recurrence relations]]
[[Category:Integer sequences]]