Fibonacci-, Lucas- und Ulamzahlen

Inhaltsverzeichnis

1. Was Kaninchen und antike Bauwerke gemeinsam haben

2. Die Lucaszahlen
2.1. Édouard Lucas: Leben und Werk
2.2. Mathematische Definition der Lucaszahlen
2.3. Mathematische Besonderheiten
2.4. Praktische Anwendungen der Lucaszahlen
2.4.1. Der Lucas-Lehmer-Test
2.4.2. Lucaszahlen in der Datenverschlüsselung

3. Die Fibonaccizahlen
3.1. Leonardo da Pisa: Leben und Werk
3.2. Entdeckung der Fibonaccizahlen
3.2.1. Entdeckung der Zahlenfolge vor Fibonacci
3.2.2. Liber Abaci: Die Kaninchenaufgabe
3.3. Mathematische Definition der Fibonaccizahlen
3.3.1. Allgemeine Definition
3.3.2. Die Formel von Binet
3.4. Mathematische Besonderheiten
3.5. Die Fibonaccizahlen und der Goldene Schnitt
3.5.1. Mathematischer Zusammenhang
3.5.2. Fibonaccizahlen in der Natur
3.5.3. Fibonaccizahlen in der Kunst
3.5.4. Fibonaccizahlen in der Architektur
3.5.5. Fibonaccizahlen in der Musik
3.6. Praktische Anwendungen der Fibonaccizahlen
3.7. Zusammenhänge zwischen Fibonacci- und Lucaszahlen

4. Die Ulamzahlen
4.1. Stanislaw Ulam: Leben und Werk
4.2. Mathematische Definition der Ulamzahlen
4.3. Mathematische Besonderheiten

5. Zusammenfassung und Ausblick

6. Literaturverzeichnis

7. Abbildungsverzeichnis

1. Was Kaninchen und antike Bauwerke gemeinsam haben

Was hat die Vermehrung von Kaninchen mit der Anordnung von Sonnenblumenkernen oder der antiken Architektur zu tun? Und welche Rolle spielt dabei ein italienischer Mathematiker namens Leonardo da Pisa? Lassen sich derartige Dinge etwa durch mathematische Formeln berechnen? Die vorliegende Seminararbeit wird Antworten auf diese und auch auf viele weitere Fragen geben.

Die Lucaszahlen stellen das erste Thema dieser Arbeit dar. Sie sind eine wichtige Zahlenfolge in der Zahlentheorie und finden beispielsweise in der Datenverschlüsselung Verwendung. Sie stehen in direktem Zusammenhang mit den Fibonaccizahlen.

Die Fibonaccifolge birgt die Antwort auf die oben genannten Fragen. Obwohl sie zu den allgemein bekanntesten Zahlenfolgen zählt, wissen die meisten Menschen nichts oder nicht viel über sie sowie über ihre Bedeutung für unser gesamtes Leben und unsere Umwelt. Sie erscheint auf den ersten Blick sehr simpel und unbedeutsam, und doch sind die Menschen schon seit Jahrhunderten von ihr fasziniert. Der größte Teil dieser Seminararbeit wird sich damit befassen, dem Leser diese wichtige Zahlenfolge näher zu bringen.

Eine weitere Zahlenfolge - die Ulamfolge - wird am Ende noch kurz beleuchtet. Vertieft darauf einzugehen würde jedoch den Umfang dieser Arbeit sprengen.

Alle drei Zahlenfolgen werden nacheinander behandelt und ihre Problematiken dem Leser nähergebracht. Dabei wird jeweils zunächst kurz auf ihre Entdecker bzw. ihre Namensgeber eingegangen. Danach werden die Folgen definiert, ihre mathematischen Besonderheiten betrachtet und - wo möglich - praktische Anwendungen aufgezeigt.

2. Die Lucaszahlen

2.1. Édouard Lucas: Leben und Werk

„Die (…) Folge trägt ihren Namen zu Ehren des französischen Zahlentheoretikers Édouard Lucas“^[1]. Dieser wurde am 4. April 1842 alsFrançois Édouard Anatole Lucasin Amiens in Frankreich geboren. Nachdem er im Deutsch-Französischen Krieg^[2]als Offizier gedient hatte, wurde er Professor für Mathematik in Paris. Dabei beschäftigte er sich hauptsächlich mit der Zahlentheorie. Berühmt wurde er vor allem für seine Erkenntnisse bezüglich der Fibonaccizahlen und der Lucaszahlen. Er benannte die Fibonaccifolge nach ihrem Erfinder und fand eine Verallgemeinerung dieser Folge. Außerdem entwickelte er den Lucas-Test, der der Vorreiter für den Lucas-Lehmer-Test war. Mit Hilfe dieses Tests lässt sich feststellen, ob es sich bei einerMersenne-Zahl^[3]um eine Primzahl handelt oder nicht.^[4]Des Weiteren erfand und vermarktete er ein bekanntes mathematisches Knobelspiel mit NamenDie Türme von Hanoi. Lucas starb am 3. Oktober 1891 in Paris.^[5]

2.2. Mathematische Definition der Lucaszahlen

Die Lucaszahlen sind die Glieder der Lucasfolge, die als ln = ln-1 + ln-2 definiert ist, wobei n eine natürliche Zahl und ln die n-te Lucaszahl ist. Diese Zahlenfolge ist also rekursiv definiert, d.h. jedes Glied der Folge kann aus vorhergehenden Gliedern berechnet werden. Die einzige Voraussetzung ist dabei das Setzen zweier Startwerte. Bei der Lucasfolge sind diese Startwerte auf l1 = 1 und l2 = 3, bzw. l0 = 2 und l1 = 1 festgelegt.

Somit sind die ersten Glieder der Lucasfolge: (2,) 1, 3, 4, 7, 11, 18, 29, 47, 76, …^[6]

Darüber hinaus gibt es weitere Folgen, die ebenso Lucasfolgen genannt werden: dieallgemeinen Lucasfolgen. Sie lauten, für[Abbildung in dieser Leseprobe nicht enthalten]:

Abbildung in dieser Leseprobe nicht enthalten

Diese Folgen stellen eine Verallgemeinerung der Fibonaccifolge dar.^[7]

2.3. Mathematische Besonderheiten

Die Lucasfolge weist sehr viele Besonderheiten auf. All diese aufzuzeigen würde eine eigene Seminararbeit füllen. Aus diesem Grund wird hier nur ein kleiner Ausschnitt betrachtet.

Es existiert zum Beispiel keine Lucaszahl, die durch die Zahl 8 teilbar ist. Diese Behauptung lässt sich beweisen, indem man aufeinanderfolgende Lucaszahlenmodulo 8betrachtet; das heißt, man teilt die jeweilige Lucaszahl durch 8 und gibt den Rest an. Falls dieser Teilerrest 0 beträgt, ist die betreffende Lucaszahl durch 8 teilbar.

Es fällt auf, dass sich nach einer Periodenlänge von 12 die Restbeträge wiederholen und innerhalb dieser Reihe der Rest 0 nicht vorkommt; das heißt:

l0 = l12 = l24 = l36 = l(n*12) = 2 (mod 8),

l1 = l13 = l25 = l37 = l(n*12)+1 = 1 (mod 8),

l2 = l14 = l26 = l38 = l(n*12)+2 = 3 (mod 8),

usw.

Da sich die verbleibenden Restbeträge immer nach zwölf Lucaszahlen wiederholen und dabei ln = 0 (mod 8) nicht vorkommt, ist bewiesen, dass es keine Lucaszahl gibt, die durch 8 teilbar ist.^[8]

Weitere Besonderheiten gibt es im Bereich der Quadratzahlen. So kommen beispielsweise nur zwei Quadratzahlen bei den Gliedern der Lucasfolge vor. Diese sind l1 = 1 und l3 = 4.^[9]Der Beweis hierfür ist in dem 2009 erschienenen BuchFibonacci und die Folge(n)von Huberta Lausch ab Seite 99 nachzulesen. Darüber hinaus werden darin auch weitere Besonderheiten der Lucasfolge dargelegt.

2.4. Praktische Anwendungen der Lucaszahlen

2.4.1. Der Lucas-Lehmer-Test

Mit Hilfe des sogenanntenLucas-Lehmer-Testskann geprüft werden, ob es sich bei einerMersenne-Zahl^[10]um eine Primzahl handelt. Der Test beruht auf den oben genanntenallgemeinen Lucasfolgenund deren Eigenschaften. Er wurde 1930 von dem MathematikerDerrick Lehmerentwickelt und funktioniert folgendermaßen:^[11]

„Seipungerade. Ferner sei die FunktionS(k) definiert durchS(1)= 4;S(k+1)=S(k)2 -2.

Dann gilt:M p= 2p-1 ist genau dann eine Primzahl, wennS(p-1) durchM pteilbar ist.“[sic!]^[12]

Dieses Verfahren ist zwar ausschließlich auf die Mersenne-Zahlen begrenzt, doch ist es für diese Zahlen, im Vergleich zu anderen Tests, eine sehr schnelle Methode.^[13]

2.4.2. Lucaszahlen in der Datenverschlüsselung

Ein weiterer Anwendungsbereich ist die sogenannteasymmetrische Verschlüsselung. Die Besonderheit bei dieser Verschlüsselungstechnik besteht darin, dass es hier anstatt eines Schlüssels zwei Schlüssel gibt: denprivatenund denöffentlichen. Die Codierung mit Hilfe der Lucasfolge ist hierbei möglich, wird allerdings in der Praxis kaum verwendet. Auch dieses Verfahren wurde von Derrick Lehmer entwickelt.^[14]

[...]

^[1]Lausch, H. (2009): Fibonacci und die Folge(n), Seite 3.

^[2]Deutsch-Französischer Krieg: 1870-1871.

^[3]Mersenne-Zahlen: Mn = 2n-1.

^[4]Siehe Kapitel 2.4.1Der Lucas-Lehmer-Test.

^[5]Vgl. O'Connor; Robertson: François Edouard Anatole Lucas, Internetseite: „http://www-history.mcs.st-

andrews.ac.uk/Biographies/Lucas.html” vom Dezember 1996; aufgerufen am 07.11.2010.

^[6]Vgl. Lausch (2009), S. 3.

^[7]Vgl. Lausch (2009), S. 163f.

^[8]Vgl. Lausch (2009), S. 75.

^[9]Vgl. Lausch (2009), S. 99.

^[10]Mersenne-Zahlen: Mn = 2n-1.

^[11]Vgl. Verfasser unbekannt: Der Lucas-Lehmer-Test, Internetseite: „http://www.uni-protokolle.de/ Lexikon/Mersenne-Primzahl.html#Der_Lucas-Lehmer-Test“; aufgerufen am 07.11.2010.

^[12]Ebd.

^[13]Vgl. Göbel; Goehring; Ostermeier: Primzahltests und Faktorisierung, Internetseite: „http://www.cs.uni- potsdam.de/ti/lehre/06-Kryptographie/slides/slides-07.pdf“, vom 07.12.2006, S. 43; aufgerufen am 07.11.2010.

^[14]Vgl. Pommerening, K.: Asymmetrische Verschlüsselung, Internetseite: „http://www.staff.uni-mainz.de/ pommeren/Kryptologie/Asymmetrisch/Asymm.pdf“, vom 16.01.2009, S. 1 und S. 70; aufgerufen am 07.11.2010.