Elementare Zahlentheorie WS 2003/04
Protokoll vom 04.11.03 (AE)
Thema der Stunde: Eulers Zugang zur Phi-Funktion
Zu Beginn der Stunde stellte sich die Frage, wie Euler ohne den chinesischen Restesatz auf die Phi-Funktion kam. Zunächst definierten wir unser Ziel, eine explizite Formel für Phi zu finden. Um uns diesem Problem zu nähern, stellten wir die folgenden Fragen und begannen, Antworten zu suchen:
F1: Wie ist Phi definiert?
F2: Wozu ist Phi gut?
F3: Welche explizite Formel gibt es für Phi?
F4: Was wissen wir bereits über die Einheitengruppe
von Z/nZ?
A1: Phi ordnet einer natürlichen Zahl n den Restklassenring Z/nZ zu, diesem wird die Einheitengruppe E(Z/nZ) zugeordnet und dieser Gruppe wiederum ihre Ordnung. Definitions- und Wertebereich sind also beides die natürlichen Zahlen.
A3: Wir wissen über E(Z/nZ): Die Restklasse ā ist genau dann Einheit von Z/nZ, wenn (a, n) teilerfremd sind (a Element von Z).
F5: Welche Elemente sind nicht teilerfremd? Wie viele?
A5: N(n) := Anzahl der Elemente ā, für die gilt: (a, n) sind nicht teilerfremd, wobei a zwischen 0 und n - 1 liegt.
Es gilt also folgendes:
Anzahl von E(Z/nZ) = N(n) + φ(n).
Nun versuchten wir wiederum durch Fragen und Antworten N(n) zu bestimmen.
F6: Welche Elemente sind nicht teilerfremd?
F7: Was sind die Teiler von n?
F8: Wie lautet die Primfaktorzerlegung von n?
A8:
n = p1α1
... prαr
mit Primzahlen pi (i zwischen 1
und r).
A6: (a, n) nicht teilerfremd bedeutet: Es existiert pi (i zwischen 1 und r) mit pi teilt a.
F9: Wie viele a (a zwischen 0 und n - 1) werden von einer Primzahl p geteilt?
A9: Die Anzahl beträgt n/p.
Also gilt: N(n) = n/p1 + n/p2 + ... + n/pr - T2 , wo T2 := Anzahl der a, die durch mindestens zwei der pi (i zwischen 1 und r) geteilt werden.
F10: Wie lässt sich T2 durch Formeln ausdrücken?
A10: Definiere zunächst Tk := Anzahl der a, die durch mindestens k der pi ( i zwischen 1 und r) geteilt werden.
T2 = n/(p1p2) +n/(p1p3)+...+n/(p1pr)+ n/(p2p3) + ....+ n/(pr - 1pr) - T3
T3 = n/(p1p2p3) + ... - T4
...
Tr = n/(p1p2...pr)
Also folgt:
N(n) = n/p1 + n/p2 + ... + n/pr - n/(p1p2) + n/(p1p3) + ... + n/(p1pr) + n/(p2p3) + ... + (-1)r - 1 n/(p1p2...pr)
Schlussbemerkung:
Wir haben die Formel für N(n) natürlich nicht sofort
(wie oben dargestellt) herausgefunden, sondern
zunächst falsche oder unzulängliche Formeln aufgestellt, diese
teilweise an Beispielen überprüft und nach und nach verbessert.