Elementare Zahlentheorie

Protokoll zur Vorlesung Elementare Zahlentheorie vom 06.11.2003 (NB)

I. Inhaltliches Denken

[Wiederholung der letzten Vorlesung]

φ(n) = |E(Z/nZ)| = n - T₁(n), mit n = p₁^α₁· . . . ·p_r^α_r Primfaktorzerlegung.
T₁(n) = ( ∑^r_i=1 n/p_i ) - T₂(n)
Wobei wir bedenken müssen, dass wir die Paare zählen: |{(p_i,x) | 0 ≤ x ≤ n-1, p_i | x}|. Hierbei tritt das Problem auf, dass ein gleiches x bei verschiedenen p_i vorkommen kann. Diese müssen wir also wieder abziehen:

T₂(n) = ( ∑_i<.j n/( p_i · p_j ) ) - T₃(n)
...

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

Also: φ(n) = n - ( ∑ n/p_i ) + ( ∑ n/( p_i · p_j ) ) - ... (-1)^r n / ( p₁·. . .·p_r ).

II. Formales Denken (Formel umformen)

Wie sollen wir die Formel umformen?

n ausklammern.
Alles auf einen Nenner bringen.

Setze q_i = 1 / p_i und erhalte: φ(n) = n · ( 1 - ( ∑ q_i ) + ( ∑ q_i · q_j ) - ... (-1)^r q₁·. . .·q_r ).

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 - q₁ )
r = 2 : φ(n) = n · ( 1 - ( q₁ + q₂ ) + q₁·q₂) = n · ( 1 - q₁ )( 1 - q₂ )
r = 3 : φ(n) = n · ( 1 - q₁ - q₂ - q₃ + q₁·q₂ + q₂·q₃ + q₁·q₃ - q₁·q₂·q₃ + q₁·q₂) = n · ( 1 - q₁ )( 1 - q₂ )( 1 - q₃ )

Also:

φ(n) = n · ( 1 - 1/p₁ ) · ... · ( 1 - 1/p_r )

Dies ist die sog. EULERsche-Phi-Funktion.

Probe:
n = 12 = 2² · 3¹
φ(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. m₁ und m₂: φ(m₁·m₂) = φ(m₁) · φ(m₂). 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/m₁m₂Z ≈ Z/m₁Z x Z/m₂Z (als Ring-m-1) bzw. E(Z/m₁m₂Z) ≈ E(Z/m₁Z) x E(Z/m₂Z) (als Gruppen) für m₁, m₂ tlfr.
Allgemein: E(Z/nZ) ≈ E(Z/p₁^α₁·Z) x ... x E(Z/p_r^α_r·Z), wenn n = p₁^α₁ · . . . · p_r^α_r.
Also gilt nach der Formel: φ(n) = φ(p₁^α₁) · ... · φ(p_r^α_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 | x^k = 1} =: m
Beh.: m teilt diese k aus N.
Beweis: Division mit Rest: k = m · q + r (0 ≤ r < m), 1 = x^k = x^mq+r = (x^m)^q·x^r = x^r , 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> = {a⁰=1, a¹, ..., a^m-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, a⁰, a¹, ...} ≈ 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 Ug₁ vereinigt mit Ug₂ vereinigt mit ... vereinigt mit Ug_r . 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.