Fermat-Zahl

Beweis durch Widerspruch: Man führt die Annahme, dass das zu Beweisende falsch sei, zu einem Widerspruch.

Annahme: ${\displaystyle k>0}$ und ${\displaystyle 2^{k}+1}$ ist prim und die Hochzahl ${\displaystyle k}$ hat einen ungeraden Teiler ${\displaystyle c>1}$.

Dann gilt

${\displaystyle 2^{k}+1=2^{{\frac {k}{c}}\cdot c}+1=(2^{\frac {k}{c}})^{c}+1^{c}}$

mit einer ganzen Zahl ${\displaystyle k/c}$. Nach Annahme ist ${\displaystyle c}$ ungerade, also ist diese Summe bekanntlich durch die Summe ${\displaystyle 2^{\frac {k}{c}}+1}$ der beiden Basen teilbar:

${\displaystyle 2^{k}+1=(2^{\frac {k}{c}})^{c}+1^{c}=(2^{\frac {k}{c}}+1)\cdot \sum _{j=0}^{c-1}(-1)^{j}\cdot (2^{\frac {k}{c}})^{j}}$

Weil die Zahl ${\displaystyle 2^{k}+1}$ prim ist, muss ihr Teiler ${\displaystyle 2^{\frac {k}{c}}+1}$ gleich 1 oder gleich ${\displaystyle 2^{k}+1}$ sein. Aber in Widerspruch dazu ist ${\displaystyle 2^{\frac {k}{c}}+1}$ (wegen ${\displaystyle 2^{\frac {k}{c}}>0}$) größer als 1 und (wegen ${\displaystyle k>0\Rightarrow k/c<k}$) kleiner als ${\displaystyle 2^{k}+1}$. Die Annahme, dass sowohl ${\displaystyle 2^{k}+1}$ prim ist als auch, dass ${\displaystyle k}$ positiv ist und einen ungeraden Teiler ${\displaystyle c>1}$ hat, muss daher fallengelassen werden: ${\displaystyle 2^{k}+1}$ kann nur prim sein, wenn ${\displaystyle k}$ gleich 0 oder gleich einer Zweierpotenz ${\displaystyle 2^{n}}$ mit ${\displaystyle n\geq 0}$ ist, was zu zeigen war. ${\displaystyle \Box }$

Es gibt keine sinnvolle Methode, sich die Menge an Papier, die man benötigt sie aufzuschreiben – oder gar die Zahl selber – vorzustellen: Selbst mit den hypothetisch kleinsten Teilchen aufgeschrieben, ist das Universum spätestens mit F₆₁₅ vollgeschrieben und für jeden weiteren Schritt bis F_18233954 würde sich der Platz zum Aufschreiben jeweils verdoppeln. Nur hat man mit F₆₁₅ ja quasi damit noch nicht mal richtig angefangen! Ein wissenschaftlicher Taschenrechner würde eine etwa 27 Kilometer lange Zeile oder alternativ eine 27 Meter mal 10 Meter große Tafel allein für das Anschreiben der Anzahl der Stellen, also von 10^5488966, als Dezimalzahl benötigen.

Es wurden somit bisher 352 Primfaktoren von Fermat-Zahlen mit Computern gefunden (Stand: 30. Juli 2023).

Zwei der vier Beweise funktionieren mittels vollständiger Induktion. Man zeigt, dass die Behauptungen für den Anfang gelten (Induktionsanfang), nimmt an, dass die Behauptung für ${\displaystyle n}$ gilt (Induktionsvoraussetzung) und beweist, dass die Behauptung dadurch auch für ${\displaystyle n+1}$ gelten muss (Induktionsschluss).

Beweis der ersten Behauptung: ${\displaystyle F_{n}=(F_{n-1}-1)^{2}+1}$ für ${\displaystyle n\geq 1}$

Der Beweis funktioniert direkt.

${\displaystyle F_{n}=2^{2^{n}}+1=2^{2\cdot 2^{n-1}}+1=(2^{2^{n-1}})^{2}+1=({\color {red}2^{2^{n-1}}+1}-1)^{2}+1=({\color {red}F_{n-1}}-1)^{2}+1}$, was zu zeigen war. ${\displaystyle \Box }$

Beweis der zweiten Behauptung: ${\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}\cdot F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-2}}$ für ${\displaystyle n\geq 2}$

Der Beweis funktioniert mittels vollständiger Induktion.

Induktionsanfang:

${\displaystyle 17=F_{2}=F_{1}+2^{2^{2-1}}\cdot F_{0}=5+2^{2^{1}}\cdot 3=5+2^{2}\cdot 3=5+4\cdot 3=17}$

${\displaystyle 257=F_{3}=F_{2}+2^{2^{3-1}}\cdot F_{0}\cdot F_{1}=17+2^{4}\cdot 3\cdot 5=17+16\cdot 3\cdot 5=17+240=257}$

Induktionsvoraussetzung: ${\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}\cdot F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-2}}$ bzw. umgeformt ${\displaystyle F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-2}={\frac {F_{n}-F_{n-1}}{2^{2^{n-1}}}}}$

Induktionsschluss: zu zeigen: ${\displaystyle F_{n+1}=F_{n}+2^{2^{n}}\cdot F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-1}}$

${\displaystyle {\begin{array}{rcll}F_{n+1}&=&(F_{n}-1)^{2}+1&{\text{(erste obige Behauptung)}}\\&=&{\color {red}F_{n}}^{2}-2{\color {magenta}F_{n}}+1+1\\&=&({\color {red}F_{n-1}+2^{2^{n-1}}F_{0}F_{1}\ldots F_{n-2}})^{2}-2\cdot ({\color {magenta}F_{n-1}+2^{2^{n-1}}F_{0}F_{1}\ldots F_{n-2}})+2&{\text{(Induktionsvoraussetzung)}}\\&=&F_{n-1}^{2}+2\cdot 2^{2^{n-1}}F_{0}F_{1}\ldots F_{n-2}F_{n-1}+(2^{2^{n-1}})^{2}F_{0}^{2}F_{1}^{2}\ldots F_{n-2}^{2}-2F_{n-1}-2\cdot 2^{2^{n-1}}F_{0}F_{1}\ldots F_{n-2}+2\\&=&(F_{n-1}^{2}-2F_{n-1}+1)+1+2^{2^{n-1}}F_{0}F_{1}\ldots F_{n-2}\cdot (2F_{n-1}+2^{2^{n-1}}F_{0}F_{1}\ldots F_{n-2}-2)\\&=&{\color {magenta}(F_{n-1}-1)^{2}+1}+2^{2^{n}}F_{0}F_{1}\ldots F_{n-2}\cdot ({\frac {2}{2^{2^{n-1}}}}F_{n-1}+{\color {red}F_{0}F_{1}\ldots F_{n-2}}-{\frac {2}{2^{2^{n-1}}}})\\&=&{\color {magenta}F_{n}}+2^{2^{n}}F_{0}F_{1}\ldots F_{n-2}\cdot ({\frac {2}{2^{2^{n-1}}}}F_{n-1}+{\color {red}{\frac {F_{n}-F_{n-1}}{2^{2^{n-1}}}}}-{\frac {2}{2^{2^{n-1}}}})&{\text{(umgeformte Induktionsvoraussetzung)}}\\&=&F_{n}+2^{2^{n}}F_{0}F_{1}\ldots F_{n-2}\cdot {\frac {2F_{n-1}+F_{n}-F_{n-1}-2}{2^{2^{n-1}}}}\\&=&F_{n}+2^{2^{n}}F_{0}F_{1}\ldots F_{n-2}\cdot {\frac {{\color {red}F_{n-1}}+{\color {magenta}F_{n}}-2}{2^{2^{n-1}}}}\\&=&F_{n}+2^{2^{n}}F_{0}F_{1}\ldots F_{n-2}\cdot {\frac {{\color {red}2^{2^{n-1}}+1}+{\color {magenta}2^{2^{n}}+1}-2}{2^{2^{n-1}}}}&{\text{(Definition von Fermat-Zahlen)}}\\&=&F_{n}+2^{2^{n}}F_{0}F_{1}\ldots F_{n-2}\cdot {\frac {2^{2^{n-1}}+2^{2^{n}}}{2^{2^{n-1}}}}\\&=&F_{n}+2^{2^{n}}F_{0}F_{1}\ldots F_{n-2}\cdot {\frac {2^{2^{n-1}}\cdot (1+2^{2^{n-1}})}{2^{2^{n-1}}}}\\&=&F_{n}+2^{2^{n}}F_{0}F_{1}\ldots F_{n-2}\cdot ({\color {red}2^{2^{n-1}}+1})\\&=&F_{n}+2^{2^{n}}F_{0}F_{1}\ldots F_{n-2}\cdot {\color {red}F_{n-1}}&{\text{(Definition von Fermat-Zahlen)}}\end{array}}}$

Was zu zeigen war. ${\displaystyle \Box }$

Beweis der dritten Behauptung: ${\displaystyle F_{n}=F_{n-1}^{2}-2\cdot (F_{n-2}-1)^{2}}$ für ${\displaystyle n\geq 2}$

Der Beweis funktioniert direkt.

${\displaystyle {\begin{array}{rcll}F_{n}=2^{2^{n}}+1&=&2^{2\cdot 2^{n-1}}+2\cdot 2^{2^{n-1}}+1-2\cdot 2^{2^{n-1}}\\&=&(2^{2^{n-1}})^{2}+2\cdot 2^{2^{n-1}}+1-2\cdot 2^{2\cdot 2^{n-2}}\\&=&({\color {red}2^{2^{n-1}}+1})^{2}-2\cdot (2^{2^{n-2}})^{2}\\&=&{\color {red}F_{n-1}}^{2}-2\cdot (2^{2^{n-2}}+1-1)^{2}\\&=&F_{n-1}^{2}-2\cdot (F_{n-2}-1)^{2}\end{array}}}$

Was zu zeigen war. ${\displaystyle \Box }$

Beweis der vierten Behauptung: ${\displaystyle F_{n}=F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-1}+2}$ für ${\displaystyle n\geq 1}$

Der Beweis funktioniert mittels vollständiger Induktion.

Induktionsanfang:

${\displaystyle 5=F_{1}=F_{0}+2=3+2=5}$

${\displaystyle 17=F_{2}=F_{0}\cdot F_{1}+2=3\cdot 5+2=15+2=17}$

Induktionsvoraussetzung: ${\displaystyle F_{n}=F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-1}+2}$

Induktionsschluss: zu zeigen: ${\displaystyle F_{n+1}=F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n}+2}$

${\displaystyle {\begin{array}{rcll}F_{n+1}&=&(F_{n}-1)^{2}+1&{\text{(erste obige Behauptung)}}\\&=&{\color {red}F_{n}}^{2}-2{\color {magenta}F_{n}}+1+1\\&=&({\color {red}F_{0}F_{1}\ldots F_{n-1}+2})^{2}-2({\color {magenta}F_{0}F_{1}\ldots F_{n-1}+2})+2&{\text{(Induktionsvoraussetzung)}}\\&=&F_{0}^{2}F_{1}^{2}\ldots F_{n-1}^{2}+4F_{0}F_{1}\ldots F_{n-1}+4-2F_{0}F_{1}\ldots F_{n-1}-4+2\\&=&F_{0}^{2}F_{1}^{2}\ldots F_{n-1}^{2}+2F_{0}F_{1}\ldots F_{n-1}+2\\&=&F_{0}F_{1}\ldots F_{n-1}\cdot ({\color {red}F_{0}F_{1}\ldots F_{n-1}+2})+2\\&=&F_{0}F_{1}\ldots F_{n-1}\cdot {\color {red}F_{n}}+2&{\text{(Induktionsvoraussetzung)}}\end{array}}}$

Was zu zeigen war. ${\displaystyle \Box }$

Beweis der ersten Behauptung: ${\displaystyle F_{n}\equiv -1{\pmod {6}}}$

Der Beweis funktioniert direkt. Man startet mit einer bekannten richtigen Aussage und beweist das Gewünschte.

Eine weiter oben angegebene Eigenschaft besagt, dass ${\displaystyle F_{n}=F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-1}+2}$ gilt für ${\displaystyle n\geq 1}$. Somit gilt aber, weil ${\displaystyle F_{0}=3}$ ist:

${\displaystyle F_{n}+1=F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-1}+3=3\cdot F_{1}\cdot \ldots \cdot F_{n-1}+3=3\cdot (F_{1}\cdot \ldots \cdot F_{n-1}+1)}$.

Der Ausdruck ${\displaystyle F_{1}\cdot \ldots \cdot F_{n-1}}$ ist als Produkt von ungeraden Fermat-Zahlen selber ungerade. Addiert man 1 dazu, erhält man eine gerade Zahl. Also ist ${\displaystyle F_{n}+1}$ ein Produkt aus 3 und einer geraden Zahl und somit durch 6 teilbar. Es gibt also ein ${\displaystyle m\in \mathbb {N} }$ mit ${\displaystyle F_{n}+1=6m}$. Daher ist ${\displaystyle F_{n}}$ von der Form ${\displaystyle 6m-1}$, was zu zeigen war. ${\displaystyle \Box }$

Beweis der zweiten Behauptung: ${\displaystyle F_{n}\equiv 1{\pmod {4}}}$

${\displaystyle F_{n}=2^{2^{n}}+1=(2^{2})^{\frac {2^{n}}{2}}+1=4^{2^{n-1}}+1\equiv 1{\pmod {4}}}$, was zu zeigen war. ${\displaystyle \Box }$

Beweis der dritten Behauptung: ${\displaystyle F_{n}\equiv 2{\pmod {3}}}$

Der dritte Beweis funktioniert mit vollständiger Induktion:

Induktionsanfang:

${\displaystyle F_{1}=2^{2^{1}}+1=5=3\cdot 1+2\equiv 2{\pmod {3}}}$

${\displaystyle F_{2}=2^{2^{2}}+1=17=3\cdot 5+2\equiv 2{\pmod {3}}}$

Induktionsvoraussetzung: ${\displaystyle F_{n}=3\cdot k+2}$

Induktionsschluss: zu zeigen: ${\displaystyle F_{n+1}=3\cdot m+2}$ für ein ${\displaystyle m\in \mathbb {N} }$

${\displaystyle {\begin{array}{rcll}F_{n+1}&=&(F_{n}-1)^{2}+1&{\text{(erste Behauptung weiter oben)}}\\&=&{\color {red}F_{n}}^{2}-2{\color {magenta}F_{n}}+1+1\\&=&({\color {red}3k+2})^{2}-2\cdot ({\color {magenta}3k+2})+2&{\text{(Induktionsvoraussetzung)}}\\&=&9k^{2}+12k+4-6k-4+2\\&=&9k^{2}+6k+2\\&=&3\cdot (3k^{2}+2k)+2\\&=&3m+2&{\text{(mit }}m:=3k^{2}+2k{\text{)}}\end{array}}}$

Was zu zeigen war. ${\displaystyle \Box }$

Beweis der vierten Behauptung: ${\displaystyle F_{n}\equiv 7{\pmod {10}}}$

Der vierte Beweis funktioniert direkt:

Weiter oben wurde gezeigt, dass ${\displaystyle F_{n}=F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-1}+2}$ für ${\displaystyle n\geq 1}$ gilt. Daraus kann man folgern, dass ${\displaystyle F_{n}\equiv 2{\pmod {F_{k}}}}$ für ${\displaystyle k=0,1,\ldots ,n-1}$ gilt. Im Speziellen gilt also für ${\displaystyle k=1}$ (also für ${\displaystyle F_{1}=5}$) die Kongruenz ${\displaystyle F_{n}\equiv 2{\pmod {5}}}$ und somit entweder ${\displaystyle F_{n}\equiv 2{\pmod {10}}}$ oder ${\displaystyle F_{n}\equiv 7{\pmod {10}}}$. Weil aber Fermat-Zahlen immer ungerade sind, kann nur die Kongruenz ${\displaystyle F_{n}\equiv 7{\pmod {10}}}$ zutreffen, was zu zeigen war.

Die Aussage, dass die letzten beiden Ziffern 17, 37, 57 oder 97 sind, kann man der Literatur[16] entnehmen. ${\displaystyle \Box }$

Beweis der ersten Behauptung: ${\displaystyle F_{n}=x^{2}-2y^{2}}$

Der Beweis funktioniert direkt.

Die Existenz einer solchen Darstellung konnte schon weiter oben mit ${\displaystyle x:=F_{n-1}}$ und ${\displaystyle y:=F_{n-2}-1}$ gezeigt werden: ${\displaystyle F_{n}=x^{2}-2y^{2}=F_{n-1}^{2}-2\cdot (F_{n-2}-1)^{2}}$

Um unendlich viele solche Darstellungen zu erhalten, betrachte man folgende Identität:

${\displaystyle {\begin{array}{rcl}(3x+4y)^{2}-2\cdot (2x+3y)^{2}&=&9x^{2}+24xy+16y^{2}-2\cdot (4x^{2}+12xy+9y^{2})\\&=&9x^{2}+24xy+16y^{2}-8x^{2}-24xy-18y^{2}\\&=&x^{2}-2y^{2}\end{array}}}$

Weil ${\displaystyle x,y\in \mathbb {N} }$ ist, gilt ${\displaystyle 3x+4y>x}$ und ${\displaystyle 2x+3y>y}$. Somit kann man aus dem Darstellungspaar ${\displaystyle (x,y)}$ für ${\displaystyle F_{n}}$ ein (größeres) Darstellungspaar ${\displaystyle (3x+4y,2x+3y)}$ für ${\displaystyle F_{n}}$ konstruieren. Aus diesem kann man mit obiger Identität das nächste (größere) Darstellungspaar für ${\displaystyle F_{n}}$ konstruieren und so fort. Man erhält also unendlich viele Darstellungspaare für ${\displaystyle F_{n}}$ und somit auch unendlich viele Darstellungen von ${\displaystyle F_{n}}$ der Form ${\displaystyle F_{n}=x^{2}-2y^{2}}$, was zu zeigen war. ${\displaystyle \Box }$

Beweis der zweiten Behauptung: ${\displaystyle F_{n}=x^{2}-y^{2}}$

Der Beweis funktioniert direkt.

Es gilt:

${\displaystyle F_{n}=2^{2^{n}}+1=2^{2^{n}}+2^{2^{n}}+1-2^{2^{n}}=2^{2^{n}}+2\cdot 2^{2^{n}-1}+1-2^{2^{n}}=\left(2^{2^{n}-1}+1\right)^{2}-\left(2^{2^{n}-1}\right)^{2}}$

Somit hat man zwei Zahlen ${\displaystyle x:=2^{2^{n}-1}+1}$ und ${\displaystyle y:=2^{2^{n}-1}}$ gefunden, sodass ${\displaystyle F_{n}=x^{2}-y^{2}}$, also die Differenz von zwei Quadratzahlen, ist, was zu zeigen war.

Die Aussage, dass es mehrere solche Darstellungsmöglichkeiten als Differenz von zwei Quadratzahlen gibt, wenn ${\displaystyle F_{n}}$ zusammengesetzt ist, kann man der Literatur[18] entnehmen. ${\displaystyle \Box }$

Beweis der dritten Behauptung: ${\displaystyle F_{n}\not =p_{1}+p_{2}}$

Der Beweis funktioniert indirekt. Man startet mit einer Behauptung und zeigt, dass sie falsch ist, womit die Behauptung fallengelassen werden muss und das Gegenteil gilt.

Alle Fermat-Zahlen ${\displaystyle F_{n}=2^{2^{n}}+1}$ sind als Summe einer geraden und einer ungeraden Zahl 1 immer ungerade Zahlen. Primzahlen sind, bis auf die erste Primzahl ${\displaystyle p=2}$, immer ungerade. Wenn also die ungerade Zahl ${\displaystyle F_{n}}$ Summe von zwei Primzahlen sein soll, so dürfen nicht beide Primzahlen ungerade sein, weil die Summe zweier ungerader Zahlen eine gerade Zahl ergibt. Eine davon muss gerade sein. Weil es nur eine gerade Primzahl gibt, muss also 2 eine der beiden Summanden sein. Der andere prime Summand ist somit ${\displaystyle F_{n}-2}$ und es gilt trivialerweise ${\displaystyle F_{n}=2+(F_{n}-2)}$. Es gilt aber:

${\displaystyle F_{n}-2=2^{2^{n}}+1-2=2^{2^{n}}-1=(2^{2^{n-1}}-1)\cdot (2^{2^{n-1}}+1)}$

Somit ist aber ${\displaystyle F_{n}-2}$ für ${\displaystyle n\geq 2}$ zusammengesetzt und keine Primzahl, weil sogar der kleinere der beiden Faktoren ${\displaystyle 2^{2^{n-1}}-1\geq 2^{2^{2-1}}-1=2^{2}-1=3}$ ist und somit eine nichttriviale Faktorisierung von ${\displaystyle F_{n}-2}$ existiert. Wir erhalten einen Widerspruch. Die Annahme, dass man eine Fermat-Zahl als Summe zweier Primzahlen darstellen kann, muss fallengelassen werden, was zu zeigen war. ${\displaystyle \Box }$

Beweis der vierten Behauptung: ${\displaystyle F_{n}\not =a^{p}-b^{p}}$

Der Beweis funktioniert indirekt. Man startet mit einer Behauptung und zeigt, dass sie falsch ist, womit die Behauptung fallengelassen werden muss und das Gegenteil gilt.

Angenommen, ${\displaystyle p\in \mathbb {P} }$ ist eine ungerade Primzahl und ${\displaystyle F_{n}}$ kann dargestellt werden als Differenz von zwei p-ten Potenzen. Es sei also ${\displaystyle F_{n}=a^{p}-b^{p}}$. Dann gilt:

${\displaystyle F_{n}=a^{p}-b^{p}=(a-b)\cdot (a^{p-1}+a^{p-2}b+\ldots +ab^{p-2}+b^{p-1})}$ mit ${\displaystyle a>b}$

Weil ${\displaystyle F_{n}}$ prim ist und somit nicht zwei Teiler haben darf, muss ${\displaystyle a-b=1}$ sein. Wegen des kleinen fermatschen Satzes ist ${\displaystyle a^{p}\equiv a{\pmod {p}}}$ und ${\displaystyle b^{p}\equiv b{\pmod {p}}}$ und somit gilt:

${\displaystyle F_{n}=a^{p}-b^{p}\equiv a-b\equiv 1{\pmod {p}}}$

Somit muss ${\displaystyle p}$ ein Teiler von ${\displaystyle F_{n}-1=2^{2^{n}}+1-1=2^{2^{n}}}$ sein, was aber nicht sein kann, weil ${\displaystyle 2^{2^{n}}}$ nur Zweierpotenzen als Teiler hat.

Die Annahme muss also fallengelassen werden, ${\displaystyle F_{n}}$ kann daher nicht dargestellt werden als Differenz von zwei p-ten Potenzen.

Was zu zeigen war. ${\displaystyle \Box }$