Lucas sequence: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Karsten Meyer
(New page: '''Lucas sequences''' are the particular generalisation of sequences like Fibonacci numbers, Lucas numbers, Pell numbers or [[Jacobsth...)
 
imported>Karsten Meyer
mNo edit summary
Line 27: Line 27:
Is the natural number <math>p\ </math> a [[Prime number]], then it is true, that
Is the natural number <math>p\ </math> a [[Prime number]], then it is true, that
*<math>p\ </math> divides <math>U_p(P,Q)-\left(\frac Dp\right)</math>
*<math>p\ </math> divides <math>U_p(P,Q)-\left(\frac Dp\right)</math>
*<math>p\ </math> divides <math>V_p(P,Q)-\P </math>
*<math>p\ </math> divides <math>V_p(P,Q)-P\ </math>


Fermat's little theorem you can see as a special case of <math>p\ </math> divides <math>(V_n(P,Q) - P)\ </math> because <math>a^p \equiv a \mod p</math> is äquivalent to <math>V_p(a+1,a) \equiv V_1(a+1,a) \mod p</math>
Fermat's little theorem you can see as a special case of <math>p\ </math> divides <math>(V_n(P,Q) - P)\ </math> because <math>a^p \equiv a \mod p</math> is äquivalent to <math>V_p(a+1,a) \equiv V_1(a+1,a) \mod p</math>


The converse (If <math>n\ </math> divides <math>U_n(P,Q)-\left(\frac Dn\right)</math> then is <math>n\ </math> a prime number and if <math>m\ </math> divides <math>V_m(P,Q)-\P </math> then is <math>m\ </math> a prime number) is false and lead to [[Fibonacci pseudoprime|Fibonacci pseudoprimes]] respectively to [[Lucas pseudoprime|Lucas pseudoprimes]].
The converse (If <math>n\ </math> divides <math>U_n(P,Q)-\left(\frac Dn\right)</math> then is <math>n\ </math> a prime number and if <math>m\ </math> divides <math>V_m(P,Q)-P\ </math> then is <math>m\ </math> a prime number) is false and lead to [[Fibonacci pseudoprime|Fibonacci pseudoprimes]] respectively to [[Lucas pseudoprime|Lucas pseudoprimes]].


== Further reading ==
== Further reading ==

Revision as of 21:12, 15 November 2007

Lucas sequences are the particular generalisation of sequences like Fibonacci numbers, Lucas numbers, Pell numbers or Jacobsthal numbers. Every of this sequences has one common factor. They could be generatet over quadratic equatations 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 x^2-Px+Q=0\ } .

There exists kinds of Lucas sequences:

  • 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 U(P,Q) = (U_n(P,Q))_{n \ge 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 U_n(P,Q)=\frac{a^n-b^n}{a-b}}
  • 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 V(P,Q) = (V_n(P,Q))_{n \ge 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 U_n(P,Q)=a^n+b^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 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 equatation 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 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 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\ } , 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 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 Q\ } are interdependent. So it is true, 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 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 Q=a\cdot b.} .
  • For very 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 U(P,Q) = (U_n(P,Q))_{n \ge 1}} is it true, 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 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 very 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 V(P,Q) = (V_n(P,Q))_{n \ge 1}} is it true, 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 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 is true 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 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 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 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 \operatorname{ggT}(U_m,U_n)=U_{\operatorname{ggT}(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 m\mid n\implies U_m\mid U_n} ; für alle 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_m\ne 1}

Fibonacci numbers and Lucas numbers

The both 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 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 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 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 b = \frac{1-\sqrt{5}}{2}} .

Lucas sequences and the Prime numbers

Is 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 p\ } a Prime number, then it is true, 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 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 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 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 V_p(P,Q)-P\ }

Fermat's little theorem you can see 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 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 (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 a^p \equiv a \mod p} is äquivalent 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 V_p(a+1,a) \equiv V_1(a+1,a) \mod p}

The converse (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 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 U_n(P,Q)-\left(\frac Dn\right)} then is 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 n\ } a prime number and 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 m\ } 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 V_m(P,Q)-P\ } then is 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 m\ } a prime number) is false and lead to Fibonacci pseudoprimes respectively to Lucas pseudoprimes.

Further reading

Retrieved from "https://citizendium.org/wiki/index.php?title=Lucas_sequence&oldid=338665"