12 Was Mersenne an diesen Beispielen zeigte, stimmt immer: Wenn man eine aus den Faktoren a und b zusammengesetzte Zahl a × b betrachtet, wobei sowohl a als auch b größer als 1 sind, dann ist
2 a×b − 1 = (2 a− 1) × (1 + 2 a + 22a + … + 2(b – 1)×a)
eine zusammengesetzte Zahl.
13 Um der Wahrheit die Ehre zu geben: Fermat schrieb diese Zahlen als Potenztürme. Sie besitzen nämlich zugleich die Darstellungen
, 
, 
, 
und so weiter.
14 Im Prinzip könnte man 4 294 967 297 der Reihe nach durch die Primzahlen aus einer genügend langen und vollständigen Primzahlentabelle dividieren und untersuchen, ob die Division ohne Rest aufgeht. Aber das ist nicht nur außerordentlich zeitaufwendig, es ist auch erbärmlich primitiv. Euler ging sicher anders vor. Vielleicht stellte er fest, dass 641 = 54 + 24 und zugleich 641 = 5 × 27 + 1 ist. Wegen der ersten Formel teilt 641 die Zahl (54 + 24) × 228 und wegen der zweiten Formel teilt 641 die Zahl 54 × (228 − 1), weil man deren zweiten Faktor in
228 − 1 = (27 + 1) × (221 − 214 + 27 − 1)
zerlegen kann. Wenn somit 641 die Zahlen (54 + 24) × 228 und 54 × (228 − 1) teilt, dann teilt sie auch deren Differenz, die
(54 + 24) × 228 − 54 × (228 − 1) = 24 × 228 + 1 = 232 + 1 = 4 294 967 297
beträgt.
15 Wir jedoch wollen verstehen: Warum funktioniert das eigenartige Verfahren des Chiffrierens und Dechiffrierens? Um diese Frage beantworten zu können, müssen wir weit ausholen und blicken auf Pierre de Fermat, jenen unerhört geistreichen Rechtsgelehrten aus der Zeit des Barock, der seine Freizeit am liebsten mit dem Studium der Zahlen zubrachte.
Man muss sich Fermat als vom Rechnen besessen vorstellen. Manisch suchte er den Zahlen Geheimnisse zu entlocken. So fiel ihm zum Beispiel auf, dass die fünften Potenzen aller Ziffern durchwegs mit eben dieser Ziffer an der Einerstelle enden: 05 = 0 endet mit 0, 15 = 1 endet mit 1, 25 = 32 endet mit 2, 35 = 243 endet mit 3, 45 = 1024 endet mit 4, 55 = 3125 endet mit 5, 65 = 7776 endet mit 6, 75 = 16 807 endet mit 7, 85 = 32 768 endet mit 8 und 95 = 59 049 endet mit 9. Und wie sieht das bei den dritten Potenzen aus? Da stimmt es nicht. Es ist zum Beispiel 23 = 8: diese Zahl endet nicht mit 2. Aber Fermat stellt fest, dass 23 − 2, also 8 − 2 = 6 durch die Hochzahl 3 teilbar ist. Das nämlich war es eigentlich, was er oben festgestellt hat: dass die fünfte Potenz jeder Ziffer minus eben dieser Ziffer durch fünf teilbar ist. Und er rechnet weiter: Es ist 33 − 3, also 27 − 3 = 24, und diese Zahl ist tatsächlich durch 3 teilbar. Genauso bestätigt er dass 43 − 4, also 64 − 4 = 60 durch 3 teilbar ist, dass 53 − 5, also 125 − 5 = 120 durch 3 teilbar ist, dass 63 − 6, also 216 − 6 = 210 durch 3 teilbar ist, dass 73 − 7, also 343 − 7 = 336 durch 3 teilbar ist, dass 83 − 8, also 512 − 8 = 504 durch 3 teilbar ist, ferner dass 93 − 9, also 729 − 9 = 720 durch 3 teilbar ist, dass sogar 103 − 10, also 1000 − 10 = 990 durch 3 teilbar ist und dass 113 − 11, also 1331 − 11 = 1320 durch 3 teilbar ist.
Das kann doch kein Zufall sein! Oder vielleicht doch? Was ist, wenn man die vierten Potenzen von Zahlen betrachtet? Zum Beispiel ist 34 = 81 Aber 34 − 3, also 81 − 3 = 78 ist nicht durch 4 teilbar. Wie aber sieht es mit den siebenten Potenzen aus? Bei 27 = 128 tritt das Phänomen wieder zutage: 27 − 2, also 128 − 2 = 126 ist durch 7 teilbar. Und bei 37 = 2187 stimmt es auch: 37 − 3, also 2187 − 3 = 2184 ist durch 7 teilbar.
Bei der Hochzahl 4 stellt Fermat das Phänomen nicht fest, wohl aber bei den Hochzahlen 5, 3 oder 7. Die Zahlen 3, 5, 7, so überlegt Fermat, sind Primzahlen, 4 hingegen nicht. Vielleicht liegt es daran?
Nun lässt ihn dieser Gedanke nicht mehr los: Wenn p eine Primzahl bezeichnet, so scheint für jede Zahl a die Differenz ap – a durch diese Primzahl p teilbar zu sein. Eine raffinierte Überlegung, die sein Zeitgenosse und Brieffreund Blaise Pascal entwickelt hatte, bestärkte ihn bei seiner Vermutung:
Was geschieht, so fragt Fermat, wenn man nicht die p-te Potzenz von a, also die Zahl ap, sondern die p-te Potenz der nächsten Zahl, also (a + 1)p berechnet? Ausführlich angeschrieben sieht das so aus:
(a + 1) p = (a + 1) (a + 1) (a + 1)… (a + 1),
mit anderen Worten: p-mal wird (a + 1) mit sich selbst multipliziert. Das auszurechnen scheint unerhört mühsam – besonders dann, wenn p eine große Primzahl ist. Aber einiges lässt sich doch bei dieser Rechnung feststellen.
Sehen wir uns zum Beispiel diese Rechnung für die Primzahl p = 5 an: Das Ergebnis lautet
(a + 1)5 = (a + 1)(a + 1)(a + 1)(a + 1)(a + 1) = a5 + 1 + 5a4 + 10a3 + 10a2 + 5a.
Wieso kommt man dazu? Der erste Summand a5 ist klar: Alle fünf ersten Summanden a in den Klammern wurden miteinander multipliziert. Auch der zweite Summand 1 ist klar: Alle fünf zweiten Summanden 1 in den Klammern wurden miteinander multipliziert. Der dritte Summand 5a4 kommt so zustande: Man nimmt von den Klammern vier erste Summanden a und einen zweiten Summanden 1 und multipliziert diese. Und es gibt genau 5 Möglichkeiten für diese Auswahl, daher der Faktor 5 vor der Potenz a4. Genauso kann man erklären, wie der letzte Summand 5a entsteht. Der vierte Summand 10a3 kommt so zustande: Man nimmt von den Klammern drei erste Summanden a und zwei zweite Summanden 1 und multipliziert diese. Wie viele Möglichkeiten gibt es für diese Auswahl? Für den einen zweiten Summanden 1 offenbar fünf und für den anderen zweiten Summanden 1 nur mehr vier, denn eine der Zahlen 1 ist ja schon für den ersten Summanden 1 gewählt worden. Das deutet auf 5 × 4 = 20 mögliche Wahlen hin. Allerdings ist zu bedenken, dass jeweils zwei dieser Wahlen zum gleichen Ergebnis führen, weil von den beiden gewählten Zahlen 1 unerheblich ist, welche von ihnen der „erste“ und welche der „zweite“ der gewählten Summanden ist. Die Anzahl der möglichen Vertauschungen von zwei gewählten Zahlen beträgt 1 × 2 = 2. Durch diese Zahl 2 muss man 20 dividieren, wodurch der Faktor 10 vor der Potenz a3 entsteht. Schließlich kommt der dritte Summand 10a2 so zustande: Man nimmt von den Klammern zwei erste Summanden a und drei zweite Summanden 1 und multipliziert diese. Wie viele Möglichkeiten gibt es für diese Auswahl? Für den einen zweiten Summanden 1 offenbar fünf, für den nächsten zweiten Summanden 1 nur mehr vier und für den letzten zweiten Summanden 1 nur mehr drei. Das deutet auf 5 × 4 × 3 = 60 mögliche Wahlen hin. Allerdings ist zu bedenken, dass jeweils sechs dieser Wahlen zum gleichen Ergebnis führen, weil von den drei gewählten Zahlen 1 unerheblich ist, welche von ihnen der „erste“, welche der „zweite“ und welche der „dritte“ der gewählten Summanden 1 ist. Die Anzahl der möglichen Vertauschungen von drei gewählten Zahlen beträgt 1 × 2 × 3 = 6. Durch diese Zahl 6 muss man 60 dividieren, wodurch der Faktor 10 vor der Potenz a2 entsteht.