- 2 -

Inhaltsverzeichnis

1.  Was Kaninchen und antike Bauwerke gemeinsam haben  3

2.  Die Lucaszahlen.  4

2.1.  Édouard Lucas: Leben und Werk.  4

2.2.  Mathematische Definition der Lucaszahlen  4

2.3.  Mathematische Besonderheiten.  5

2.4.  Praktische Anwendungen der Lucaszahlen.  6

2.4.1.  Der Lucas-Lehmer-Test  6

2.4.2.  Lucaszahlen in der Datenverschlüsselung.  6

3.  Die Fibonaccizahlen  7

3.1.  Leonardo da Pisa: Leben und Werk  7

3.2.  Entdeckung der Fibonaccizahlen.  7

3.2.1.  Entdeckung der Zahlenfolge vor Fibonacci  7

3.2.2.  Liber Abaci: Die Kaninchenaufgabe.  8

3.3.  Mathematische Definition der Fibonaccizahlen.  8

3.3.1.  Allgemeine Definition.  8

3.3.2.  Die Formel von Binet  9

3.4.  Mathematische Besonderheiten.  9

3.5.  Die Fibonaccizahlen und der Goldene Schnitt  10

3.5.1.  Mathematischer Zusammenhang.  10

3.5.2.  Fibonaccizahlen in der Natur  11

3.5.3.  Fibonaccizahlen in der Kunst  11

3.5.4.  Fibonaccizahlen in der Architektur  12

3.5.5.  Fibonaccizahlen in der Musik  13

3.6.  Praktische Anwendungen der Fibonaccizahlen.  13

3.7.  Zusammenhänge zwischen Fibonacci- und Lucaszahlen.  14

4.  Die Ulamzahlen.  15

4.1.  Stanislaw Ulam: Leben und Werk.  15

4.2.  Mathematische Definition der Ulamzahlen.  15

4.3.  Mathematische Besonderheiten.  16

5.  Zusammenfassung und Ausblick  17

6.  Literaturverzeichnis.  18

7.  Abbildungsverzeichnis  19

- 3 - 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.

- 4 - 2.Die Lucaszahlen

2.1. Édouard Lucas: Leben und Werk

„Die (…) Folge trägt ihren Namen zu Ehren des französischen Zahlentheoretikers Édouard Lucas“ ¹ . Dieser wurde am 4. April 1842 als François Édouard Anatole Lucas in Amiens in Frankreich geboren. Nachdem er im Deutsch-Französischen Krieg ² 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 einer Mersenne-Zahl 3 um eine Primzahl handelt oder nicht. ⁴ Des Weiteren erfand und vermarktete er ein bekanntes mathematisches Knobelspiel mit Namen Die 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 l n = l n-1 + l n-2 definiert ist, wobei n eine natürliche Zahl und l n 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 l 1 = 1 und l 2 = 3, bzw. l 0 = 2 und l 1 = 1 festgelegt. Somit sind die ersten Glieder der Lucasfolge: (2,) 1, 3, 4, 7, 11, 18, 29, 47, 76, … ⁶ Darüber hinaus gibt es weitere Folgen, die ebenso Lucasfolgen genannt werden: die allgemeinen Lucasfolgen. Sie lauten, für :

¹ Lausch, H. (2009): Fibonacci und die Folge(n), Seite 3.

² Deutsch-Französischer Krieg: 1870-1871.

^{3 Mersenne-Zahlen: M} n = 2 ⁿ -1.

⁴ Siehe Kapitel 2.4.1 Der Lucas-Lehmer-Test.

⁵ 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.

⁶ Vgl. Lausch (2009), S. 3.

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 Lucaszahlen modulo 8 betrachtet; 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: l 0 = l 12 = l 24 = l 36 = l (n*12) = 2 (mod 8), l 1 = l 13 = l 25 = l 37 = l (n*12)+1 = 1 (mod 8), l 2 = l 14 = l 26 = l 38 = l (n*12)+2 = 3 (mod 8), usw.

Da sich die verbleibenden Restbeträge immer nach zwölf Lucaszahlen wiederholen und dabei l n = 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 l 1 = 1 und l 3 = 4. ⁹ Der Beweis hierfür ist in dem 2009 erschienenen Buch Fibonacci und die Folge(n) von Huberta Lausch ab Seite 99 nachzulesen. Darüber hinaus werden darin auch weitere Besonderheiten der Lucasfolge dargelegt.

⁷ Vgl. Lausch (2009), S. 163f.

⁸ Vgl. Lausch (2009), S. 75.

⁹ Vgl. Lausch (2009), S. 99.

- 6 - 2.4.Praktische Anwendungen der Lucaszahlen

2.4.1. Der Lucas-Lehmer-Test

Mit Hilfe des sogenannten Lucas-Lehmer-Tests kann geprüft werden, ob es sich bei einer Mersenne-Zahl 10 um eine Primzahl handelt. Der Test beruht auf den oben genannten allgemeinen Lucasfolgen und deren Eigenschaften. Er wurde 1930 von dem Mathematiker Derrick Lehmer entwickelt und funktioniert folgendermaßen: ¹¹ „Sei p ungerade. Ferner sei die Funktion S(k) definiert durch S(1)= 4; S(k +1)= S(k) ² -2. Dann gilt: M p = 2 p -1 ist genau dann eine Primzahl, wenn S(p -1) durch M p teilbar 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 sogenannte asymmetrische Verschlüsselung. Die Besonderheit bei dieser Verschlüsselungstechnik besteht darin, dass es hier anstatt eines Schlüssels zwei Schlüssel gibt: den privaten und 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

^{10 Mersenne-Zahlen: M} n = 2 ⁿ -1.

¹¹ 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.

¹² Ebd.

¹³ 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.

¹⁴ 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.