|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|||||||||||||||||||||||
|
|
|
||||||||||||||||||||||
|
|
|||||||||||||||||||||||
Elementare Zahlentheorie WS 2003/04
11.11.2003 AZ
Z/n Z ist ein R-m-1.
1) Additive Struktur: Z/nZ zyklische Gruppe.
2) Multiplikative Struktur: E(Z/nZ) ist eine Gruppe mit φ(n) Elementen.
Thema: Struktur der "primen Restklassengruppe" [(Prime Restklassen)-Gruppe]
Kann man 2) in zyklische Gruppen zerlegen?
Frage: Ist E(Z/nZ) zyklisch? (Zyklisch: Ordnung o(a) vom Erzeuger a der zyklischen Gruppe muss gleich φ(n) sein.)
[Ab hier muss noch redigiert werden.]Frage: |<a>| für a є E(Z/nZ) = o(a) = Min{m є N| am = 1}
Beispiele:
bekannt: |<a>| teilt |E(Z/nZ)|
o(a) teilt φ(n) , also sind die Kandidaten für o(a) die Teiler von φ(n)
| n | φ(n) | alle Elemente von E & o(a) | E zyklisch? |
|
4 8 16 6 3 5 7 11 32 |
2
4 8 2 2 4 6 10 6 |
{1,3} : 1,2
{1,3,5,7} : 1,2,2,2 {1,3,5,7,9,11,13,15} : 1,4,4,2,2,4,4,2 {1,5} : 1,2 {1,2} : 1,2 {1,2,3,4} : 1,4,4,2 {1,2,3,4,5,6} : 1,3,6,3,6,2 {1,2,3,4,5,6,7,8,9,10}: 1,10,5,... {1,2,4,5,7,8} : 1,6,3,6,3,2 |
Ja, E ≡ C2
Nein Nein Ja, E ≡ C2 Ja, E ≡ C2 Ja, E ≡ C4 , E=<2>=<3> Ja, E ≡ C6 , E=<3>=<5>, 3=5-1 Ja, E ≡ C10 Ja, E ≡ C6 |
Elemente der Untergruppen
Beispiel: Elemente der zyklischen Gruppe mit φ(n)=10
Beispiel: Elemente der zyklischen Gruppe mit φ(n)=6
Was sehen wir jetzt, was schließen wir aus den Beispielen?
1. Vermutung: E(Z/pZ) ist zyklisch ( multiplikative Gruppe des Körpers (Z/pZ))
2. Vermutung: E(Z/2eZ) ist nicht zyklisch, denn E(Z/2eZ) = <5>* <-1>≡C2e-2 x C2
Dazu:
Beispiel 1: n=8, φ(n)= 4
Es gibt drei Untergruppen der Ordnung 2. Daher kann man immer 2 dieser Untergruppen auswählen, um ganz E zu erzeugen. Wähle also zum Beispiel E= <3> * <5>. Dabei erzeugt dieses innere direkte Produkt die Menge {1,3,5,7} mit 3*5 = 7
Beispiel 2: n = 16, φ(n)=8
Hier ist E = C4 x C2 = <3> * <15> = <3> * <-1> = <5> * <15>
Man kann auch hier immer zwei Untergruppen beliebig auswählen, um E zu erzeugen.
Beispiel 3: n = 32, φ(n) = 16
E = C8 x C2 = <5> * <-1>
Ingesamt folgt also, dass E(Z/2eZ) nicht zyklisch ist, denn E(Z/2eZ) = <5>* <-1>≡C2e-2 x C2
Zusatz: Bei ungeraden Primzahlen entfällt die <-1> und es folgt, dass E dann zyklisch ist.
Beweis der ersten Vermutung
[Existieren Elemente der Ordnung p-1? Beh.: E(Z/pZ) = Cp-1 . In Cp-1 gibt es zu jedem Teiler k von p-1 genau eine Untergruppe der Ordnung k, also hat Cp-1 höchstens k Elemente der Ordnung k.]
E(k):= {x є E | o(x) teilt k} : xk = 1, xk - 1 = 0 ; dh, x ist Nullstelle von Xk - 1 є K[X] mit K[X] = Z/pZ
Also ist | E(k) | ≤ k. Warum?
p(X) = (X-x1)...(X-xr) q(X) = ? = (X-x1´)...(X-xs´)
Angenommen, p(X) = (X-x1)p2(X)
x2 ist Nullstelle von p, daraus folgt dann, dass x2 Nullstelle von p2 ist.
Dann folgt mit Division mit Rest für Polynome über Körper, dass (X-x2) | p2(X).
Also sind die Nullstellen eindeutig bestimmt.