Protokoll zur Vorlesung Elementare Zahlentheorie vom 06.11.2003 (NB)
[Zurück zur
Protokollübersicht]
I. Inhaltliches Denken
[Wiederholung der letzten Vorlesung]
φ(n) = |E(Z/nZ)| = n - T1(n),
mit n = p1α1· . . .
·prαr Primfaktorzerlegung.
T1(n) = ( ∑ri=1 n/pi ) - T2(n)
Wobei wir bedenken müssen, dass wir die Paare zählen: |{(pi,x) | 0 ≤ x ≤ n-1, pi | x}|. Hierbei tritt das Problem auf, dass ein gleiches x bei verschiedenen pi vorkommen kann. Diese müssen wir also wieder abziehen:
T2(n) = ( ∑i<.j n/( pi · pj ) ) - T3(n)
...
Tr(n) = n / (p1·. . .·pr)
Also: φ(n) = n - ( ∑ n/pi ) +
( ∑ n/( pi · pj ) ) - ...
(-1)r n / ( p1·. . .·pr ).
II. Formales Denken (Formel umformen)
Wie sollen wir die Formel umformen?
- n ausklammern.
- Alles auf einen Nenner bringen.
Setze qi = 1 / pi und erhalte:
φ(n) = n · ( 1 - ( ∑ qi ) +
( ∑ qi · qj ) - ...
(-1)r q1·. . .·qr ).
- Um weiter umformen zu können wählen wir Beispiele für ein kleines r und erhalten so einen Überblick.
Beispiele:
- r = 1 : φ(n) = n · ( 1 - q1 )
- r = 2 : φ(n) = n · ( 1 - ( q1 + q2 ) + q1·q2) = n · ( 1 - q1 )( 1 - q2 )
- r = 3 : φ(n) = n · ( 1 - q1 -
q2 - q3 + q1·q2 +
q2·q3 + q1·q3 -
q1·q2·q3 +
q1·q2) =
n · ( 1 - q1 )( 1 - q2 )( 1 - q3 )
Also:
φ(n) = n · ( 1 - 1/p1 )
· ... · ( 1 - 1/pr ) |
Dies ist die sog. EULERsche-Phi-Funktion.
Probe:
n = 12 = 22 · 31
φ(12) = 12 · ( 1 - 1/2 )·( 1 - 1/3 ) = 12 · 1/2 · 2/3 = 4
Nach Chinesischem Restesatz:
φ(12) = φ(4) · φ(3) = 2 · 2 = 4
Denn hier galt die Formel für tlfr. m1 und m2: φ(m1·m2) = φ(m1) · φ(m2).
Diese Formel ist durch Termumformung in die Euler-Formel überführbar.
Vergleichen wir die beiden Methoden einmal:
- Chinesischer Restesatz: Hier wurde mittels der Gruppen- und Ringtheorie argumentiert. Der Beweis fand auf einer sehr abstrakten Ebene
[DE 3 und 4] statt. Aber man erhält nicht nur eine Aussage über die Anzahl der Elemente der Einheiten, sondern wir bekommen Aussagen über die Struktur und die Isomorphietypen:
Z/m1m2Z ≈ Z/m1Z x Z/m2Z (als Ring-m-1) bzw. E(Z/m1m2Z) ≈ E(Z/m1Z) x E(Z/m2Z) (als Gruppen) für m1, m2 tlfr.
Allgemein: E(Z/nZ) ≈
E(Z/p1α1·Z)
x ... x E(Z/prαr·Z),
wenn n = p1α1 · . . .
· prαr.
Also gilt nach der Formel: φ(n) = φ(p1α1)
· ... · φ(prαr)
mit φ(pα) = pα - pα - 1
= pα - 1 (p-1) = pα(1-1/p).
[Dies ergibt eingesetzt genau die Euler-Formel!]
- Euler: Hier kommt man mit ganz elementaren Rechnungen aus und die Gruppen- und Ringtheorie wird nicht benötigt. Man bekommt allerdings auch nur die Anzahl der Elemente. Weitere (Struktur-)Aussagen lassen sich nicht gewinnen.
III. Weiterführendes Denken (Fragen und Planen)
Wir interessieren uns ja für die Einheitengruppe
E := E(Z/nZ). Bis jetzt haben wir: φ(n)=|E(Z/nZ)|.
Also stellen wir weitere Fragen an die Gruppe: [FRAGEN]
- Welche Untergruppen gibt es?
- Welche Elemente sind in der Gruppe? Was sind die Elementordnungen?
- Was sind die Normalteiler und was ist das Zentrum?
- Gibt es ein minimales Erzeugendensystem? Ist E zyklisch?
- Was sind die Isomorphietypen von E(Z/pαZ)?
[Konvention: Ich schreibe x für die Restklassen von x.]
Finden der Antworten: [PLANEN]
Zu 2.:
Die Elemente: E={x | 0 ≤ x ≤ n-1, ggT(x,n)=1}
Die Elementordnungen: |<x>| = o(x) = Min { k aus N | xk = 1} =: m
Beh.: m teilt diese k aus N.
Beweis: Division mit Rest: k = m · q + r (0 ≤ r < m), 1 = xk = xmq+r = (xm)q·xr = xr , Da aber m minimal ist, ist r = 0.
Zu 3.:
Diese Frage ist unerheblich, da E eine abelsche Gruppe ist und somit jede Untergruppe Normalteiler ist.
Zu 4.:
Zuerst betrachten wir allgemeine zyklische Gruppen:
Analyse:
- Gruppe bezgl. der Multiplikation: <.a> = {a0=1, a1, ..., am-1}: m
- Gruppe bezgl. der Addition: <.b> = { 0b, 1b, ..., (m-1)b} ≈ Z/mZ = {0, 1, ...,m-1} = <1>, wobei hier b ↔ 1 bijektiv abgebildet wird.
- Unendl. zykl. Gruppe: <.a> = {..., a-2, a-1, a0, a1, ...} ≈ Z/0Z ≈ Z = {..., -2, -1, 0, 1, 2, ...} = <1> wobei hier a ↔ 1 bijektiv abgebildet wird.
Also sind alle zyklischen Gruppen isomorph zu Z/mZ.
Ist nun auch E(Z/nZ) zyklisch?
Betrachten wir in Gruppenarbeit Beispiele. Zuvor aber noch ein hilfreicher Satz:
Beh.: |U| teil |G| für U Untergruppe der Gruppe G.
Beweis: G = U vereinigt mit Ug1 vereinigt mit Ug2 vereinigt mit ... vereinigt mit Ugr . Da alle Nebenklassen gleich viele
Elemente enthalten, gilt natürlich: |G| = r · |U|, q. e. d.
Gehen wir nun die Beispiele an:
m |
25 |
13 |
11 |
7 |
5 |
27 |
9 |
3 |
16 |
8 |
4 |
2 |
|E| |
20 |
12 |
10 |
6 |
4 |
18 |
6 |
2 |
8 |
4 |
2 |
1 |
Wir müssen also jeweils testen, ob die Ordnung s von
x aus E(Z/nZ) gerade gleich
|E| ist. Für diese n ist E(Z/nZ)
zyklisch.
Die weitere Untersuchung findet in der nächsten Vorlesung statt.
Zurück
zur vorangehenden Stunde (04.11.03),
zur Protokollübersicht.