Lucas sequence: Difference between revisions
imported>Hendra I. Nurdin mNo edit summary |
mNo edit summary |
||
| (9 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
'''Lucas | {{subpages}} | ||
In [[mathematics]], a '''Lucas sequence''' is a particular generalisation of sequences like the [[Fibonacci number|Fibonacci numbers]], [[Lucas number|Lucas numbers]], [[Pell number|Pell numbers]] or [[Jacobsthal number|Jacobsthal numbers]]. Lucas sequences have one common characteristic: they can be generated over [[quadratic equation|quadratic equations]] of the form: <math>\scriptstyle x^2-Px+Q=0\ </math> with <math>\scriptstyle P^2-4Q \ne 0</math>. | |||
There exist two kinds of Lucas sequences: | There exist two kinds of Lucas sequences: | ||
*Sequences <math>\scriptstyle U(P,Q) = (U_n(P,Q))_{n \ge | *Sequences <math>\scriptstyle U(P,Q) = (U_n(P,Q))_{n \ge 0}</math> with <math>\scriptstyle U_n(P,Q)=\frac{a^n-b^n}{a-b}</math>, | ||
*Sequences <math>\scriptstyle V(P,Q) = (V_n(P,Q))_{n \ge | *Sequences <math>\scriptstyle V(P,Q) = (V_n(P,Q))_{n \ge 0}</math> with <math>\scriptstyle V_n(P,Q)=a^n+b^n\ </math>, | ||
where <math>\scriptstyle a\ </math> and <math>b\ </math> are the solutions | where <math>\scriptstyle a\ </math> and <math>b\ </math> are the solutions | ||
| Line 18: | Line 19: | ||
*The variables <math>\scriptstyle a\ </math> and <math>\scriptstyle b\ </math>, and the parameter <math>\scriptstyle P\ </math> and <math>\scriptstyle Q\ </math> are interdependent. In particular, <math>\scriptstyle P=a+b\ </math> and <math>\scriptstyle Q=a\cdot b.</math>. | *The variables <math>\scriptstyle a\ </math> and <math>\scriptstyle b\ </math>, and the parameter <math>\scriptstyle P\ </math> and <math>\scriptstyle Q\ </math> are interdependent. In particular, <math>\scriptstyle P=a+b\ </math> and <math>\scriptstyle Q=a\cdot b.</math>. | ||
*For every sequence <math>\scriptstyle U(P,Q) = (U_n(P,Q))_{n \ge | *For every sequence <math>\scriptstyle U(P,Q) = (U_n(P,Q))_{n \ge 0}</math> it holds that <math>\scriptstyle U_0 = 0\ </math> and <math>U_1 = 1 </math>. | ||
*For every sequence <math>\scriptstyle V(P,Q) = (V_n(P,Q))_{n \ge | *For every sequence <math>\scriptstyle V(P,Q) = (V_n(P,Q))_{n \ge 0}</math> is holds that <math>\scriptstyle V_0 = 2\ </math> and <math>V_1 = P </math>. | ||
For every Lucas sequence the following are true: | For every Lucas sequence the following are true: | ||
| Line 25: | Line 26: | ||
*<math>\scriptstyle V_n = U_{n+1} - QU_{n-1}\ </math> | *<math>\scriptstyle V_n = U_{n+1} - QU_{n-1}\ </math> | ||
*<math>\scriptstyle V_{2n} = V_n^2 - 2Q^n\ </math> | *<math>\scriptstyle V_{2n} = V_n^2 - 2Q^n\ </math> | ||
*<math>\scriptstyle \operatorname{ | *<math>\scriptstyle \operatorname{gcd}(U_m,U_n)=U_{\operatorname{gcd}(m,n)}</math> | ||
*<math>\scriptstyle m\mid n\implies U_m\mid U_n</math> for all <math>\scriptstyle U_m\ne 1</math> | *<math>\scriptstyle m\mid n\implies U_m\mid U_n</math> for all <math>\scriptstyle U_m\ne 1</math> | ||
<!-- Taken from engish Wikipedia - Start --> | |||
==Recurrence relation== | |||
The Lucas sequences ''U''(''P'',''Q'') and ''V''(''P'',''Q'') are defined by the [[recurrence relation]]s | |||
:<math>U_0(P,Q)=0 \,</math> | |||
<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.--> | |||
:<math>U_1(P,Q)=1 \,</math> | |||
<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.--> | |||
:<math>U_n(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q) \mbox{ for }n>1 \,</math> | |||
<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.--> | |||
and | |||
:<math>V_0(P,Q)=2 \,</math> | |||
<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.--> | |||
:<math>V_1(P,Q)=P \,</math> | |||
<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.--> | |||
:<math>V_n(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q) \mbox{ for }n>1 \,</math> | |||
<!-- The \, is to keep the formula rendered as PNG instead of HTML. Please don't remove it.--> | |||
<!-- Taken from english Wikipedia - End --> | |||
==Fibonacci numbers and Lucas numbers== | ==Fibonacci numbers and Lucas numbers== | ||
| Line 38: | Line 67: | ||
*<math>\scriptstyle p\ </math> divides <math>\scriptstyle V_p(P,Q)-P\ </math> | *<math>\scriptstyle p\ </math> divides <math>\scriptstyle V_p(P,Q)-P\ </math> | ||
[[Fermat's Little Theorem]] can then be seen as a special case of <math>\scriptstyle p\ </math> divides <math>\scriptstyle (V_n(P,Q) - P)\ </math> because <math>\scriptstyle a^p \equiv a \ | [[Fermat's Little Theorem]] can then be seen as a special case of <math>\scriptstyle p\ </math> divides <math>\scriptstyle (V_n(P,Q) - P)\ </math> because <math>\scriptstyle a^p \equiv a \pmod p</math> is equivalent to <math>\scriptstyle V_p(a+1,a) \equiv V_1(a+1,a) \pmod p</math>. | ||
The converse pair of statements that if <math>\scriptstyle n\ </math> divides <math>\scriptstyle U_n(P,Q)-\left(\frac Dn\right)</math> then is <math>\scriptstyle n\ </math> a prime number and if <math>m\ </math> divides <math>\scriptstyle V_m(P,Q)-P\ </math> then is <math>m\ </math> a prime number) are individually false and lead to [[Fibonacci pseudoprime|Fibonacci pseudoprimes]] and [[Lucas pseudoprime|Lucas pseudoprimes]], respectively. | The converse pair of statements that if <math>\scriptstyle n\ </math> divides <math>\scriptstyle U_n(P,Q)-\left(\frac Dn\right)</math> then is <math>\scriptstyle n\ </math> a prime number and if <math>m\ </math> divides <math>\scriptstyle V_m(P,Q)-P\ </math> then is <math>m\ </math> a prime number) are individually false and lead to [[Fibonacci pseudoprime|Fibonacci pseudoprimes]] and [[Lucas pseudoprime|Lucas pseudoprimes]], respectively. | ||
| Line 44: | Line 73: | ||
== Further reading == | == Further reading == | ||
*P. Ribenboim, ''The New Book of Prime Number Records'' (3 ed.), Springer, 1996, ISBN 0-387-94457-5. | *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. | *P. Ribenboim, ''My Numbers, My Friends'', Springer, 2000, ISBN 0-387-98911-0.[[Category:Suggestion Bot Tag]] | ||
[[Category: | |||
Latest revision as of 16:00, 13 September 2024
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 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^2-4Q \ne 0} .
There exist two kinds of Lucas sequences:
- Sequences 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}} 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 U_n(P,Q)=\frac{a^n-b^n}{a-b}} ,
- Sequences 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}} 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 V_n(P,Q)=a^n+b^n\ } ,
where 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\ } 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 b\ } are the solutions
- 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 a = \frac{P + \sqrt{P^2 - 4Q}}{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 b = \frac{P - \sqrt{P^2 - 4Q}}{2}}
of the quadratic equation 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} .
Properties
- The variables 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\ } 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\ } , and the parameter 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\ } 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 a prime number and if divides then is 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.