Lucas-Folge

Unter der Lucas-Folge versteht man zwei unterschiedliche Dinge, nämlich einmal die beiden allgemeinen Lucas-Folgen U(P,Q) und V(P,Q), und andererseits die spezielle Lucas-Folge: 2 1 3 4 7 11 18 29 ..., die mit der Fibonacci-Folge zusammen hängt. Die Lucas-Folge ist nach dem französischen Mathematiker Edouard Lucas benannt, der sich als erster mit ihr beschäftigt hat.

Vorbemerkung

Die allgemeine Lucas-Folge hat zum einen mit quadratischen Gleichungen zu tun, und andererseits ist es zum Verständnis von Vorteil, ableiten (Differentialrechnung) zu können.

Einleitung

Eine quadratische Gleichung $x^{2}+px+q=0\$ läßt sich nach der pq-Formel lösen:

x_{1}=-{\frac {p}{2}}+{\sqrt {{\frac {p^{2}}{4}}-q}}

und

x_{2}=-{\frac {p}{2}}-{\sqrt {{\frac {p^{2}}{4}}-q}}

Dabei bezeichnet man ${\frac {p^{2}}{4}}-q$ als die Diskriminante d

So lassen sich also über die quadratische Gleichung $x^{2}-px+q=0\$ , bei vorgegebenen P und Q die entsprechenden a und b berechnen:

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

und

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

Mit anderen Worten: Die Parameter P und Q und die Werte a und b sind von einander abhängig.

Die allgemeinen Lucas-Folgen

Das Glied einer allgemeinen Lucas-Folge $U_{n}(P,Q)\$ berechnet sich nach folgender Formel:

U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}

für alle $n\geq 0$

Das Glied einer allgemeinen Lucas-Folge $V_{n}(P,Q)\$ berechnet sich nach folgender Formel:

V_{n}(P,Q)=a^{n}+b^{n}\

für alle $n\geq 0$

Die Folgen $U(P,Q)=(U_{n}(P,Q))_{n\geq 0}\$ und $V(P,Q)=(V_{n}(P,Q))_{n\geq 0}\$ bezeichnet man dabei als Lucas-Folgen assoziiert zum Paar (P,Q).

P	Q	a	b	U(P,Q)	V(P,Q)
1	-1	${\frac {1+{\sqrt {5}}}{2}}$	${\frac {1-{\sqrt {5}}}{2}}$	Fibonacci-Folge	Lucas-Folge
3	2	2	1	2ⁿ-1 Folge	2ⁿ+1 Folge
2	-1	$1+{\sqrt {2}}$	$1-{\sqrt {2}}$	Pell-Folge	Companion Pell-Folge
1	-2	${\frac {1+{\sqrt {9}}}{2}}$	${\frac {1-{\sqrt {9}}}{2}}$	Jacobsthal-Folge
3	-10	5	-2	Folge A015528 in OEIS
4	-5	5	-1	Folge A015531 in OEIS
5	-6	6	-1	Folge A015540 in OEIS
8	-9	9	-1	Folge A015577 in OEIS

Eigenschaften

U₀, U₁, V₀ und V₁ sind definiert

Unabhängig von P und Q sind $U_{0}(P,Q),\ U_{1}(P,Q)\$ und $V_{0}(P,Q)\$ definiert:

U_{0}={\frac {a^{0}-b^{0}}{a-b}}={\frac {1-1}{a-b}}={\frac {0}{a-b}}=0

U_{1}={\frac {a^{1}-b^{1}}{a-b}}={\frac {a-b}{a-b}}={\frac {1}{1}}=1

V_{0}=a^{0}+b^{0}=1+1=2\

V_{1}(P,Q)=P\

Die allgemeine Lucas-Folgen U_n(P,Q), V_n(P,Q) und die Primzahlen

Die Allgemeinen Lucas-Folgen $U(P,Q)\$ und $V(P,Q)\$ haben eine spezielle Eigenschaft auf die Teilbarkeit, von Primzahlen. Diese Eigenschaft wurde bei bestimmten Verfahren zur Bestimung der Primalität einer Zahl angewandt. Leider waren diese Verfahren für bestimmte Arten von Pseudoprimzahlen anfällig.

U(P,Q)

Für alle Lucas-Folgen $U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}$ mit der Diskriminante $D=P^{2}-4Q\$ gilt:

Ist

p\

eine Primzahl, so ist

U_{n}(P,Q)-\left({\frac {D}{p}}\right)

durch

p\

teilbar

Dabei ist $\left({\frac {D}{p}}\right)={\begin{cases}1&p\equiv 1,4\mod D\\-1&p\equiv 2,3\mod D\\0&p=D\end{cases}}$ das Legendre-Symbol

Es existieren auch zusammengesetzte Zahlen, die diese Bedingung erfüllen. Diese Zahlen nennt man Lucas-Pseudoprimzahlen.

V(P,Q)

Für alle Lucas-Folgen $V_{n}(P,Q)=a^{n}+b^{n}\$ mit $P>0\$ und $Q=\pm 1$ gilt, das wenn $n\$ eine Primzahl ist, das $(V_{n}(P,Q)-P)\$ durch $n\$ teilbar ist. Oder anders ausgedrückt:

V_{n}(P,Q)\equiv P\mod n

für alle $n\$ die Primzahlen sind.

Der kleine fermatsche Satz

Besonders interessant ist dies für die Folge $V_{n}(3,2)=a^{n}+b^{n}=2^{n}+1\$ . Für diese Folge gilt nämlich:

Wenn n eine Primzahl ist, dann gilt: n teilt

2^{n}+1-3=2^{n}-2\

.

Dies ist eine spezielle Form des kleinen Fermatschen Satz.

Analog zu $a^{p}\equiv a\mod p$ gilt also $V_{p}(a+1,a)\equiv V_{1}(a+1,a)\mod p$

Anwendungen der allgemeinen Lucas-Folgen

Die allgemeinen Lucas-Folgen spielen in der Zahlentheorie und der Kryptographie eine Rolle.

Siehe auch: Lucas-Lehmer-Test, Lucassche Pseudoprimzahl, Fibonacci-Folge, Jacobsthal-Folge, Pell-Folge

Die spezielle Lucas-Folge

Die allgemein als Lucas-Folge bekannte Folge L_n der Lucas-Zahlen 2 1 3 4 7 11 18 29 ... läßt sich auf unterschiedlichste Art und Weise erzeugen:

Über die Formel von Binet (nach Jacques Philippe Marie Binet):

 $L_{n}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}$ 
die sich aus der allgemeinen Lucas-Folge  $L_{n}=V_{n}(-1,1)=a^{n}+b^{n}$  mit a =  ${\frac {1+{\sqrt {5}}}{2}}$  und b =  ${\frac {1-{\sqrt {5}}}{2}}$  ableiten läßt

Über die rekursive Formel, die der rekursiven Formel für die Fibonacci-Folge gleicht:

 $L_{n}=L_{n-1}+L_{n-2}\$

Über eine Potenz des goldenen Schnitt

 $L_{n}=\Phi ^{n}\$

Eine andere rekursive Formel:

 $L_{n+1}=\left[{\frac {L_{n}(1+{\sqrt {5}})+1}{2}}\right]$

Die Lucas-Folge: ... 2 1 3 4 7 11 18 29 ... läßt sich auch als Summe zweier verschobener Fibonacci-Folgen darstellen:

   ... 1 1 2 3 5  8 13 21 34 55 ...
+  ... 1 0 1 1 2  3  5  8 13 21 ...
-----------------------------------
=  ... 2 1 3 4 7 11 18 29 47 71 ...

Die Folge ist nach dem französischen Mathematiker Edouard Lucas (1842-1891) benannt, nachdem auch die allgemeinen Lucas-Folgen benannt sind, und der sich intensiv mit Zahlentheorie beschäftigte.

Siehe auch

lineare Differenzengleichung

Literatur

The new Book of Primenumber Records, Paolo Ribenboim, ISBN 0-387-94457-5
My Numbers, my Friends, Paolo Ribenboim, ISBN 0-387-98911-0

Weblinks