Überdies ist bemerkenswert, dass alle Faktoren 5, 10, 10 und 5 durch 5 teilbar sind. Dies liegt daran, dass 5 eine Primzahl ist.
Nun beschreiben wir allgemein, wie man
(a + 1) p = (a + 1) (a + 1) (a + 1)… (a + 1) ,
berechnet:
Zum einen wird man alle ersten Summanden a mit sich multiplizieren müssen. Das ergibt ap. Zum anderen wird man alle letzten Summanden 1 mit sich multiplizieren müssen. Das ergibt 1p = 1. Also ist
(a + 1) p = (a + 1) (a + 1) (a + 1)… (a + 1) = a p + 1 + … .
Was hier schamhaft mit den drei Punkten … symbolisiert wird, ist alles Übrige, was beim Ausmultiplizieren dazukommt. Das werden die Potenzen ap-1, ap-2, ap-3, und so weiter sein – nur stellt sich hier die Frage: Wie oft kommen sie vor? Zum Beispiel kommt die Potenz ap-1 dadurch zustande, dass man p - 1 der ersten Summanden a mit genau einem der zweiten Summanden 1 multipliziert. Dafür gibt es beim Ausmultiplizieren insgesamt p Möglichkeiten. Also kommt die Potenz ap-1 in den drei Punkten als pap-1 vor. Oder es kommt die Potenz ap-2 dadurch zustande, dass man p − 2 der ersten Summanden a mit genau zwei der zweiten Summanden 1 multipliziert. Wie oft erfolgt das beim Ausmultiplizieren? Für den einen der beiden zweiten Summanden 1 bestehen p Auswahlen, für den andern nur mehr p − 1 Auswahlen: das läuft auf p × (p − 1) hinaus. Allerdings muss man diese Zahl noch durch 1 × 2 dividieren, denn welche der beiden Summanden 1 als Erster und welcher als Zweiter gewählt wurde, ist unerheblich. Also kommt die Potenz ap-2 in den drei Punkten als
vor. Allgemein überlegt man sich, dass die Potenzap-n dadurch zustande kommt, dass man p – n der ersten Summanden a mit genau n der zweiten Summanden 1 multipliziert. Wie oft erfolgt das beim Ausmultiplizieren? Für den ersten der n Summanden 1 bestehen p Auswahlen, für den zweiten nur mehr p − 1 Auswahlen, und dies geht so weiter, bis schließlich für den n-ten Summanden 1 nur mehr p − n + 1 Auswahlen bestehen. Das läuft auf p × (p − 1) × … × ( p – n + 1) Auswahlen hinaus. Allerdings muss man diese Zahl noch durch 1 × 2 × … ×n dividieren, denn welche der n Summanden 1 als Erster, welcher als Zweiter, …, welcher als n-ter gewählt wurde, ist unerheblich. Also kommt die Potenz ap-n in den drei Punkten als
vor.
Die Faktoren vor den Potenzen von a sehen nur scheinbar wie Brüche aus; in Wirklichkeit sind sie ganze Zahlen. Mit anderen Worten: die Nenner der angeschriebenen Brüche sind mit Sicherheit Teiler der Zähler. Die zu Beginn angeschriebene Primzahl p können sie aber nicht teilen. Das ist im Wesen der Primzahl begründet. Deshalb sind die Faktoren vor den Potenzen von a, mit ap-1 beginnend und mit a = a1 endend, nicht nur ganze Zahlen, sie sind sogar durch die Primzahl p teilbare ganze Zahlen.
Zusammengefasst besagt dies: Es ist
(a + 1) p = a p + 1 + …,
wobei alle Zahlen, die in den drei Punkten … verborgen sind, durch die Primzahl p teilbar sind.
Angenommen, so argumentiert Fermat nun weiter, wir wüssten bereits, dass ap – a durch p teilbar ist. Dann ist wegen der Rechnung
(a + 1) p – (a + 1) = a p + 1 + … − (a + 1) = a p + 1 + … − a − 1 = a p – a + …
und wegen der Tatsache, dass alle Zahlen, die in den drei Punkten verborgen sind, durch p teilbar sind, auch die Differenz (a + 1)p – (a + 1) durch p teilbar.
Damit hat Fermat das gezeigt, was er beweisen wollte. Denn 1p − 1 ist klarerweise durch p teilbar. Die eben durchgeführte Überlegung zeigt, dass daher auch 2p − 2 durch p teilbar ist. Die eben durchgeführte Überlegung noch einmal angewendet beweist, dass auch 3p − 3 durch p teilbar ist. Die eben durchgeführte Überlegung noch einmal angewendet beweist, dass auch 4p − 4 durch p teilbar ist. Und so kann man von jeder Zahl a, von der man weiß, dass ap – a durch p teilbar ist, zur nächsten Zahl a + 1 voranschreiten und auch von ihr feststellen, dass (a + 1)p – (a + 1) durch p teilbar ist.
Die hier bewiesene Erkenntnis wird der Satz von Fermat genannt. Allerdings nicht der „große Satz von Fermat“, von dem Simon Singh in seinem schönen Buch „Fermats letzter Satz“ erzählt, sondern der sogenannte „kleine Satz von Fermat“. Obwohl dieser Satz alles andere als „klein“, vielmehr sehr bedeutend ist. Nebenbei bemerkt: Fermat hat nicht verraten, wie er zu seinem „kleinen Satz“ gelangt ist. Erst ein Jahrhundert später fand Leonhard Euler heraus, warum dieser Satz stimmt.
Wenn man weiß, dass ap – a = a(ap-1 − 1) durch die Primzahl p teilbar ist, und wenn die Zahl a selbst durch p nicht teilbar ist, folgt, dass ap-1bei der Division durch p den Rest 1 besitzen muss. Denn wenn a nicht durch p teilbar ist, muss ap-1 − 1 durch p teilbar sein. Auch diese Aussage wird zuweilen der „kleine Satz von Fermat“ genannt.
Zum Beispiel muss die 12. Potenz jeder nicht durch 13 teilbaren Zahl nach Division durch 13 den Rest 1 lassen. Oder die 16. Potenz jeder nicht durch 17 teilbaren Zahl muss nach Division durch 17 den Rest 1 lassen.
Jetzt sind wir plötzlich bei der Chiffriermethode des George Smiley angelangt: Denn der kleine Satz von Fermat besagt, dass für jede nicht durch 13 teilbare Zahl a, insbesondere für a = 7, die Potenz a12 nach Division durch 13 den Rest 1 lässt. Der kleine Satz von Fermat besagt auch, dass – falls a nicht durch 17 teilbar ist – die 16. Potenz von a12, also die Zahl (a12)16 = a12 × 16 = a192 nach Division durch 17 den Rest 1 lässt. Und nach Division durch 13 lässt sie auch den Rest 1. Also lässt die Potenz a192 nach Division durch den Modul 13 × 17 = 221 mit Sicherheit den Rest 1. Als Formel geschrieben: a192 ≡ 1.