Die Zahl, die aus der Kälte kam: Wenn Mathematik zum Abenteuer wird (German Edition)

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 a
p
-
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 a
p
-1 beginnend und mit a  =  a 1 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 a p  – 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 1 p − 1 ist klarerweise durch p teilbar. Die eben durchgeführte Überlegung zeigt, dass daher auch 2 p − 2 durch p teilbar ist. Die eben durchgeführte Überlegung noch einmal angewendet beweist, dass auch 3 p − 3 durch p teilbar ist. Die eben durchgeführte Überlegung noch einmal angewendet beweist, dass auch 4 p − 4 durch p teilbar ist. Und so kann man von jeder Zahl a , von der man weiß, dass a p  – 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 a
p
 – a = a ( a
p
-1 − 1) durch die Primzahl p teilbar ist, und wenn die Zahl a  selbst durch p nicht teilbar ist, folgt, dass a
p
-1 bei der Division durch p den Rest 1 besitzen muss . Denn wenn a nicht durch p teilbar ist, muss a
p
-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 a 12 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 a 12 , also die Zahl ( a 12 ) 16 = a 12 ×  16 = a 192 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 a 192 nach Division durch den Modul 13  ×  17 = 221 mit Sicherheit den Rest 1. Als Formel geschrieben: a 192 ≡ 1.
    Die Zahl 192, die wir aus der Rechnung (13 − 1)  ×  (17 − 1) = 12  ×  16 erhalten, ist genauso geheim wie der von Toby Esterhase aus dem Tresor entnommene Geheimkoeffizient 35. Wir nennen 192 den „Geheimmodul“.
    Die Eierköpfe des Circus ermittelten mit dem Geheimmodul 192 für den Exponenten 11 den Geheimexponenten 35. Diese Zahl 35 ist nämlich deshalb der