In diesem Artikel beschäftigen wir uns wieder ewtas direkter mit Mathematik. Wir werden einen wichtigen Satz aus der Zahlentheorie, den Satz von Euler-Fermat formulieren, verstehen und beweisen. Ich empfehle, den Artikel über Teilbarkeitsregeln vor diesem zu lesen, da wir die Modulonotation benötigen werden.
Zur Erinnerung: Wir schreiben a \equiv b \mod n, falls die Differenz a-b durch n teilbar ist.
Zwei ganze Zahlen a und b heißen teilerfremd, falls der größte gemeinsame Teiler von a und b gleich 1 ist. Beispielsweise sind 3 und 7 teilerfremd. Dahingegen sind 10 und 15 nicht teilerfremd, weil sie 5 als gemeinsamen Teiler haben.
Wir betrachten jetzt zu einer gegebenen Zahl n\gt 1 die Anzahl der positiven teilerfremden Zahlen kleiner als n. Diese Anzahl schreiben wir als \varphi(n), das ist die Eulersche Phi-Funktion. Es gilt zum Beispiel \varphi(4)=2, da die Zahlen 1 und 3 teilerfremd zu 4 sind. Es ist \varphi(12)=4, da 1, 5, 7 und 11 teilerfremd zu 12 sind. Für eine Primzahl p gilt \varphi(p)=p-1. Schließlich sind alle kleineren positiven Zahlen zu ihr teilerfremd.
Berechnung von \varphi(n)
Wir möchten \varphi(n) einigermaßen effizient bestimmen können. Schließlich wollen wir für \varphi(1000) nicht das Zählen anfangen. Dazu gibt es zwei nützliche Gleichungen.
Für eine Primzahlpotenz p^r ist das Zählen noch recht einfach. Wir gehen von allen Zahlen aus und ziehen die ab, die nicht zu p^r teilerfremd sind. Das sind aber genau die durch p teilbaren Zahlen. Davon gibt es \frac{p^r}{p}=p^{r-1} viele. Also folgt
\varphi(p^r)=p^r-p^{r-1}\;.Außerdem kann man herleiten, dass für zwei teilerfremde Zahlen a und b gilt:
\varphi(ab)=\varphi(a)\varphi(b)Den Nachweis dieser Gleichung lasse ich hier weg, weil das relativ technisch ist und man aus meiner Sicht nicht so viel daraus lernen kann. Wichtig ist zu beachten, dass die Gleichung nur für teilerfremde a und b gilt.
Für \varphi(12) hätten wir also \varphi(12)=\varphi(4)\varphi(3)=2 \cdot 2=4 rechnen können. Allgemein schauen wir uns zu einer Zahl n ihre Primfaktorenzerlegung an. Dabei fassen wir gleiche Primfaktoren zu einer Primpotenz zusammen. Von den Primpotenzen können wir mit der ersten Gleichung \varphi(p^r) bestimmen. Mit der zweiten Gleichung fügen wir nach und nach die Primpotenzen zusammen. Das funktioniert, weil eine Primpotenz p^r zu jeder Zahl, die nicht durch p teilbar ist, teilerfremd ist.
Für n=1000 finden wir zunächst die Primfaktorenzerlegung 1000~=~2^3 ~\cdot ~5^3. Es ist \varphi(8)=8-4=4 und \varphi(125)=125-25=100. Es folgt \varphi(1000)=400.
Der Satz von Euler-Fermat
Wir können jetzt den zentralen Satz dieses Artikels formulieren.
Sei n\gt 1 eine natürliche Zahl und a eine zu n teilerfremde ganze Zahl. Dann gilt
a^{\varphi(n)}\equiv 1 \mod nAlso ist a^{\varphi(n)}-1 immer durch n teilbar, solange a und n teilerfremd sind.
Für a=5 und n=12 erhalten wir zum Beispiel, dass 5^4-1=624 durch 12 teilbar ist. Das Ziel ist jetzt den Satz zu beweisen. Ich werde beim Beweis die grundlegende Idee mit diesem Beispiel verdeutlichen. Das ist für einen Beweis natürlich nicht notwendig, kann dir aber vielleicht helfen, ihn besser zu verstehen.
Der Beweis
Wir betrachten die positiven ganzen Zahlen kleiner n, die zu n teilerfremd sind. Nach Definition der Eulerschen Phi-Funktion gibt es davon genau \varphi(n) viele. Wir können sie also mit d_1, d_2, d_3, \cdots d_{\varphi(n)} nummerieren. Wir betrachten jetzt das Produkt dieser d_i also d_1 \cdot d_2 \cdot \cdots \cdot d_{\varphi(n)}. In dem Beispiel schauen wir uns also gerade das Produkt 1 \cdot 5 \cdot 7 \cdot 11 an.
Wir multiplizieren nun diese d_i jeweils mit a und betrachten diese Zahlen modulo n. Im Beispiel erhalten wir die Zahlen 5, 25, 35 und 55. Modulo 12 entspricht das den Resten 5, 1, 11 und 7. Das sind doch genau die gleichen! Genau diese Feststellung wollen wir jetzt beweisen.
Zunächst einmal sind die erhaltenen Zahlen wieder teilerfremd zu n. Schließlich haben wir zu n teilerfremde Zahlen mit a multipliziert. Hier geht ein, dass a zu n teilerfremd ist. Das Produkt hat dann immer noch keinen gemeinsamen Teiler. Wir hatten alle zu n teilerfremden Zahlen kleiner als n betrachtet, also alle möglichen teilerfremden Reste. Es reicht also zu zeigen, dass die Produkte a \cdot d_i alle verschiedene Reste haben müssen. Dann müssen sie nämlich auch alle abdecken. In dem Beispiel beweisen wir also nun, dass die erhaltenen Reste 5, 1, 11 und 7 tatsächlich verschieden sein müssen, weil dann auch alle Reste vorkommen müssen.
Nehmen wir also mal das Gegenteil an. Angenommen es gibt also zwei verschiedene teilerfremde Zahlen d_i und d_j mit a \cdot d_i \equiv a\cdot d_j \mod n Umstellen liefert a(d_i-d_j)\equiv 0 \mod n. Also ist a(d_i-d_j) durch n teilbar. Da aber a zu n teilerfremd ist, also keinen gemeinsamen Faktor enthält, muss schon d_i-d_j durch n teilbar sein. Das heißt aber d_i\equiv d_j \mod n. Also waren sie nicht verschieden, ein Widerspruch. Damit sind tatsächlich alle Reste verschieden.
Wir wissen jetzt also, dass modulo n die Zahlen d_1, d_2, \ldots d_{\varphi(n)} und a~\cdot~d_1, a~\cdot~d_2, \ldots a~\cdot~d_{\varphi(n)} bis auf Vertauschung der Reihenfolge gleich sind. Wenn wir die Produkte von allen vergleichen, müssen diese also auch gleich sein. Also:
d_1 \cdot d_2 \cdots d_{\varphi(n)}\equiv(a\cdot d_1) \cdot (a\cdot d_2) \cdots (a\cdot d_{\varphi(n)} \mod nAuf der rechten Seiten können wir aus jedem Faktor ein a herausziehen und zu einem a^{\varphi(n)} zusammenfassen. Das ist doch genau das, was im Satz von Euler-Fermat betrachtet wird! Umstellen der obigen Gleichung modulo n liefert:
(a^{\varphi(n)}-1)(d_1\cdot d_2 \cdots d_{\varphi(n)})\equiv 0 \mod nHier haben wir jetzt den gleichen Fall wie eben. Ein Produkt zweier Faktoren ist 0 \mod n und einer der Faktoren ist teilerfremd zu n. Dann ist der andere Faktor schon durch n teilbar. Also folgt
a^{\varphi(n)}\equiv 1 \mod n \;,was zu zeigen war.
Im Beispiel haben wir also ausgenutzt, dass
1\cdot 5\cdot 7 \cdot 11 \equiv (5\cdot 1) \cdot (5\cdot 5) \cdot (5 \cdot 7) \cdot (5\cdot 11) \mod 12Auf der rechten Seite steht ein Faktor 5^4 zusätzlich. Dann mussten wir noch argumentieren, warum wir hier im Prinzip durch den Rest teilen dürfen. Der Grund ist, dass der andere Faktor teilerfremd zu n ist.
Eine einfache Folgerung aus diesem Satz ist der kleine Satz von Fermat. Dieser besagt, dass für eine Primzahl p und eine Zahl a, die nicht durch p teilbar ist, gilt:
a^{p-1} \equiv 1 \mod pWir können einfach eine Primzahl in den Satz von Euler-Fermat einsetzen und erhalten genau diese Aussage.
Im nächsten Artikel werden wir eine Anwendung dieses Satzes behandeln. Es wird um Verschlüsselung gehen.