Lucas sequence

In mathematics, a Lucas sequence is a particular generalisation of sequences like the Fibonacci numbers, Lucas numbers, Pell numbers or Jacobsthal numbers. Lucas sequences have one common characteristic: they can be generated over quadratic equations of the form: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle x^2-Px+Q=0\ } with $\scriptstyle P^{2}-4Q\neq 0$.

There exist two kinds of Lucas sequences:

• Sequences $\scriptstyle U(P,Q)=(U_{n}(P,Q))_{n\geq 0}$ with $\scriptstyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}$,
• Sequences $\scriptstyle V(P,Q)=(V_{n}(P,Q))_{n\geq 0}$ with $\scriptstyle V_{n}(P,Q)=a^{n}+b^{n}\$,

where $\scriptstyle a\$ and $b\$ are the solutions

$a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}$

and

$b={\frac {P-{\sqrt {P^{2}-4Q}}}{2}}$

of the quadratic equation $\scriptstyle x^{2}-Px+Q=0$.

Properties

• The variables $\scriptstyle a\$ and $\scriptstyle b\$, and the parameter $\scriptstyle P\$ and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle Q\ } are interdependent. In particular, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle P=a+b\ } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle Q=a\cdot b.} .
• For every sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle U(P,Q) = (U_n(P,Q))_{n \ge 0}} it holds that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle U_0 = 0\ } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_1 = 1 } .
• For every sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle V(P,Q) = (V_n(P,Q))_{n \ge 0}} is holds that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle V_0 = 2\ } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_1 = P } .

For every Lucas sequence the following are true:

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle U_{2n} = U_n\cdot V_n\ }
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle V_n = U_{n+1} - QU_{n-1}\ }
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle V_{2n} = V_n^2 - 2Q^n\ }
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \operatorname{gcd}(U_m,U_n)=U_{\operatorname{gcd}(m,n)}}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle m\mid n\implies U_m\mid U_n} for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle U_m\ne 1}

Recurrence relation

The Lucas sequences U(P,Q) and V(P,Q) are defined by the recurrence relations

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_0(P,Q)=0 \,}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_1(P,Q)=1 \,}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_n(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q) \mbox{ for }n>1 \,}

and

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_0(P,Q)=2 \,}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_1(P,Q)=P \,}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_n(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q) \mbox{ for }n>1 \,}

Fibonacci numbers and Lucas numbers

The two best known Lucas sequences are the Fibonacci numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle U(1,-1)\ } and the Lucas numbers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle V(1,-1)\ } with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle a = \frac{1+\sqrt{5}}{2}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle b = \frac{1-\sqrt{5}}{2}} .

Lucas sequences and the prime numbers

If the natural number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p\ } is a prime number then it holds that

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p\ } divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle U_p(P,Q)-\left(\frac Dp\right)}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p\ } divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle V_p(P,Q)-P\ }

Fermat's Little Theorem can then be seen as a special case of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p\ } divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle (V_n(P,Q) - P)\ } because Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle a^p \equiv a \pmod p} is equivalent to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle V_p(a+1,a) \equiv V_1(a+1,a) \pmod p} .

The converse pair of statements that if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n\ } divides Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \scriptstyle U_n(P,Q)-\left(\frac Dn\right)} then is $\scriptstyle n\$ a prime number and if $m\$ divides $\scriptstyle V_{m}(P,Q)-P\$ then is $m\$ a prime number) are individually false and lead to Fibonacci pseudoprimes and Lucas pseudoprimes, respectively.

Further reading

• P. Ribenboim, The New Book of Prime Number Records (3 ed.), Springer, 1996, ISBN 0-387-94457-5.
• P. Ribenboim, My Numbers, My Friends, Springer, 2000, ISBN 0-387-98911-0.