Lucas-Zahlen

Lucas-Zahlen

Unter der Lucas-Folge versteht man zwei unterschiedliche Dinge:

  • Einerseits die Folge
2, 1, 3, 4, 7, 11, 18, 29, ...
bei der jedes Folgenglied (ab dem dritten) die Summe der beiden vorhergehenden ist.
  • Andererseits die beiden allgemeinen Lucas-Folgen Un(P,Q) und Vn(P,Q), die abhängig von den Parametern P und Q definiert sind als diejenigen Folgen, die
U_0=0,\quad U_1=1 bzw. V_0=2,\quad V_1=P
erfüllen und der Rekursionsformel
Un = PUn − 1QUn − 2 für n > 1
(entsprechend für Vn) genügen. Im Spezialfall P = 1 und Q = − 1 ist Un die Folge der Fibonacci-Zahlen, Vn die oben definierte spezielle Lucas-Folge.

Die Lucas-Folgen sind nach dem französischen Mathematiker Édouard Lucas benannt, der sich als erster mit ihnen beschäftigt hat.

Inhaltsverzeichnis

Explizite Formeln

Vorbereitung

Zur Bestimmung der Folgenglieder der allgemeinen Lucas-Folge muss vorbereitend die zugeordnete quadratische Gleichung gelöst werden.

Für die expliziten Formeln werden die beiden Lösungen a und b der quadratischen Gleichung x^2-Px+Q=0\ benötigt. Es sind dies

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}

Ist P2 − 4Q < 0, so ist eine der beiden komplexen Wurzeln zu wählen. Welche der beiden Zahlen a und welche b genannt wird, ist hierbei nicht von Belang.

Die Parameter P und Q und die Werte a und b sind von einander abhängig, es gilt umgekehrt

P=a+b,\quad Q=a\cdot b. (Satzgruppe von Vieta)

Die Formeln für a und b lassen sich in Bezug auf die Potenzen verallgemeinern. Und zwar gilt:

a^n = \frac{V_n + U_n \sqrt{P^2-4Q}}{2}\,
b^n = \frac{V_n - U_n \sqrt{P^2-4Q}}{2}\,


Die allgemeinen Lucas-Folgen

Falls P^2-4Q\ne0 gilt, oder äquivalent dazu: falls die Zahlen a und b verschieden sind, so berechnet sich das Glied der allgemeinen Lucas-Folge U_n(P,Q)\ nach folgender Formel:

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

für alle n \ge 0. Im Spezialfall P2 − 4Q = 0 gilt stattdessen

U_n(P,Q)=na^{n-1}=n\left(\frac P2\right)^{n-1}.

Das Glied der allgemeinen Lucas-Folge V_n(P,Q)\ berechnet sich nach folgender Formel:

V_n(P,Q)=a^n+b^n\

für alle n \ge 0

Beziehungen zwischen den Folgegliedern

  • U_{2n} = U_n\cdot V_n\
  • V_n = U_{n+1} - QU_{n-1}\
  • V_{2n} = V_n^2 - 2Q^n\
  • \operatorname{ggT}(U_m,U_n)=U_{\operatorname{ggT}(m,n)}
  • m\mid n\implies U_m\mid U_n; für alle U_m\ne 1

Spezialfälle

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
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
A+1 A A 1 a_i = 1+a_{i-1}\cdot A mit a_0=0\ An+1 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

Die allgemeine Lucas-Folgen Un(P,Q), Vn(P,Q) und die Primzahlen

Die Allgemeinen Lucas-Folgen U(P,Q)\ und V(P,Q)\ haben für ganzzahlige Parameter P und Q eine spezielle Eigenschaft hinsichtlich der Teilbarkeit durch Primzahlen. Diese Eigenschaft wurde bei bestimmten Verfahren zur Bestimmung 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} gilt:

Ist p\ eine Primzahl, so ist U_p(P,Q)-\left(\frac Dp\right) durch p\ teilbar.

Dabei ist \left(\frac Dp\right) 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\ gilt: wenn n\ eine Primzahl ist, dann ist (V_n(P,Q) - P)\ durch n\ teilbar. Oder, anders ausgedrückt:

V_n(P,Q) \equiv P \mod n

für alle n\ , die Primzahlen sind. Zusammengesetzte Zahlen die diese Bedingung erfüllen, mit der Einschränkung das P\ positiv und Q\ entweder 1 oder -1 ist, nennt man Fibonacci-Pseudoprimzahlen.

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ässt sich auf unterschiedlichste Art und Weise erzeugen:

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 Ln = Vn( − 1,1) = an + bn mit a = \frac{1 + \sqrt{5}}{2} und b = \frac{1 - \sqrt{5}}{2} ableiten lässt
  • Über die rekursive Formel, die der rekursiven Formel für die Fibonacci-Folge gleicht:
L_n = L_{n-1} + L_{n-2}\  mit den Anfangswerten L_0 = 2\  und L_1 = 1\ 
  • Über eine Potenz des goldenen Schnitt:
L_n = \Phi^n + \Psi^n\ 
  • Eine andere rekursive Formel:
L_{n+1} = \left[\frac{L_n(1+\sqrt{5})+1}{2}\right]
L_n = f_{n-1} + f_{n+1}\ 



Siehe auch

Literatur

  • Paulo Ribenboim: The new Book of Primenumber Records, ISBN 0-387-94457-5.
  • Paulo Ribenboim: My Numbers, my Friends, ISBN 0-387-98911-0.

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Lucas-Folgen — Unter der Lucas Folge versteht man zwei unterschiedliche Dinge: Einerseits die Folge 2, 1, 3, 4, 7, 11, 18, 29, ... bei der jedes Folgenglied (ab dem dritten) die Summe der beiden vorhergehenden ist. Andererseits die beiden allgemeinen Lucas… …   Deutsch Wikipedia

  • Lucas-Folge — Unter der Lucas Folge versteht man zwei unterschiedliche Dinge: Einerseits die Folge der Lucas Zahlen 2, 1, 3, 4, 7, 11, 18, 29, … bei der jedes Folgenglied (ab dem dritten) die Summe der beiden vorhergehenden ist. Andererseits die beiden… …   Deutsch Wikipedia

  • Zahlen — Zahlen, Mengen von Einheiten ein und derselben Art. Die Lehre von den Zahlen (Zahlentheorie) beherrscht gegenwärtig fall die gesamte reine Mathematik und drückt verschiedenen Zweigen derselben (z.B. der Algebra, Funktionentheorie, Geometrie) ihr… …   Lexikon der gesamten Technik

  • Lucas Cejpek — liest in Sydney (2005) Lucas Cejpek (* 14. Dezember 1956 in Wien) ist ein österreichischer Schriftsteller und Regisseur. Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • Lucas-Lehmer Test — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Lucas-Test (Mathematik) — Der Lucas Test ist eine Weiterentwicklung des Fermatschen Primzahltests durch den Mathematiker Édouard Lucas. Der Test wurde in den 50er Jahren von Derrick Lehmer und später nochmals von John Brillhart und John L. Selfridge verbessert. Er sollte… …   Deutsch Wikipedia

  • Lucas-Lehmer-Test — Ausschnitt von Seite 316 der Arbeit Théorie des Fonctions Numériques Simplement Périodiques von Édouard Lucas (1878) Der Lucas Lehmer Test ist ein Primzahltest für Mersenne Zahlen, das heißt für Zahlen der Form Mn = 2n − 1. Der Test wird im GIMPS …   Deutsch Wikipedia

  • Lucas-Carmichael-Zahl — Eine Lucas Carmichael Zahl ist eine zusammengesetzte, natürliche Zahl, die eine ähnliche Bedingung wie eine Carmichael Zahl erfüllt. Inhaltsverzeichnis 1 Definition 2 Beispiel 3 Die kleinsten Lucas Carmichael Zahlen 4 …   Deutsch Wikipedia

  • Fibonacci-Zahlen — Ein Kachelmuster aus Quadraten, deren Kantenlänge der Fiboncci Folge entspricht Die Fibonacci Folge ist eine unendliche Folge von Zahlen (den Fibonacci Zahlen), bei der sich die jeweils folgende Zahl durch Addition der beiden vorherigen Zahlen… …   Deutsch Wikipedia

  • Édouard Lucas — François Édouard Anatole Lucas (* 4. April 1842 in Amiens; † 3. Oktober 1891 in Paris) war ein französischer Mathematiker. Édouard Lucas Inhaltsverzeichnis …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”