Kap 3.4
Die Fermatzahlen F_n

Von Pierre de Fermat (1601-1665) haben wir ja schon gelegentlich gehört. Da wir in den nächsten Kapiteln besonders viel über seine Entdeckungen sprechen werden, hier ein paar Zeilen zu seiner Biographie:
Fermat bekleidete als Jurist und Magistratsmitglied viele öffentliche Ämter in Toulouse. Er veröffentlichte keine seiner Entdeckungen, aber er war ein fleißiger Briefschreiber. Seine Korrespondenz mit Renee Descartes (1596 - 1650) und B. Pascal (1623 -1662) enthält aber viele der von ihm gefundenen Theoreme, die er aber grundsätzlich ohne Beweis mitteilte. Erst sein Sohn Samuel veröffentlichte nach seinem Tode den Nachlaß Fermats, in dem sich dann auch eine Vielzahl von Beweisen fand. Fermat arbeitete als Autodidakt auf dem Gebiete der Zahlentheorie, die damals durch Neuveröffentlichung der griechischen Klassiker (die wiederum durch die Mauren in arabischen Übersetzungen nach Spanien gekommen waren - die Römer hatten ja nachhaltig dafür gesorgt, daß die Klassiker nicht direkt zugänglich wurden. Speziell handwelt es sich um die Werke von Diophant, den wir ja auch schon kennengelernt haben.) gerade neu entdeckt wurde. Außerdem schuf er mit seinen Arbeiten die Grundlagen der Differentialrechnung und Wahrscheinlichkeitsrechnung. Gleichzeitig mit Descartes, aber unabhängig von ihm, entwarf Fermat die Idee des Koordinatensystems und begründete damit die Analytische Geometrie.

Fermat untersuchte unter anderem die Folge der Primzahlen 2, 3, 5, 7, 11.... Er fragte sich, ob es auch unter den Zahlen 2^k+1 (3, 5, 9, 17, ..) unendlich viele Primzahlen gebe. Wenn man nun die Exponenten der ersten Primzahlen unter den obigen Zahlen aufschreibt (1, 2, 4 ), so fällt auf, daß es sich dabei um Zweierpotenzen handelt. Fermat bewies nun: 2^k+1 prim Þk=2ⁿ.
(Idee: Wenn k keine Zweierpotenz ist, so hat k einen ungeraden Teiler m (warum?). Es sei also k=s·m. Dann gilt2^k+1=2^s·m+1=(2^s)^m+1^m. Dieser Term ist aber nach Satz 1.2 (F3) durch 2^s+1 teilbar und damit nicht prim.)

In einem Brief an Pascal (1623-1662) stellte Fermat im Jahre 1654 daher die Vermutung auf, daß die Zahlen F_n:= (die wir zu Ehren Fermats nun die "Fermatzahlen" nennen) für alle n³ 0 prim seien. Fermat konnte diese Vermutung mangels Taschenrechners nur bis n=4 prüfen - und hatte soweit recht, wie die folgende Tabelle zeigt:

Schon beim Überprüfen von F₄ hat man ohne Primzahltabelle oder Rechner einige Mühe; jedoch erweist sich diese Zahl als Primzahl. Es dauerte beinahe 100 Jahre, bis Euler 1732 für F₅=4.294.967.297 die Zerlegung 641·6.700.417 angeben konnte - die Fermatsche Vermutung war also falsch. 1880 gab Landry für F₆ an:
F₆=18.446.744.073.709.551.617=274.177 · 67.280.421.310.721 (selbstverständlich zwei Primfaktoren!). Übrigens ist F₆-2 die Anzahl der Reiskörner in der berühmten Schachbrettaufgabe. Wie schon die wenigen Beispiele zeigen, werden die Fermatzahlen schnell sehr groß, wie man aus lg(F_n+1)»2ⁿ⁺¹·lg2=2·2ⁿ·lg2=2·lg =2·lg(F_n) sieht.

AUFGABE 3.29
a) Berechne die Länge der Fermatzahlen F_n für n=8,9,10,15,20.
b) Berechne die Länge von F₇₃. Wie viele km lang ist diese Zahl, wenn man eine Ziffer pro mm schreibt? Berechne die Zeit, die das Lichtbraucht, um vom Anfang bis zum Ende dieser Zahl zu kommen. (Lichtgeschwindigkeit: ca. 300.000 km pro Sekunde)
c) Nimmt man an, eine Bibliothek habe 1Million Bücher mit je 1000 Seiten, von denen jede 100 Zeilen mit je 100 Ziffern faßt. Wie viele dieser Bibliotheken brauchte man, um die Zahl F₇₃ auszuschreiben?

Wie man aus Aufgabe 3.23 ersieht, ist F₇₃ unvorstellbar groß. Wir werden in den folgenden Abschnitten trotzdem die letzten drei Stellen von F₇₃ ausrechnen. Dazu werden wir zwei schöne Hilfssätze herleiten, für die wir wiederum etwas mehr über die binomischen Formeln wissen müssen.

Jeder kennt schon (a+b)⁰=1, (a+b)¹=a+b und (a+b)²=a²+2ab+b². Aber wie geht´s weiter?

(a+b)³=(a+b)²(a+b)=(a²+2ab+b²)(a+b)
       = a³+2a²b+ab²+ a²b+2ab²+b³
       = a³+3a²b+3ab²+b³

Schaut man sich einmal an, wie die Koeffizienten zustande kommen, so erkennt man (vielleicht) ein System, welches wir allgemein untersuchen wollen. Dazu benennen wir den Koeffizienten von a^n-rb^r in (a+b)ⁿ mit k_n,r und berechnen mit diesen Bezeichnungen (a+b)ⁿ⁺¹:

(a+b)ⁿ⁺¹=(a+b)ⁿ(a+b)
=(k_n,0aⁿ + k_n,1a^n-1b + k_n,2a^n-2b² +...+ k_n,n-1ab^n-1 + k_n,nbⁿ)(a+b)
= k_n,0aⁿ⁺¹ + k_n,1aⁿb + k_n,2a^n-1b² +...+ k_n,n-1a²b^n-1 + k_n,nabⁿ
 + k_n,0aⁿb + k_n,1a^n-1b² +...............+ k_n,n-1abⁿ + k_n,nbⁿ⁺¹
= k_n,0aⁿ⁺¹+(k_n,0+k_n,1)aⁿb+(k_n,1+k_n,2)a^n-1b²+...........+(k_n,n-1+k_n,n)abⁿ+k_n,nbⁿ⁺¹
= k_n+1,0aⁿ⁺¹ + k_n+1,1aⁿb + k_n+1,2a^n-1b²+...........+ k_n+1,nabⁿ+k_n+1,n+1bⁿ⁺¹

Es ergibt sich also das typische Bildungsgesetz: k_n+1,i=k_n,i-1+k_n,i  (B1)
Berücksichtigt man noch: k_n,0=k_n,n=1  (B2), so ergibt sich das unter dem Namen "Pascalsches Dreieck" bekannte Schema (nach dem oben erwähnten Blaise Pascal benannt, dem als dem Erfinder der ersten funktionstüchtigen Rechenmaschine auch die Programmiersprache PASCAL gewidmet ist - jedoch nicht von diesem gefunden, wie wesentlich ältere Literatur aus China und Indien belegt). Dazu werden die Koeffizienten der binomischen Entwicklungen beginnend mit dem Exponenten 0 in ein dreieckiges Schema geschrieben, das nach dem oben hergeleiteten Gesetz weiterentwickelt wird:

Dabei wird jede Zeile nach (B2) mit 1 begonnen und beendet, während eine innere Zahl nach (B1) durch Addition der beiden schräg über ihr stehenden Zahlen der vorangegangenen Zeile gebildet wird.

AUFGABE 3.30
Erweitere das Pascalsche Dreieck bis n=10. Berechne dann (a+b)⁹ und (a+b)¹⁰. Berechne auch (3a-2b)⁴ und (x²-y)³.

AUFGABE 3.31
Bestätige an drei Beispielen die beiden Regeln für des Pascalsche Dreieck:
a) Die Summe der Glieder der n-ten Zeile ist 2ⁿ.
b) Addiert man die ersten m Zahlen einer Diagonalreihe von links oben nach rechts unten, so erhält man die m-te Zahl in der auf die zuletzt addierte Zahl folgenden Zeile.

Die beiden Gesetze (B1) und (B2) sind äußerst umständlich zu gebrauchen, wenn man die Koeffizienten in einer binomischen Entwicklung höheren Grades berechnen. Wir führen dazu jetzt neue "Zahlen" ein, von denen wir zeigen werden, daß sie ebenfalls den Gesetzen (B1) und (B2) gehorchen und damit identisch zu den k_n,i sind.

DEFINITION 3.2
Für nÎ N gelte
n!:=1·2·3·4·5···(n-1)·n (gelesen n-Fakultät)
1!:=1 0!:=1

Beispiele:
5!=5·4·3·2·1=120
8!=8·7·6·5·4·3·2·1=8·7·6·5!=336·120=40320

DEFINITION 3.3
Die Zahlen für n,kÎ N₀ mit n³k heißen "Binomialkoeffizienten".

Beispiele:

AUFGABE 3.32
Berechne: , und

AUFGABE 3.33
Beweise, daß gilt: und

Die Binomialkoeffizienten erfüllen also die Eigenschaften des Pascalschen Dreiecks - wir können es auch so schreiben:

Damit ergibt sich für die binomischen Formeln:
(a+b)²=a²+ ab+ b² oder (a+b)³=a³+ a²b+ ab²+ b³

oder allgemein: (a+b)ⁿ=aⁿ+ a^n-1b+ a^n-2 b²+...+ ab^n-1+ bⁿ

oder noch kürzer und einprägsamer:

(Binomische Formel) (a+b)ⁿ=

Diese Formel unter Benutzung der Binomialkoeffizienten hat den Vorteil, daß man auch für große n leicht die zugehörigen Koeffizienten direkt berechnen kann, ohne wie vorher beim Pascalschen Dreieck alle Zeilen bis zum gewünschten n aufschreiben zu müssen. So errechnet sich z.B. der Koeffizient von a²⁰b⁵ in (a+b)²⁵ als .

AUFGABE 3.34
Berechne die Koeffizienten der angegebenen Glieder in den angegebenen Entwicklungen:
a) x¹³y⁷ in (x-y)²⁰    b) r¹⁴s¹² in (r²+s)¹⁹    c) a⁵b³ in (2a-3b)⁸

AUFGABE 3.35
a) Bestätige die folgende Formel für n=7 und m=3 (n=6, m=5):
b) Bestätige für n= 5 und n=8:
c) Zeige:
d) Zeige:

AUFGABE 3.36
Beweise: Ist p prim, so ist vollkommen, wenn 2^p-1 prim ist.

AUFGABE 3.37
Zeige, daß aⁿº1 mod a-1 für alle a,nÎ N. (Tip: aⁿ=(a-1+1)ⁿ=....)

Nachdem wir nun die Binomischen Formeln "im Griff" haben, leiten wir zwei Sätze über Endziffern her:

EZS 1
Für alle nÎN gilt: n²º n²² mod 100 (d.h. sie stimmen in den letzten beiden Ziffern überein).

AUFGABE 3.38
Überprüfe den Satz an einigen Beispielen. Berechne dazu:
a) 79², 79³, 79¹², 79¹³, 79¹⁵, 79²⁰, 79²¹, 79²² mod 100
b) 136², 136¹², 136²² mod 10 c) 122², 122³, 122¹², 122¹³, 122²² mod 100

Beweis: Wir wollen zeigen: n²²º n² mod 100 Û100ï n²²-n² Û 2²× 5²ï n²(n¹⁰+1)(n¹⁰-1) (*)
Um die letzte Behauptung zu zeigen, überlegen wir und zunächst:
Die letzen beiden Ziffern von m¹⁰ hängen nur von der Einerziffer von m ab.
Es sei m=10a+b. Dann gilt m¹⁰=(10a+b)¹⁰=
= b¹⁰ + 100ab⁹+...
Der zweite Summand und erst recht alle weiteren enthalten wegen (10a)ⁱ mit i>1 den Faktor 100 und sind deshalb wegen ³ 1 alle größer als 100, d.h. sie haben keinen Einfluß auf die letzten beiden Ziffern. Wie behauptet, ist also alleine die Einerziffer b entscheidend. Wir wollen nun die drei Faktoren von (*) daraufhin untersuchen, welche Endziffern sie in Abhängigkeit von der Einerziffer von n hinterlassen. Dazu sehen wir uns die folgende Tabelle an:

(Anmerkung: ist die EZ von n gerade, so gilt 2ï n, also 4ï n²)

FOLGERUNG aus EZS 1: Für k>22 gilt: a^k=a^22+r=a^22× a^rº a^2× a^r=a^r+2=a^k-20. Man kann also im Exponenten wiederholt 20 abziehen, solange man noch mindestens 2 überläßt.

AUFGABE 3.39
Berechne vorteilhaft: 17⁴⁵, 39³⁵⁶, 223⁴⁶⁹, 2117⁶⁶⁷ mod 100.

Wir beweisen nun einen zweiten schönen Satz, der etwas über die letzten drei Stellen einer Zahl aussagt:

EZS 2
Für alle nÎN gilt: n¹⁰³º n³ mod 1000

Beweis: n¹⁰³º n³ mod 1000 Û1000ï n¹⁰³-n³ Û2³· 5³ïn³(n⁵⁰+1)(n⁵⁰-1) (**)
Zunächst beweisen wir dafür:
Die letzten drei Ziffern von m⁵⁰ hängen nur von der Einerziffer von m ab.
Es sei m=10a+b. Dann gilt
m⁵⁰=(10a+b)⁵⁰=
= b⁵⁰ + 500ab⁴⁹ + 1225· 100a²b⁴⁸+ (Rest)
= b⁵⁰ + 500ab⁴⁸(b+245a)+ (Rest) (***)
Wir müssen nun nachweisen, daß alle Summanden von (***) bis auf den ersten den Faktor 1000 enthalten und damit für die letzten drei Stellen nicht mehr zuständig sind.
Jeder Summand im Rest enthält (10a)ⁱ für i³ 3 und damit den Faktor 1000. Also müssen wir uns noch mit dem Summanden 500ab⁴⁸(b+245a) beschäftigen. Ist eine der beiden Zahlen a oder b gerade, so enthält sicher 500ab⁴⁸ den Faktor 1000. Sind aber a und b ungerade, so ist b+245a gerade und der Faktor 1000 ist mit dem Koeffizienten 500 gesichert. Also ist auch der zweite Summand von (***) ein Vielfaches von 1000 und damit b⁵⁰ alleine für die drei letzten Stellen zuständig. Wir untersuchen nun wie beim Beweis von EZS 1, wie die Faktoren 2³ und 5³ in der Zerlegung (**) von n¹⁰³-n³ in Abhängigkeit von der Einerziffer von n auftreten:

FOLGERUNG aus EZS 2: Für k>103 gilt: a^k=a^103+r=a¹⁰³· a^rº a³·a^r=a^r+3=a^k-100. Man kann also im Exponenten wiederholt 100 abziehen, solange man noch mindestens der Exponent 3 überbleibt.

Damit kommen wir nun zu der angepeilten Aufgabe: Man bestimme die letzten drei Ziffern von F₇₃= .

2⁷³=2^3·20+13º 2¹³=2¹⁰·2³º24· 8º92 mod 100 Þ2⁷³=100k+92
Þ=2^100k+92 º2⁹²=(2¹⁰)⁹· 2²º24⁹·4=(24³)³· 4º824³·4º896 mod 1000
Þ F₇₃º897 mod 1000

AUFGABE 3.40
Berechne die letzten drei Ziffern von
a) 8⁹⁹⁷+13²⁸¹    b) 23⁹⁰⁰¹-11¹⁹⁷
c) (12 hoch 3 hoch 45)    d) (421 hoch 7 hoch 107)

Fermats Vermutung bezüglich der Nichtzerlegbarkeit der Fermatzahlen war bekanntlich falsch. Heutzutage vermutet man eher, daß alle Fermatzahlen bis auf die ersten fünf zerlegbar sind. Es sind aber erst für relativ wenige Fermatzahlen konkrete Nachweise der Zerlegbarkeit oder gar die Zerlegungen selbst bekannt. Nach Scheid sind bis 1990 F₂₂, F₂₄ und F₂₈ die kleinsten Fermatzahlen, von denen man noch keinen Zerlegbarkeitsbeweis kennt. Dagegen ist bekannt, daß F₂₃₄₇₁ den (kleinsten) Primfaktor 10· 2²³⁴⁷²+1 hat. Auch F₁₉₄₅ ist nachweislich zerlegbar. Wegen lg(lg(F₁₉₄₅))»lg(2¹⁹⁴⁵·lg2)=1945·lg2+lg(lg2) »584,98 hat schon die Zahl, die die Länge von F₁₉₄₅ 585 Stellen!

AUFGABE 3.41
Berechne die letzten drei Stellen von F₁₉₄₅.(ebenso von M_216.091)

Zusätzliche Aufgaben zum Thema Fermatzahlen

1) Zeige: Für n>0 gilt F_nº5 mod 12.

2) Zeige: F_nï . Tip: (a-b)ï (aⁿ-bⁿ)

3) Gib eine Zerlegung von an. (Tip: man kann Aufgabe 1 benutzen)

4) Zeige: F_n=F₀·F₁·F₂···F_n-1+2

5) Zeige mit Aufgabe 4: Zwei verschiedene Fermatzahlen sind teilerfremd.
Warum hat daher für n>1 mindestens zwei verschiedene Primteiler?

6) Zeige: Für kÎ N gilt: 2^k+1 ist prim, wenn k=2ⁿ für nÎ N₀ ist.

1971 gaben J.Brillhart und M.A.Morrison mit einem nur 5 Zeilen langen (!) Artikel im Bulletin of the American Mathematical Society Nr.77 bekannt, daß sie für F₇ die Primfaktorzerlegung gefunden hätten. Der kleinere der Faktoren hat 17 Ziffern.

Einen weitern erstaunlichen Satz in diesem Dunstkreis bewies der junge K.F.Gauß (1777 - 1855) im Jahre 1796:
Ein regelmäßiges n-Eck ist genau dann mit Zirkel und Lineal konsruierbar, wenn n=2^r· f₁···f_s ist, wobei die f_i paarweise verschiedenen Fermatprimzahlen sind.
Damit finden sich als erste n: 2,3,4,5,6,8,10,12,15,16,17,20,24,30,32,34,40,48,51,60 ...

Download Kap3_3 (34 KB)

Copyright © Michael Dorner, Januar 2001.