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 = p₁^α₁  ... p_r^α_r mit Primzahlen p_i (i zwischen 1 und r).

A6: (a, n) nicht teilerfremd bedeutet: Es existiert p_i  (i zwischen 1 und r) mit p_i 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/p₁ + n/p₂ + ... + n/p_r - T₂ ,   wo T₂ := Anzahl der a, die durch mindestens zwei der p_i (i zwischen 1 und r) geteilt werden.

F10: Wie lässt sich T₂ durch Formeln ausdrücken?

A10: Definiere zunächst T_k := Anzahl der a, die durch mindestens k der p_i ( i zwischen 1 und r) geteilt werden.

T₂ = n/(p₁p₂) +n/(p₁p₃)+...+n/(p₁p_r)+  n/(p₂p₃) + ....+ n/(p_{r - 1}p_r)  - T₃

T3 = n/(p₁p₂p₃₎   + ... - T₄

...

T_r = n/(p₁p₂...p_r)

Also folgt:

N(n) = n/p₁ + n/p₂ + ... + n/p_r - n/(p₁p₂) + n/(p₁p₃) + ... + n/(p₁p_r) + n/(p₂p₃)  + ... + (-1)^{r - 1} n/(p₁p₂...p_r)

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.