Kap 3.4
Die Fermatzahlen Fn

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 2k+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: 2k+1 prim Þk=2n.
(Idee: Wenn k keine Zweierpotenz ist, so hat k einen ungeraden Teiler m (warum?). Es sei also k=s·m. Dann gilt2k+1=2s·m+1=(2s)m+1m. Dieser Term ist aber nach Satz 1.2 (F3) durch 2s+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 Fn:= (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:

n 0 1 2 3 4
2n 1 2 4 8 16
Fn 3 5 17 257 65537

Schon beim Überprüfen von F4 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 F5=4.294.967.297 die Zerlegung 641·6.700.417 angeben konnte - die Fermatsche Vermutung war also falsch. 1880 gab Landry für F6 an:
F6=18.446.744.073.709.551.617=274.177 · 67.280.421.310.721 (selbstverständlich zwei Primfaktoren!). Übrigens ist F6-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(Fn+1)»2n+1·lg2=2·2n·lg2=2·lg =2·lg(Fn) sieht.

AUFGABE 3.29
a) Berechne die Länge der Fermatzahlen Fn für n=8,9,10,15,20.
b) Berechne die Länge von F73. 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 F73 auszuschreiben?

Wie man aus Aufgabe 3.23 ersieht, ist F73 unvorstellbar groß. Wir werden in den folgenden Abschnitten trotzdem die letzten drei Stellen von F73 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)0=1, (a+b)1=a+b und (a+b)2=a2+2ab+b2. Aber wie geht´s weiter?

(a+b)3=(a+b)2(a+b)=(a2+2ab+b2)(a+b)
       = a3+2a2b+ab2+ a2b+2ab2+b3
       = a3+3a2b+3ab2+b3

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 an-rbr in (a+b)n mit kn,r und berechnen mit diesen Bezeichnungen (a+b)n+1:

(a+b)n+1=(a+b)n(a+b)
=(kn,0an + kn,1an-1b + kn,2an-2b2 +...+ kn,n-1abn-1 + kn,nbn)(a+b)
= kn,0an+1 + kn,1anb + kn,2an-1b2 +...+ kn,n-1a2bn-1 + kn,nabn
 + kn,0anb + kn,1an-1b2 +...............+ kn,n-1abn + kn,nbn+1
= kn,0an+1+(kn,0+kn,1)anb+(kn,1+kn,2)an-1b2+...........+(kn,n-1+kn,n)abn+kn,nbn+1
= kn+1,0an+1 + kn+1,1anb + kn+1,2an-1b2+...........+ kn+1,nabn+kn+1,n+1bn+1

Es ergibt sich also das typische Bildungsgesetz: kn+1,i=kn,i-1+kn,i  (B1)
Berücksichtigt man noch: kn,0=kn,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:

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10  10  5  1
1  6  15  20  15  6  1

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)9 und (a+b)10. Berechne auch (3a-2b)4 und (x2-y)3.

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 2n.
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 kn,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Î N0 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:

  
    
      
   usw.

Damit ergibt sich für die binomischen Formeln:
(a+b)2=a2+ ab+ b2 oder (a+b)3=a3+ a2b+ ab2+ b3

oder allgemein: (a+b)n=an+ an-1b+ an-2 b2+...+ abn-1+ bn

oder noch kürzer und einprägsamer:

(Binomische Formel) (a+b)n=

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 a20b5 in (a+b)25 als .

AUFGABE 3.34
Berechne die Koeffizienten der angegebenen Glieder in den angegebenen Entwicklungen:
a) x13y7 in (x-y)20    b) r14s12 in (r2+s)19    c) a5b3 in (2a-3b)8

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 2p-1 prim ist.

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

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: n2º n22 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) 792, 793, 7912, 7913, 7915, 7920, 7921, 7922 mod 100
b) 1362, 13612, 13622 mod 10 c) 1222, 1223, 12212, 12213, 12222 mod 100

Beweis: Wir wollen zeigen: n22º n2 mod 100 Û100ï n22-n2 Û 22× 52ï n2(n10+1)(n10-1) (*)
Um die letzte Behauptung zu zeigen, überlegen wir und zunächst:
Die letzen beiden Ziffern von m10 hängen nur von der Einerziffer von m ab.
Es sei m=10a+b. Dann gilt m10=(10a+b)10=
= b10 + 100ab9+...
Der zweite Summand und erst recht alle weiteren enthalten wegen (10a)i 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:

EZ von n Endzff von n10 ...von n10+1 ..von n10-1 ...von n2 4·25ïn22-n2
0 ...00 ...01 ...99 ...00 100ïn2
1 ...01 ...02 ...00 ...1 100ïn10-1
2 ...24 ...25 ...23 ...4 25ïn10+1Ù 4ïn2
3 ...49 ...50 ...48 ...9 25ïn10+1Ù 4ïn10-1
4 ...76 ...77 ...75 ...6 25ïn10-1Ù 4ïn2
5 ...25 ...26 ...24 ...5 25ïn2 Ù4ïn10-1
6 ...76 ...77 ...75 ...6 25ïn10-1Ù 4ïn2
7 ...49 ...50 ...48 ...9 25ïn10+1Ù 4ïn10-1
8 ...24 ...25 ...23 ...4 25ïn10+1Ù 4ïn2
9 ...01 ...02 ...00 ...1 100ïn10-1

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

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

AUFGABE 3.39
Berechne vorteilhaft: 1745, 39356, 223469, 2117667 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: n103º n3 mod 1000

Beweis: n103º n3 mod 1000 Û1000ï n103-n3 Û23· 53ïn3(n50+1)(n50-1) (**)
Zunächst beweisen wir dafür:
Die letzten drei Ziffern von m50 hängen nur von der Einerziffer von m ab.
Es sei m=10a+b. Dann gilt
m50=(10a+b)50=
= b50 + 500ab49 + 1225· 100a2b48+ (Rest)
= b50 + 500ab48(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)i für i³ 3 und damit den Faktor 1000. Also müssen wir uns noch mit dem Summanden 500ab48(b+245a) beschäftigen. Ist eine der beiden Zahlen a oder b gerade, so enthält sicher 500ab48 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 b50 alleine für die drei letzten Stellen zuständig. Wir untersuchen nun wie beim Beweis von EZS 1, wie die Faktoren 23 und 53 in der Zerlegung (**) von n103-n3 in Abhängigkeit von der Einerziffer von n auftreten:

EZ von n Endzff von n10 ...von n50+1 ..von n50-1 ...von n3 8·125ïn103-n3
0 ...000 ...01 ...99 ...000 1000ïn50
1 ...001 ...002 ...000 ...1 1000ïn50-1
2 ...624 ...625 ...623 ...8 125ïn50+1Ù 8ïn3
3 ...249 ...250 ...248 ...7 125ïn50+1Ù 8ïn50-1
4 ...376 ...377 ...375 ...4 125ïn50-1Ù 8ïn3
5 ...625 ...626 ...624 ...5 125ïn3Ù 4ïn50-1 Ù 2ïn50+1
6 ...376 ...377 ...375 ...6 125ïn50-1Ù 8ïn3
7 ...249 ...250 ...248 ...3 125ïn50+1Ù 8ïn50-1
8 ...624 ...625 ...623 ...2 125ïn50+1Ù 8ïn3
9 ...001 ...002 ...000 ...9 1000ïn50-1

FOLGERUNG aus EZS 2: Für k>103 gilt: ak=a103+r=a103· arº a3·ar=ar+3=ak-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 F73= .

273=23·20+13º 213=210·23º24· 8º92 mod 100 Þ273=100k+92
Þ=2100k+92 º292=(210)9· 22º249·4=(243)3· 4º8243·4º896 mod 1000
Þ F73º897 mod 1000

AUFGABE 3.40
Berechne die letzten drei Ziffern von
a) 8997+13281    b) 239001-11197
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 F22, F24 und F28 die kleinsten Fermatzahlen, von denen man noch keinen Zerlegbarkeitsbeweis kennt. Dagegen ist bekannt, daß F23471 den (kleinsten) Primfaktor 10· 223472+1 hat. Auch F1945 ist nachweislich zerlegbar. Wegen lg(lg(F1945))»lg(21945·lg2)=1945·lg2+lg(lg2) »584,98 hat schon die Zahl, die die Länge von F1945 585 Stellen!

AUFGABE 3.41
Berechne die letzten drei Stellen von F1945.(ebenso von M216.091)





Zusätzliche Aufgaben zum Thema Fermatzahlen

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

2) Zeige: Fnï . Tip: (a-b)ï (an-bn)

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

4) Zeige: Fn=F0·F1·F2···Fn-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: 2k+1 ist prim, wenn k=2n für nÎ N0 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 F7 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=2r· f1···fs ist, wobei die fi 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 ...

DownloadDownload Kap3_3 (34 KB)
Inhaltsverzeichnis vorherige Seite zum Seitenanfang naechste Seite Kontakt


Copyright © Michael Dorner, Januar 2001.