Lucas sequence: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Karsten Meyer
mNo edit summary
imported>Karsten Meyer
Line 38: Line 38:
*<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 \mod p</math> is equivalent to <math>\scriptstyle V_p(a+1,a) \equiv V_1(a+1,a) \mod 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 \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.

Revision as of 09:23, 17 November 2007

Lucas sequences are a particular generalisation of sequences like the Fibonacci numbers, Lucas numbers, Pell numbers or Jacobsthal numbers. These 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\ } .

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 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 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 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 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 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 1}} 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 1}} 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{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 \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}

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 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\ } 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 \scriptstyle 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) are individually false and lead to Fibonacci pseudoprimes and Lucas pseudoprimes, respectively.

Further reading

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