1

Karl Schwalen 1.12 (Stand 11.14)

Prime Restklassengruppen Aufbau und Eigenschaften

Weitere Aufsätze des Verfassers unter http://www.primath.homepage.t-online.de Vorliegend handelt es sich um ein Kompendium elementarer Aussagen mit Bezug zu den primen Restklassengruppen, ergänzt um Beispiele und einige nur experimentelle Ergebnisse. Übersicht zum Inhalt: Seite

1. Zusammenhang mit dem Ring (Z n +, ⋅) ......................................... 2 2. Bestimmung der Gruppenelemente und ihrer Inversen ...................... 2 3. Ordnung der Gruppe ....................................................................... 4

– Eigenschaften der Euler’schen ϕ - Funktion ....................... 4 4. Ordnung der Gruppenelemente ................................................... 6

– Sätze betr. Elementordnung ................................... 6 – Anzahl primer Restklassen vorgegebener Ordnung .......... 8 – Berechnung der Ordnung eines Elementes ....................... 12 – Teilersuche via Elementordnung ................................... 13

5. Zyklische prime Restklassengruppen ...................................... 14 – Bestimmung von Primitivwurzeln ................................. 14

6. Untergruppen ........................................................................ 15 – *

nZ ist zyklisch ............................................. 15

– *nZ ist nicht zyklisch ............................................. 16

– Anzahlen zyklischer / nicht-zyklischer Untergruppen ... 17 7. Die Untergruppe „Quadratische Reste“ ...................................... 22

– Verteilung der qua. Reste in *nZ .................................. 22

– Anordnung in zykl. Untergruppen ................................. 23 – Anzahl qua. Reste in *

nZ ............................................. 23

– Max. QR-Untergruppen ............................................ 24 8. Zu *

nZ isomorphe Gruppen ................................................. 25

9. Elementarteiler; Struktur; Minimale Erzeugendensysteme ........... 27 Vorbemerkung: Die Beweise zu den aufgeführten Aussagen findet man in zahlreichen Büchern / Skripten der elementaren Gruppen- bzw. Zahlentheorie angegeben. Die meisten Aussagen, die hier nur auf *nZ bezogen werden, gelten natürlich in viel allgemeinerem

Zusammenhang, nämlich generell für endliche abelsche oder noch allgemeinere Gruppen, ohne dass dieses laufend besonders angemerkt wird. Es wird durchgängig die multiplikative Schreibweise verwendet. Wegen der umständlicheren Schreibweise wird hier die Bezeichnung (Z / nZ)×, die zum Ausdruck bringt, dass es sich um die Einheitengruppe des Faktorrings zum Ring Z handelt, nicht verwendet. Ebenso wird die unendlich viele Zahlen umfassende Restklasse a vereinfachend durch den Vertreter a angegeben, wobei im konkreten Fall für a hier der kleinste positive Vertreter gewählt wird. Eine mit p bezeichnete Zahl ist im folgenden ausnahmslos eine Primzahl; ebenso bedeutet u stets eine ungerade Zahl.

2

1. Zusammenhang mit dem Ring (Z n +, ⋅⋅⋅⋅) Die Elemente des Ringes (Z n +, ⋅) = {0, 1, ....., n – 1} bilden bezüglich der Multiplikation schon deshalb keine Gruppe, weil das Element 0 nicht invertiert werden kann. Aber auch Z n \ {0} stellt für zusammengesetzte n keine Gruppe dar, da es stets Produkte von Elementen a ≠ 0, b ≠ 0 gibt mit a⋅b = 0; d.h. die „Abgeschlossenheit“ ist nicht gegeben. Die bezüglich der Multiplikation invertierbaren Elemente – also die Einheiten des Ringes (Z n +, ⋅) bezeichnet man als „prime Restklassen modulo n“. (Die Verknüpfungen werden im Weiteren bei der Bezeichnung weggelassen, da vorliegend diesbezüglich keine Irrtümer möglich sind.) Ein Element a ∈ Z n ist genau dann invertierbar, wenn es ein b∈ Z n gibt, so dass a⋅b ≡ 1 mod n. Ein zu a inverses Element existiert genau dann, wenn ggT(a, n) = 1. Damit ist die Menge der primen Restklassen in Z n (im kleinsten pos. Vertretersystem)

gegeben als Zn* = {a ∈ {1, 2,...., n – 1}| ggT(a, n) = 1}.

*nZ ist eine endliche abelsche – also kommutative – Gruppe (d.h. für beliebige a, b ∈ *

nZ gilt

a⋅b = b⋅a) mit der Multiplikation (mod n) als Verknüpfung. (Die Elemente von Z n \ {0}, die keine Einheiten sind, werden ’Nullteiler’ genannt.)

2. Bestimmung der Gruppenelemente a und ihrer Inversen a – 1

Es ist per Definition: a⋅a – 1 ≡ 1 mod n. a – 1 ist daher Lösung der linearen Kongruenz a⋅x ≡ 1 mod n. Der erweiterte Euklidische Algorithmus (EEA) prüft, ob der ggT(a, n) = 1 ist (also ob a ein Element aus *nZ ist). Wenn ja, liefert der Algorithmus (im gleichen

‚Arbeitsgang’) zusätzlich das zu a inverse Element a – 1. Alg. EEA Eingabe: a, n (natürliche Zahlen) b = a; b1 = n; x = 1; x1 = 0; k = 0; k1 = 1 Do while b1 <> 0 v = b div b1; b2 = b – v⋅b1 x2 = x – v⋅x1; k2 = k – v⋅k1 b = b1; b1 = b2; x = x1; x1 = x2; k = k1; k1 = k2 Loop d = b Ausgabe: d, x, k mit d = x⋅a + k⋅n Wenn a ∈ Z n und d = 1 → a ∈ *

nZ und a –1 = x.

Eine andere Möglichkeit zur Inversenberechnung bietet der Satz von Fermat-Euler: Falls ggT(a, n) =1 folgt aus aϕ (n) ≡ 1 mod n: a – 1 ≡ aϕ (n) – 1 mod n. Ist n eine Primzahl (n = p) gilt insbesondere a – 1 ≡ a p – 2 mod n. Diese Methode erfordert die Kenntnis von ϕ (n), und dazu muss in der Regel die Faktorisierung von n bekannt sein (siehe folgende Ziffer). Einige typische Beispiele:

Z7

* : Elemente : 1 2 3 4 5 6 Z8* : Elemente: 1 3 5 7

Inverse: 1 4 5 2 3 6 Inverse: 1 3 5 7 Z9

* : Elemente : 1 2 4 5 7 8 Z15* : Elemente: 1 2 4 7 8 11 13 14

Inverse: 1 5 7 2 4 8 Inverse: 1 8 4 13 2 11 7 14

3

Aus den Beispielen liest man ab: a ∈ *nZ → n – a (= – a) ∈ *

nZ , was klar ist, wegen

ggT (a, n) = ggT(a + n⋅k, n); k ∈ Z. Außerdem gilt für alle a: a – 1 + (n – a) – 1 = n. Die Elemente 1 und n – 1 sind zu sich selbst invers („selbst-invers“). Bei zyklischen primen Restklassengruppen sind das die beiden einzigen Elemente mit dieser Eigenschaft. Im Falle n = 8 (siehe Beispiel) sind sogar alle Elemente selbst-invers. Das gilt für die Moduln n ∈ { 1, 2, 3, 4, 6, 8, 12, 24 }. Ist *

nZ zyklisch, gilt für das Produkt aller a i ∈ *nZ : Π a i ≡ –1 mod n. Das lässt sich wegen

a⋅a – 1 ≡ 1 mod n leicht verifizieren: Das Element 1 liefert zu dem Produkt auf der linken Seite der Gleichung den Faktor 1; das Element n – 1 den Faktor – 1. Die übrigen Elemente von *

nZ

lassen sich zu Paaren a⋅a – 1 zusammenfassen, die jeweils den Faktor 1 liefern. Ist n = p, sind alle natürlichen Zahlen 1, ......, p – 1 prime Restklassen und damit folgt unmittelbar der Satz von Wilson: (p – 1)! ≡ –1 mod p. Ist n keine Primzahl, gilt das wegen der vorhandenen Nullteiler und weiterer selbst-inverser Elemente nicht. Die Paare zueinander inverser Elemente sind „wie zufällig“ verteilt, denn für großes n ist – unabhängig davon, ob n prim oder zusammengesetzt ist – der mittlere, rel. Abstand Σ |ai – ai

– 1| / (ϕ (n) ⋅ n) ≈ 1 / 3. (Die Summe ist über alle ai ∈ *nZ zu erstrecken.)

Der Aufbau der Gruppentafel von *nZ soll am Beispiel n = 15 gezeigt werden.

×××× 1 2 4 7 8 11 13 14 1 1 2 4 7 8 11 13 14 2 2 4 8 14 1 7 11 13 4 4 8 1 13 2 14 7 11 7 7 14 13 4 11 2 1 8 8 8 1 2 11 4 13 14 7 11 11 7 14 2 13 1 8 4 13 13 11 7 1 14 8 4 2 14 14 13 11 8 7 4 2 1

In jeder Zeile und Spalte kommen alle primen Restklassen(-Vertreter) der Gruppe vor, aber jeweils in anderer Reihenfolge. Die Anordnung ist symmetrisch zu der von rechts oben nach links unten verlaufenden Diagonalen, was Folge der Kommutativität ist. Das gilt unabhängig von der Reihenfolge, in der die primen Restklassen in der Tafel angeordnet werden. Wählt man als Anordnung der Elemente der Kopf-Spalte bzw. -Zeile die ‚natürliche’*) Reihenfolge (kleinste pos. Restklassenvertreter der Größe nach angeordnet – wie oben geschehen), ist die Tafel auch zu der von links oben nach rechts unten verlaufenden Diagonalen symmetrisch. Da sich außerdem die symmetrisch zu den beiden gestrichelten Linien angeordneten Elemente immer zum Modul n ergänzen, müssen zur Aufstellung der Gruppentafel von den 64 nur die 6 blau markierten Elemente wirklich per Multiplikation mod n berechnet werden, da man die erste bzw. letzte Zeile / Spalte ‚abschreiben’ kann und die übrigen Zahlen sich durch Drehung bzw. Spiegelung des markierten Segmentes ergeben. ------------------- * ) Im Fall einer beliebigen Gruppe, in der die Elemente z.B. mit a, b, c, .... bezeichnet werden, ist eine solche Anordnung nicht definiert.

4

3. Anzahl der Gruppenelemente: Ordnung von *nZ

| *

nZ | = ϕ (n) „Eulersche-Funktion“ = Anzahl der zu n teilerfremden

positiven Zahlen < n • Berechnung von ϕ (n)

Wegen ϕ (a⋅b) = ϕ (a) ⋅ ϕ (b) für ggT(a, b) = 1 (mit der Setzung ϕ (1) = 1 handelt es sich um eine multiplikative „zahlentheoretische Funktion“) folgt mit

n =∏∞

=

α

1ii

ip : ϕϕϕϕ (n) = ∏∞

=

αϕ1i

i )p( i = n )p

11(

n|p∏ −

Dabei ist ϕ (pα) = pα – pα – 1 = pα – 1(p – 1) z.B. ϕ (2x) = 2x – 1

Für quadratfreies n vereinfacht sich die Berechnung zu ϕ (n) = Π (pi – 1). Tabelle für die ersten Werte der Euler’schen ϕ-Funktion: n: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ϕ (n):1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 12 18 12 28

• Einige Eigenschaften von ϕ (n)

– Σ ϕ (d) = n, wobei d alle Teiler von n durchläuft – Der Graph von ϕ (n) beschreibt konsequent eine „Zick-Zack-Kurve“

Behauptung: Es gibt kein n, für das gilt: ϕ (n – 1) < ϕ (n) < ϕ (n + 1) bzw. ϕ (n – 1) > ϕ (n) > ϕ (n + 1)

– ϕ (n) ist für n > 2 stets gerade. Aber es kommen durchaus nicht alle geraden Zahlen als Werte von ϕ (n) vor. Dabei handelt es sich bevorzugt um Zahlen der Form 2⋅p. Z.B. existieren keinen primen Restklassengruppen der Ordnung 2⋅7, 2⋅13, 2⋅17, 2⋅31, 2⋅37. Insgesamt nimmt die „Belegungsdichte“ mit größer werdenden Zahlen immer mehr ab: Von den ersten 100 geraden Zahlen kommen 71 % als Funktionswert ϕ (n) vor; bei den ersten 104 geraden Zahlen sind es nur noch rd. 45%. Wegen ϕ (2) =1 gilt ϕ (2u) = ϕ (u). Wenn alle geraden Zahlen als Funktionswert zur Verfügung stünden, würde jeder Wert genau doppelt belegt. Da das aber nicht der Fall ist, hat ϕ (n) notwendigerweise häufig für eine größere Anzahl von n-Werten den gleichen Wert. Z.B.: ϕ (n) Anzahl verschiedene n 2 3: 3, 4, 6

4 4: 5, 8, 10, 12 8 5: 15, 16, 20, 24, 30 ..... ...... 24 10 davon 3 ungerade 72 17 davon 6 ungerade

8640 176 davon 43 ungerade

5

Die Konzentration auf einen bestimmten Funktionswert ist um so stärker, desto mehr Teiler die betreffende Zahl besitzt.

– Ist ϕ (n) ≡ 2 mod 4, dann ist *nZ zyklisch; d.h. n ∈ {1, 2, 4, p j, 2p j

(p > 2)}. (Die Umkehrung gilt natürlich nicht.) Neben n = 4 führen genau die Zahlen der Form n = p j sowie n = 2p j mit j > 0 und p ≡ 3 mod 4 auf ϕ (n) ≡ 2 mod 4. Im Bereich bis 105 sieht die „Statistik“ wie folgt aus: Für 7484 Werte von n ist ϕ (n) ≡ 2 mod 4, davon sind 4808 Primzahlen, 2583 sind das zweifache einer Primzahl und für 93 ist n = p j bzw. 2p j mit j > 1. Insgesamt gibt es in dem Bereich aber nur 4845 verschiedene ϕ (n)-Werte mit ϕ (n) ≡ 2 mod 4, da ϕ (2n) = ϕ (n) und von den 93 fraglichen Primzahlpotenzen belegt nur etwa ein Drittel (genau 37) einen ϕ (n)-Wert, der nicht bereits durch den ϕ (n)-Wert einer Primzahl belegt ist. Weil die höheren Primzahlpotenzen nur einen relativ kleinen Beitrag leisten, hat man also die Näherung: Für große m ist |{ϕ (n) : n < m : ϕ (n) ≡ 2 mod 4 }| ≈ π (m) / 2.

– ϕ (n) ist in den folgenden Fällen eine Zweierpotenz 2x: n = 2α ⋅k, wobei

k eine der 32 verschiedenen Zahlen ist, die sich als Produkte der 5 Fermat’schen Primzahlen (zuzüglich der 1) bilden lassen. Also k ∈ {1, 3, 5, 17, 257, 56537, 3⋅5, 3⋅17, ..... , 5⋅17⋅257,....}

– Der Maximalwert des Quotienten x / ϕ (x), wobei x kleiner einem

vorgegebenen n ist, ist ∏∏==

−k

1ii

k

1ii )1p(/p . k ist so zu wählen, dass

2⋅3⋅...⋅pk < n ist. Beispiel: n = 208; 2⋅3⋅5⋅7 = 210 > 208 → k = 3 Max [x / ϕ (x)]x < 208 = 2⋅3⋅5 / 1⋅2⋅4 = 3,75 (Der Minimalwert ist px / (px – 1) wobei px die größte Primzahl ≤ n ist.)

– Besitzt eine Zahl n zwei (unbekannte) Primteiler (p und q), lassen diese sich aus der Kenntnis von ϕ (n) bestimmen: ϕ (n) = (q – 1)⋅(p – 1) = n – p – q + 1. Mit Hilfe von q = n / p ergibt sich p2 + p⋅(ϕ (n) – n – 1) + n = 0 und daraus die Lösungen p und q:

p, q = (n + 1 – ϕ (n) ± n4))n(1n( 2 −ϕ−+ ) / 2.

– Ist n = p⋅q, kann man ϕ (n) auch als Funktion des Teilerverhältnisses

v = q / p (q ≥ p) angeben : ϕ (n) = n – n / p – p + 1. Mit q = v⋅p →

n = p2⋅v → p = n / v → ϕ (n) = n – n ( v + 1 / v ) + 1 Kennt bzw. vermutet man den Bereich, in dem das Teilerverhältnis liegt, ergibt sich der Bereich, in dem ϕ (n) zu suchen ist. Z.B.:

vmax = 4 → ϕ (n)min = n – (5 / 2)⋅ n + 1. ϕ (n) ist maximal für v = 1.

Damit: ϕ (n)max = n – 2 n + 1 → ∆ϕmax = n / 2. ϕ (n) ist demnach eine im Bereich ϕ (n)min ....... ϕ (n)max liegende, durch 4 teilbare nat. Zahl.

6

4. Ordnung der Gruppenelemente Als „Ordnung der primen Restklasse a mod n“ wird der kleinste Exponent m bezeichnet, für den a m ≡ 1 mod n gilt. Abgekürzt: ord n a = m (Dass ein solches m existiert, garantiert der Satz von Fermat-Euler.) Mit „ Exponent von *

nZ “ wird der minimale Wert von s bezeichnet, für den gilt:

a s ≡ 1 mod n für alle a ∈ *nZ . Also: ε (n) = min { s: as ≡ 1 mod n für alle a ∈ *

nZ }

( ε (n) ist zugleich die maximale Ordnung eines Elementes aus *nZ .)

• Eigenschaften der Elementordnung

– ordn a | ϕ (n) „Elementordnung teilt Gruppenordnung“ – p | ϕ (n) → Es existiert ein a mit ord a = p.

– Sei ϕϕϕϕ (n) = p x ⋅⋅⋅⋅ k mit ggT(p, k) = 1 →→→→ Es gibt genau k Elemente,

deren Ordnung nicht durch p teilbar ist. (Beweis?)

– ord a = ord a– 1 Folglich kommen die Ordnungen nicht selbst-inverser Elemente mindestens zweimal in *nZ vor.

– selbst-inverse Elemente > 1 haben Ordnung 2.

– ord at = ord a / ggT(t, ord a) “Elementordnungssatz”

– ord (a⋅b) | kgV(ord a, ord b) Für ggT(ord a, ord b) = 1 folgt

ord (a⋅b) = ord a⋅ ord b. (Ist also ein a mit ungerader Ordnung u bekannt, hat man mit (a⋅(n-1)) mod n ein Element der Ordnung 2⋅u.)

– Es existiert ein Element c mit ord c = kgV(ord a, ord b). – ord (n – a) = f ⋅ord a mit f ∈ {½, 1, 2}

– Im Fall n = p ≡ 3 mod 4 unterscheiden die Ordnungen von a und n – a

sich immer um den Faktor 2.

– ai ≡ ai mod ord a mod n (Vereinfacht die Berechnung für große i.)

– Sei ggT(a, n) = 1, n keine Primzahl und an – 1≡ 1 mod n (also ist n pseudoprim zur Basis a) → ord a | n – 1 (obgleich n – 1 ≠ ϕ (n))

– Ist *

nZ zyklisch → Zu jedem Teiler d von ϕ (n), gibt es genau ϕ (d)

prime Restklassen der Ordnung d. Insbesondere existieren ϕ (p – 1) Elemente der Ordnung p – 1, falls n = p.

– Ist a quadratischer Nichtrest → ord a ist gerade. (Die Umkehrung gilt

nicht.)

7

– Die maximale Ordnung einer primen Restklasse in *nZ – also ε (n) –

bestimmt sich folgendermaßen:

Es sei n = 2 e ⋅ 11pα ⋅.....⋅ k

kpα mit k verschiedenen, ungeraden Primzahlen

p1,..., pk → ε (n) = kgV( f, ϕ( 11pα ), ...., ϕ( k

kpα )) 1 für e < 2

Darin ist f = 2 für e = 2 2e – 2 für e > 2 (Im englischsprachigen Raum wird anstelle ε (n) auch die Bezeichnung Carmichael-Funktion λ(n) verwendet.)

– ord a | ε (n) | ϕ (n); 2| ε (n) für n > 2. Für jeden Teiler t von ε (n) existieren Elemente a in *nZ mit ord a = t.

Zwecks Übersicht noch einige typische Beispiele aus denen die „fast-symmetrische“ Verteilung der Elementordnungen deutlich wird. n = 5 ϕ (5) =2 2 n = 13 ϕ (13) = 2 2⋅3 a: 1 2 3 4 a: 1 2 3 4 5 6 7 8 9 10 11 12 ord a: 1 4 4 2 ord a: 1 12 3 6 4 12 12 4 3 6 12 2

n = 7 ϕ (7) = 2⋅3 n = 11 ϕ (11) = 2⋅5 a: 1 2 3 4 5 6 a: 1 2 3 4 5 6 7 8 9 10 ord a: 1 3 6 3 6 2 ord a: 1 10 5 5 5 10 10 10 5 2 n = 15 ϕ (15) = 2⋅2 2 n = 16 ϕ (16) = 2 3 a: 1 2 4 7 8 11 13 14 a: 1 3 5 7 9 11 13 15 ord a: 1 4 2 4 4 2 4 2 ord a: 1 4 4 2 2 4 4 2 n = 21 ϕ (21) = 2⋅2⋅3 n = 9 ϕ (9) = 2⋅3 a: 1 2 4 5 8 10 11 13 16 17 19 20 a: 1 2 4 5 7 8 ord a: 1 6 3 6 2 6 6 2 3 6 6 2 ord a: 1 6 3 6 3 2 n = 19 ϕ (19) = 2⋅3 2 a: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ord a: 1 18 18 9 9 9 3 6 9 18 3 6 18 18 18 9 9 2 Die Beispiele bestätigen folgende Regeln:

– Ist für a > 1 ord a =2 x → ord (n – a ) = 2 x. Das gilt insbesondere für die selbst-inversen Elemente (x = 1) sowie im Fall ϕ (n) = 2 e.

– Ist ord a = u → ord (n – a) = 2u

Im Fall ϕ (n) ≡ 2 mod 4 gilt auch die Umkehrung: ord a = 2u hat ord (n – a) = u zur Folge.

8

• Anzahl primer Restklassen mod n mit vorgegebener Ordnung Die „Anzahl-Funktion der Elementordnungen“

Dieser Punkt erfährt eine ausführlichere Darstellung, da in der eingesehenen Literatur keine geschlossene Abhandlung dazu gefunden wurde. α) Anzahl primer Restklassen mod n, deren Ordnung Potenz einer Primzahl ist

Gegeben: n = 2 e⋅ 11pα ⋅....⋅ k

kpα mit α i > 0 und e ∈ {0, 1, 2, ....}

Gesucht ist die Anzahl )n(

p hA der primen Restklassen in *nZ mit ord a = ph, wobei p

eine beliebige Primzahl ist: )n(

p hA = |{ a : ord a = ph : a ∈ *nZ }|

Klarerweise kommen für p nur die Primteiler von ϕ (n) in Frage. Behauptung:

Es gilt die Rekursion: ∑−

=−=

1

0

1h

fp

t)n(

p fh

h A)p(A mit 0pA = 1 (nur die „1“ weist die

Ordnung 1 auf). Rechnet man (durch sukzessives Einsetzen) die Summe in vorstehender Formel aus, ergibt das:

)1p(pA hhh

ts)n(

p−−−−⋅⋅⋅⋅==== mit ∑∑∑∑

−−−−

========

1h

1ffh ts (*)

Die Werte von t h bzw. t f bestimmt man wie folgt aus dem zu *nZ isomorphen

direkten Produkt (additiver) zyklischer Restklassengruppen, welches man (mit einer Ausnahme) unmittelbar aus ϕ (n) erhält (siehe Ziffer 8):

*nZ ≅ H × Z / )1p(p 1

11

1 −−α Z × ....× Z / )1p(p k1

kk −−α Z

Darin ist H = Z / 2 e – 1 Z für e < 3 bzw. H = Z / 2Z × Z / 2 e – 2 Z für e > 2 t h ist die Anzahl der Faktoren des vorstehenden direkten Produktes, deren Ordnung von ph geteilt wird; analog t f . Nutzt man die Rekursion s h = s h – 1 + t h – 1 mit s 0 = 0 und t 0 = 0, reicht es zur Berechnung vonhp

A aus, – beginnend mit h = 1 – für jedes

h den Wert von t h abzuzählen. β) Anzahl der primen Restklassen mod n, deren Elementordnung mehr als einem Primteiler enthält Es gilt: A v ⋅⋅⋅⋅ w = A v ⋅⋅⋅⋅ A w für ggT(v, w) = 1 Wenn man die Anzahlen für alle Primzahlpotenzen, die ϕ (n) teilen, gemäß den unter α) aufgeführten Regeln bestimmt, lässt sich somit für jeden Teiler d von ε (n) – und nur genau für diese, denn weitere Produkte der geforderten Art lassen sich nicht bilden – die Anzahl der Elemente mit Ordnung d aus der Primfaktorzerlegung des betr. Teilers errechnen. Infolge Multiplikativität und A1 = 1 für alle p erfüllt diese Anzahl-Funktion die Definition einer ‚multiplikativen zahlentheoretischen Funktion’. In Analogie zur Euler’schen ϕ-Funktion ist auch )n(A

)n(|dd ϕ=∑

ϕ, wobei nur die

Teiler einen Beitrag liefern, die ε (n) teilen.

9

Ein ausführliches Beispiel:

n = 25 ⋅ 33 ⋅ 19 ⋅ 43 = 705.888 ϕ (n) = (2)⋅⋅⋅⋅(23)⋅⋅⋅⋅(32⋅⋅⋅⋅2)⋅⋅⋅⋅(2⋅⋅⋅⋅32)⋅⋅⋅⋅(2⋅⋅⋅⋅3⋅⋅⋅⋅7) = 217.728 Die Faktoren sind entsprechend

der Klammerung auszuwerten. ε (n) = kgV(2, 23, 32⋅2, 2⋅32, 2⋅3⋅7):

2 23 Teileranzahl von ε (n):

2 32 2 32 (3 + 1) ⋅ (2 + 1) ⋅ (1 + 1) = 24 2 3 7

kgV: 23 ⋅ 32 ⋅ 7 = 504 = ε (n) Elementordnung Anzahl der Elemente (Teiler von ε (n)) gezählt berechnet

1 1 A1 = 1 2 31 p = 2; t1 = 5 → A2 = 25 – 1 = 31 3 26 p = 3; t1 = 3 → A3 = 33 – 1 = 26 4 32 p = 2; t2 = 1 → A4 = 25⋅(21 – 1) = 32 6 (= 2⋅3) 806 A2 ⋅ A3 7 6 p = 7; t1 = 1 → A7 = 71 – 1 = 6 8 64 p = 2; t3 = 1 → A8 = 2(5+1)⋅(21 – 1) = 64 9 216 p = 3; t2 = 2 → A9 = 33⋅(32 – 1) = 216 12 832 A3 ⋅ A4 14 186 A2 ⋅ A7 18 6696 A2 ⋅ A9

21 156 A3 ⋅ A7 24 1664 A3 ⋅ A8 28 192 A4 ⋅ A7

36 6912 A4 ⋅ A9 42 4836 A2 ⋅ A3 ⋅ A7 56 384 A7 ⋅ A8 63 1296 A7 ⋅ A9 72 13824 A8 ⋅ A9 84 4992 A3 ⋅ A4 ⋅ A7 126 40176 A2 ⋅ A7 ⋅ A9 168 9984 A3 ⋅ A7 ⋅ A8 252 41472 A4 ⋅ A7 ⋅ A9 504 82944 A7 ⋅ A8 ⋅ A9 Summe: 217728

Ein weiteres Beispiel: ϕ (n) = 4 trifft für die Zahlen n ∈ {5, 8, 10, 12} zu. n = 5 → ϕ (5) = (4) → p = 2; t1 = 1; t2 = 1→ A2 = 21 – 1 = 1; A4 = 21⋅(21 – 1) = 2 n = 8 = 23 → ϕ (8) = (2)⋅(2) → p = 2; t1 = 2 → A2 = 22 – 1 = 3 n = 10 → ϕ (10) = (1)⋅(4) wegen A1 = 1 verläuft die Berechnung wie für n = 5 n = 12 = 22⋅3 → ϕ (12) = (2)⋅(2) → wie für n = 8: A2 = 3

10

γ) Begründung der Aussagen in α): Gemäß Definition der Elementordnung gilt: Ist für ein a ∈ *

nZ a m ≡ 1 mod n und für jeden

Teiler t von m a m / t ≡/ 1 mod n, dann ist m = ord a.

Es sei nun zunächst n = q k mit einer Primzahl q > 2, d.h. *nZ ist zyklisch. Wie in Ziffer 4.

angegeben, gibt es dann zu einem Teiler p m ( m > 0) von ϕ (q k) genau ϕ (p m) [= p m – p m – 1] Elemente der Ordnung p m . Dieses Ergebnis erklärt sich wie folgt aus der Betrachtung der Lösungsanzahl der Kongruenz x d – b ≡ 0 mod q k . Es gilt allgemein *): Wenn x d – b ≡ 0 mod q k lösbar ist gibt es ...

– q Primzahl > 2 ggT(d, ϕ(q k)) inkongruente Lösungen zum Modul q k

– q = 2 α) 1 ≤ k <3: ggT(d, 2 k – 1) Lösungen β) k ≥ 3: 2⋅ggT(d, 2 k – 2) Lösungen. Vorliegend ist b = 1; die Kongruenzen sind immer lösbar, da x = 1 in allen Fällen eine Lösungsrestklasse ist.

Im speziellen Fall d = p m besitzt mpx – 1 ≡ 0 mod q k ......

– q Primzahl > 2

...... mpL = ggT(p m, (q – 1)⋅q k – 1) Lösungen

– q = 2 (und p = 2; für p > 2 ist die Lösungsanzahl stets gleich 1)

...... m2L = ggT (2 m + 1, 2 k – 1)) Lösungen.

(Für p = 2 kann man so die Fallunterscheidung in k < 3 bzw. k > 2 vermeiden) Klar ist auch, dass alle Lösungen x i prime Restklassen zum Modul sind: Sei x 0 eine nicht zum Modul teilerfremde Lösung, also x 0 = q e (e >0) →→→→

mpeq ⋅ – 1 ≡ 0 mod q k Es ist daher q k <mpeq ⋅ →→→→ q k |

mpeq ⋅ →→→→ mpeq ⋅ ≡ 0 mod q k →→→→ Widerspruch

Wenn x1 eine Lösung von 1mpx

−– 1 ≡ 0 mod q k ist, löst x1 natürlich ebenfalls

mpx – 1 ≡ 0 mod q k . Da hier aber gemäß Definition der Ordnung nur die Lösungen gezählt werden, die ausschließlich den Exponenten p m betreffen, gilt mp

A = mpL – 1mp

L − (**)

Wenn (voraussetzungsgemäß) p m | ϕ (q k) gilt, ist mpA = p m – p m – 1.

Im Fall q = 2 gilt (**) ebenfalls.

Leider kann man im allgemeinen Fall n = 2 e⋅ 11pα ⋅....⋅ k

kpα die Anzahlen mpA der einzelnen

zyklischen Faktoren nicht einfach multiplizieren, sondern muss zunächst wieder die Anzahl

der Lösungen der Kongruenz mpx – 1 ≡ 0 mod n bestimmen. Dazu sind die Lösungsanzahlen

der Faktoren von n für jedes p m miteinander zu multiplizieren. -------------- *): siehe z.B. das im Netz verfügbare Skript „Polynomkongruenzen“ von Chr. Nelius, Uni Paderborn

11

Ein Beispiel: n = 2 4 ⋅3 3 ⋅11 ⋅19 ϕ (n) = (2 3)⋅(2⋅3 2)⋅(2⋅5)⋅(2⋅3 2) Die Primteiler in ϕ (n) sind 2, 3 und 5; die Anzahlen der Elemente in *

nZ , deren Ordnungen

Potenzen dieser Primteiler sind, werden bestimmt:

n: 2 4 ⋅ 11 ⋅ 3 3 ⋅ 19

ϕ (n): 2 3 ⋅ 2⋅5 ⋅ 2⋅3 2 ⋅ 2⋅3 2 p h Lösungsanzahl mp

L Π L mpA

p 0 : 1 1 1 1 1 1 2 : 4 2 2 2 32 31 ( = 32 – 2 0) 2 2: 8 (2) (2) (2) 64 32 ( = 64 – 32 ) 2 3: (8) (2) (2) (2) 64 0 ( = 64 – 64 ) 3 : (1) (1) 3 3 9 8 ( = 9 – 3 0 ) 3 2: (1) (1) 9 9 81 72 ( = 81 – 9 ) 3 3: (1) (1) (9) (9) 81 0 ( = 81 – 81 ) 5 : (1) 5 (1) (1) 5 4 ( = 5 – 5 0 ) 5 2: (1) (5) (1) (1) 5 0 ( = 5 – 5 )

Die in Klammern gesetzten Einträge der Tabelle sollen andeuten, dass die betreffende Primzahlpotenz p h teilerfremd zu ϕ (q k) ist (1), oder dass die Lösungsanzahl sich gegenüber derjenigen von ph – 1 nicht erhöht hat; z.B. (8). Die Spalte Π L enthält das Produkt der Faktoren aus den vorhergehenden Spalten, d.h.

die Gesamtanzahl mpL der Lösungen von

mpx – 1 ≡ 0 mod n. Die letzte Spalte zeigt,

dass auch hier wieder gilt: mpA = mp

L – 1mpL − .

Somit hat man alternativ zu (*) aus lit. α) folgende Formel zu Berechnung der Elemente-Anzahl mit Ordnung pm (mit pm|ϕϕϕϕ(n)) in *

nZ :

Sei n = ∏=

αk

1i

iiq mit qi Primzahl und αi > 0

a) n ist nicht durch 8 teilbar

)n(

p mA = ∏∏∏∏====

−−−−αααα⋅⋅⋅⋅−−−−k

1i

1ii

m )q)1q(,p(ggT i ∏∏∏∏====

−−−−αααα−−−− ⋅⋅⋅⋅−−−−−−−−k

1i

1ii

1m )q)1q(,p(ggT i (m > 0)

b) n ist durch 8 teilbar Wie vorstehend; mit der Ausnahme, dass im Fall p = 2 ....

– im ersten Term bei der ggT-Berechnung m durch m + 1 zu ersetzen ist, und

– im zweiten Term bei der ggT-Berechnung m – 1 durch m zu ersetzen ist, wenn m > 1. (Ist m = 1, ist der gesamte zweite Term stets gleich 1.)

Für )n(

2A – das ist die Anzahl der selbst-inversen Elemente der Ordnung 2 – kann man sich die

o.a. Berechnungen ersparen, da 2| )q( iiαϕ für alle q i. Sei n = 2 e⋅ 1

1pα ⋅....⋅ kkpα . Dann gilt:

)n(

2A = 2 f – 1 mit f = → Ist *nZ zyklisch, → A 2 = 1.

k für e < 2 k + 1 für e = 2 k + 2 für e > 2

12

• Berechnung der Ordnung eines Elementes

Ist die Primfaktorzerlegung von n bekannt, kann man zur Berechnung der Ordnung die Tatsache ausnutzen, dass d genau dann die Ordnung von a ist, wenn a d ≡ 1 mod n und für alle Primteiler von d gilt: a d/p ≡/ 1 mod n. Zweckmäßigerweise wird man zunächst ε (n) bestimmen und mit d = ε (n) / 2 beginnen. Ist nun a d/p ≡ 1 mod n für ein p, so startet man das Verfahren mit dem d* = d / p* erneut, für das als letztes die Bedingung a d* ≡ 1 mod n erfüllt war. Für große n ist das Verfahren a d mod n mittels der Rekursion a x = a x – 1⋅a zu berechnen keine geeignete Methode, sondern es kommt ein Algorithmus zum schnellen Potenzieren zum Einsatz – etwa so wie nachstehend aufgeführt. Alg. „Schnelles Potenzieren modulo n“ (Berechnet a d mod n )

Eingabe: a, d, n x = a: c = d: m = n If c mod n = 0 then y = 1 else y = x Do while c < > 1 c = c div 2: x = (x * x) mod n If c mod 2 = 1 then y = (x * y) mod n Loop Ausgabe: y (= a d mod n)

Kennt man die Zerlegung von n in seine Primfaktoren nicht, ist die Berechnung der Ordnung eines Elementes a mit 1 < a < n – 1 im Allgemeinen wesentlich schwieriger bzw. mit den heute bekannten Methoden undurchführbar. Der folgende „Wechsel-Schritt-Algorithmus“ (anstelle der breit eingeführten, aber dennoch immer wieder gewöhnungsbedürftigen Bezeichnung „baby steps – giant steps“) dürfte z.Z. eines der schnellsten, allgemein einsetzbaren Verfahren sein: Alg. „Elementordnung“ Eingabe: n, a ∈ *

nZ

s = 1: h(1) = s: ks = a: gs = a Do while h(gs) = 0 h(ks) = s + 1 ks = (a * ks) mod n gs = (gs * ks) mod n s = s + 1 Loop v = ( s * ( s + 1)) / 2 – h(gs) + 1 Ausgabe: ordn a = v Wie effizient der Alg. arbeitet, hängt sehr davon ab, wie schnell festgestellt wird, ob an der Stelle h(gs) bereits ein Wert h(ks) gespeichert ist. Vorliegend wird „direkte Adressierung“ angewandt, was wohl die schnellste Variante ist. Reicht der Arbeitsspeicher des Rechners dazu nicht aus, – die Länge von h( )

13

muss in der Größenordnung von n vorgesehen werden – hat man sich Gedanken über geeignete Hash-Tabellen oder Suchbäume zu machen. Die Anzahl der Schleifendurchläufe, die benötigt werden, um ord a zu erhalten,

ist proportional zu aord und somit letztlich zu n , d.h. bei Zahlen > 10 20

ist die Berechnung der Ordnung bereits schwierig. • Bestimmung eines Teilers von n mittels Elementordnung

Dass die Berechnung der Ordnung ein schwieriges Problem darstellt, zeigt sich auch darin, dass die Kenntnis der Ordnung eines Elements a mit 1 < a < n – 1 aus der primen Restklassengruppe modulo n häufig zur Bestimmung eines Teilerpaars von n ausreicht: Der ggT(x – y, n) liefert einen nicht-trivialen Teiler von n, falls x 2 ≡ y 2 mod n und x inkongruent zu ± y ist. Ein Spezialfall ist x 2 ≡ 1 mod n. Nun gilt definitionsgemäß a ord a ≡ 1 mod n für jede prime Restklasse a. Ist m = ord a gerade, so erfüllt x = a m / 2 die Kongruenz x 2 ≡ 1 mod n und ist x außerdem inkongruent zu –1 mod n liefert ggT (a m / 2 mod n – 1, n) einen Teiler von n. (Der Fall x ≡ ± y mod n tritt u.a. immer dann auf, wenn ord a gerade / ungerade ist und ord (n – a) ungerade / gerade ist; wenn also a oder n – a von ungerader Ordnung ist.) Da es zur Faktorisierung wesentlich effizientere Verfahren gibt als zur Bestimmung der Ordnung, ist die Bestimmung der Ordnung via Zerlegung von n in seine Faktoren eher angezeigt als umgekehrt die Zerlegung von n mittels der (geraden) Ordnung einer primen Restklasse. Diese Situation könnte sich ändern, wenn die Entwicklung von Quantencomputern Fortschritte macht.

In Anlage 1 sind einige Sachverhalte dargestellt, die zeigen, dass auch Zusammenhänge zwischen den Teilern einer Zahl n und der Inversenbildung in *

nZ bestehen.

14

5. Zyklische prime Restklassengruppen

*nZ wird als ’zyklisch’ bezeichnet, wenn es (mindestens) ein a ∈ *

nZ gibt, mit

*nZ = < a > = { a1, a2,......, a ϕ (n) = 1}. Somit ist ord a = ϕ (n) = ε (n).

Eine prime Restklassengruppe ist zyklisch für n ∈∈∈∈ {1, 2, 4, p j, 2p j ; p > 2}. Ein Vertreter eines erzeugenden Elementes einer zyklischen primen Restklassengruppe wird auch Primitivwurzel genannt. Ist *nZ zyklisch, gibt es ϕ (ϕ (n)) Primitivwurzeln.

Beispiele: n = 9; ϕ (9) = 6; ϕ (6) = 2 Folglich besitzen in *

9Z zwei Elemente die Ordnung 6; es sind

dies die primen Restklassen 2 und 5 wie folgende Tabelle zeigt. i 1 2 3 4 5 6 2 i mod 9 2 4 8 7 5 1 5 i mod 9 5 7 8 4 2 1

n = 10; ϕ (10) = 4; ϕ (4) = 2 Primitivwurzeln in *

10Z sind 3 und 7

Die Kenntnis von Primitivwurzeln ist z.B. von Interesse für das Rechnen im Körper Zp (Indexrechnung) sowie in der Kryptologie (Stichworte: Diffie-Hellman, El Gamal). • Bestimmung von Primitivwurzeln (PW) Die PW von 1, 2 und 4 sind leicht zu erraten und im Fall p j (j >1;p > 2) gilt: Ist a eine PW mod p, so ist

– falls a p – 1 ≡/ 1 mod p 2 a und / oder – falls (a + p) p – 1 ≡/ 1 mod p 2 a + p eine PW mod p j.

und Ist a eine PW mod p j, so ist – falls a ungerade ist a oder – falls a gerade ist a + p j

eine PW mod 2⋅⋅⋅⋅p j.

Also hat man nur den Fall einer ungeraden Primzahl zu betrachten. Hier ist man allerdings bisher im Wesentlichen aufs Probieren angewiesen. Dabei können folgende Überlegungen hilfreich sein:

- Da ϕ (n) gerade ist, muss die Ordnung der PW für p > 2 gerade sein. Daraus folgt, dass ein quadratischer Rest keine PW sein kann; d.h. a (p – 1)/ 2 ≡ – 1 mod p ist notwendige Voraussetzung, dass a eine PW mod p ist. Präziser:

- a ist genau dann PW mod p, falls pmod1a iq/)1p( ≡/− für alle Primteiler q i von p – 1.

Kennt man eine PW mod p, lassen weitere sich leicht bestimmen: - Ist a PW mod p, dann ist a k mod p ebenfalls PW, falls ggT(k, p – 1) = 1 - Ist a PW mod p und p ≡ 1 mod 4, dann ist p – a ebenfalls PW mod p

- Ist a PW mod p, so auch a – 1

15

In Sonderfällen, in denen ϕ (n) nur wenige Primteiler besitzt, lässt sich von vornherein eine PW angeben: - Für die Fermat’schen Primzahlen ist jeder quadratische Nichtrest eine PW. - Seien q und p = (q – 1) / 2 > 2 Primzahlen (q ist sog. Germain-Primzahl) Dann gilt: -- Ist p ≡ 1 mod 4 → 2 ist PW mod q (anders formuliert: Ist p = 2⋅k – 1 und q = 4⋅k – 1 → 2 ist PW mod q) -- Ist p ≡ 1 oder 3 mod 10 → 5 ist PW mod q -- Ist p ≡ 5 mod 14 → 7 ist PW mod q - Seien q und p = (q – 1) / 4 Primzahlen (q ist sog. Stern-Primzahl) Dann gilt:

-- 2 ist PW mod q -- p ≡ 1 mod 3 → 3 ist PW mod q.

6. Untergruppen

Eine nichtleere Teilmenge W von G ist Untergruppe der Gruppe G, wenn für alle a, b ∈ W gilt: a⋅b – 1 ∈ W. Die Ordnung jeder Untergruppe teilt die Ordnung der Gruppe – vorliegend also ϕ (n). Die kleinste Untergruppe von *nZ ist das Einselement {1} (a = 1, b = 1, b – 1 = 1

→ a⋅b – 1 = 1); die größte Untergruppe ist *nZ selbst (Die beiden trivialen Untergruppen).

Das Erzeugnis < a > einer jeden primen Restklasse aus *

nZ ist eine zyklische Untergruppe

der Ordnung ord a.

a) *nZ ist eine zyklische Gruppe ( n ∈ { 1, 2, 4, p j, 2p j; p > 2 })

Ist *

nZ zyklisch, sind alle Untergruppen von *nZ zyklisch und es gibt zu jedem

Teiler d von ϕϕϕϕ (n) genau eine Untergruppe; die Ordnung der betreffenden Untergruppe ist ϕϕϕϕ (n) / d.

Beispiel: n = p = 13 ϕ (13) = 12 Teiler d: 1, 2, 3, 4, 6, 12 a < a > ord a d

1 1 1 12 2 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1 12 1

3 3, 9, 1 3 4 4 4, 3, 12, 9, 10, 1 6 2 5 5, 12, 8, 1 4 3 6 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1 12 1 = {< 2 >} 7 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1 12 1 = {< 2 >} 8 8, 12, 5, 1 4 3 = {< 5 >} 9 9, 3, 1 3 4 = {< 3 >}

10 10, 9, 12, 3, 4, 1 6 2 = {< 4 >} 11 11, 4, 5, 3, 7, 12, 2, 9, 8, 10, 6, 1 12 1 = {< 2 >} 12 12, 1 2 6

16

Wie man sieht, erzeugen alle Elemente gleicher Ordnung die gleiche Untergruppe, so dass Z13

* insgesamt 6 Untergruppen besitzt entsprechend der Teileranzahl der Gruppenordnung. Kennt man eine Primitivwurzel, lassen die Elemente der einzelnen Untergruppen sich mittels des Elementordnungssatzes (s.o.) explizit angeben: Sei ϕ (n) = d⋅k und a eine Primitivwurzel zum Modul n, (d.h. jedes Element von *

nZ besitzt

eine Darstellung der Form a i mit 1 ≤ i ≤ ϕ (n)). Dann gilt: a d

ist Erzeuger der einzigen Untergruppe <<<< a d >>>> = { a d, a 2⋅⋅⋅⋅d,..., a k⋅⋅⋅⋅d } der Ordnung k.

(Bei der konkreten Berechnung der Untergruppen-Elemente können – wegen c x ≡ c x mod ϕ (n) mod n – die Exponenten von a modulo ϕ (n) reduziert werden.) Im o.a. Beispiel (p = 13) ist 2 eine Primitivwurzel. Es sei d = 4; somit k = 3. Die drei primen Restklassen der Untergruppe sind also 2 4, 2 8, 2 12. Im Vertretersystem besteht die Untergruppe aus 2 4 mod 13 = 3; (2 4)2 mod 13 = 3 2 = 9 und 2 ϕ (n) mod 13 = 1 (Vergl. vorstehende Tabelle unter Zeile a = 3) Fazit: Kennt man von einer zyklischen primen Restklassengruppe die Primfaktorzerlegung von ϕ (n) sowie eine Primitivwurzel lässt sich die Gruppe bis hin zu den Elementen der einzelnen Untergruppen vollständig beschreiben und Die Anzahl der Untergruppen ist gleich der Teileranzahl von ϕϕϕϕ (n). b) *

nZ ist nicht zyklisch

(Da hinsichtlich der Untergruppen nicht-zyklischer abelscher Gruppen in Allgemeinen nur wenig Material zu finden ist, wird dieser Punkt im Folgenden ausführlicher behandelt.) Zunächst noch einige weitere allgemeine Aussagen über Untergruppen: Das Produkt (manchmal auch als Komplexprodukt bezeichnet) zweier Untergruppen H und K von G ist definiert als: H ⋅⋅⋅⋅K = { h ⋅⋅⋅⋅k : h ∈∈∈∈ H, k ∈∈∈∈ K } Sind H und K Normalteiler in G, ist auch H⋅K ein Normalteiler (und somit eine Untergruppe von G). In abelschen Gruppen (und somit in *

nZ ) sind alle Untergruppen Normalteiler und

abelsch. Jede (Unter-)Gruppe besitzt ein Erzeugenden-System; d.h. es gilt G = < a1>⋅< a2>.....< ak> mit ai ∈ G. Da die < ai > definitionsgemäß zyklische Untergruppen sind, ist jede (Unter-)Gruppe als Produkt zyklischer Untergruppen darstellbar. In abelschen Gruppen existieren zu jedem Teiler der Gruppenordnung Untergruppen. Gilt p k teilt |G|, so ist die Anzahl der Untergruppen der Ordnung p k konkruent zu 1 mod p. Ist k maximal, gibt es in abelschen Gruppen genau eine Untergruppe der Ordnung p k . Die Schnittmenge eines Systems von Untergruppen ist wieder eine Untergruppe. Insbesondere ist für zwei Untergruppen A, B mit teilerfremden Ordnungen A∩ B = {1}. (Unter-)Gruppen von Primzahlordnung besitzen (mangels Teiler) nur die beiden trivialen Untergruppen; sie sind daher in jedem Fall zyklisch. (Unter-)Gruppen (abelsch), deren Ordnung quadratfrei ist, sind zyklisch und besitzen nur zyklische Untergruppen.

17

b1) Anzahl zyklischer Untergruppen, wenn *nZ nicht zyklisch ist

Dazu sei ein Beispiel vorangestellt: n = 35 = 5⋅7 ϕ (n) = 24 ε (n) = 12 a <<<< a >>>> ord a

1 1 1 2 2, 4, 8, 16, 32, 29, 23, 11, 22, 9, 18, 1 12 I 3 3, 9, 27, 11, 33, 29, 17, 16, 13, 4, 12, 1 12 II 4 4, 16, 29, 11, 9, 1 6 a 6 6, 1 2 8 8, 29, 22, 1 4 9 9, 11, 29, 16, 4, 1 6 a

11 11, 16, 1 3 12 12, 4, 13, 16, 17, 29, 33, 11, 27, 9, 3, 1 12 II 13 13, 29, 27, 1 4 16 16, 11, 1 3 17 17, 9, 13, 11, 12, 29, 3, 16, 27, 4, 33, 1 12 II 18 18, 9, 22, 11, 23, 29, 32, 16, 8, 4, 2, 1 12 I 19 19, 11, 34, 16, 24, 1 6 b 22 22, 29, 8, 1 4 23 23, 4, 22, 16, 18, 29, 2, 11, 8, 9, 32, 1 12 I 24 24, 16, 34, 11, 19, 1 6 b 26 26, 11, 6, 16, 31, 1 6 c 27 27, 29, 13, 1 4 29 29, 1 2 31 31, 16, 6, 11, 26, 1 6 c 32 32, 9, 8, 11, 2, 29, 18, 16, 22, 4, 23, 1 12 I 33 33, 4, 27, 16, 3, 29, 12, 11, 13, 9, 17, 1 12 II 34 34, 1 2 Aus der Tabelle entnimmt man, dass es z.B. 2 zyklische Untergruppen der Ordnung 12 gibt (in der letzten Spalte mit I bzw. II gekennzeichnet) sowie 3 der Ordnung 6 (a, b, c). Die allen Untergruppen der Ordnung 12 gemeinsamen primen Restklassen – also deren Schnittmenge – sind blau markiert; sie bilden eine Untergruppe der Ordnung 6 (siehe a). Die regelmäßige Anordnung der ‚blauen’ Elemente ist auffallend – und typisch. Für die Anzahl zyklischer Untergruppen der Ordnung m in *

nZ (mit )n(zyA (m) bezeichnet),

erhält man folgenden Zusammenhang: )n(zyA (m) = )n(

mA / ϕ (m).

Darin ist )n(mA gemäß der oben ausführlich behandelten ’Anzahlfunktion der

Elementordnung’ die Anzahl der Elemente in *nZ , welche von der Ordnung m sind. ( )n(

mA ≠ 0

für m | ε (n)). Ist *

nZ zyklisch, ist )n(mA = ϕ (m), d.h. )n(

zyA (m) = 1 wie oben dargelegt.

(Ein Beweis für die vorstehende Anzahlformel wurde in der eingesehenen Literatur nicht gefunden.)

18

b2) Nicht-zyklische Untergruppen, wenn *nZ nicht zyklisch ist

Gemäß den o.a. grundsätzlichen Aussagen über Untergruppen kann es echte nicht-zyklische Untergruppen in *

nZ nur geben, wenn ϕ (n) durch 4 teilbar ist und wenn der größte (echte)

Teiler von ϕ (n) – und somit die Ordnung der Untergruppe – größer oder gleich 4 ist. Folglich muss – wegen ϕ (n) ≥ 8 – n ≥ 15 sein. In der Tat findet sich in Z15

* (genau) eine nicht-zyklische Untergruppe: {1, 4, 11, 14 }. Sie ist das Produkt von zwei der drei zyklischen Untergruppen der Ordnung 2; z.B. {1, 4} und {1, 11}. Ausrechnen des Produkt ergibt: (1⋅1) mod 15 = 1; (1⋅11) mod 15 = 11; (4⋅1) mod 15 = 4; (4⋅11) mod 15 = 14. Ebenso stellt man fest, dass alle 4 Elemente selbst-invers sind und somit „automatisch“ in der Gruppe liegen. Die (nicht-trivialen) Produkte a⋅b– 1 sind (4⋅11) mod 15 = 14; (4⋅14) mod 15 = 11 und (11⋅14) mod 15 = 4. Sie liegen ersichtlich in der Gruppe, so dass die Anforderungen der Untergruppeneigenschaft erfüllt sind. Will man im konkreten Fall die nicht-zyklischen Untergruppen explizit angeben, wird das im Allgemeinen nur mit Rechnerhilfe möglich sein.

Bei der „brute force“- Methode probiert man für alle

−−

1w

1n Möglichkeiten w – 1 Elemente

aus n – 1 Elementen auszuwählen durch, ob die Anforderungen an eine Gruppe (das Produkt von 2 beliebigen der w Elemente sowie das Inverse eines jeden Elementes ist gleich einem der w Elemente) erfüllt sind. (w ist dabei die Ordnung der gesuchten Untergruppe, die „– 1“ berücksichtigt, dass das Einselement immer zur Gruppe gehört und daher nicht zur Auswahl steht.) Das Verfahren liefert mit Sicherheit alle Untergruppen – einschließlich der zyklischen und ist brauchbar für ’w aus n’ < 10 8. Deutlich leistungsfähiger ist das Verfahren, sich zunächst für alle Teiler von w die zyklischen Untergruppen zu verschaffen und dann aus diesen alle Produkte zu bilden, bei denen das Produkt der Ordnungen der „Faktoren“ gerade w ergibt. Wenn es auf die Anzahl ankommt, ist Sorge zu tragen, dass gleiche Untergruppen nicht mehrfach gezählt werden. In der umseitigen Tabelle sind die Anzahlen aller Untergruppen getrennt nach zyklisch und nicht-zyklisch für alle nicht-zyklischen primen Restklassengruppen mit n ≤ 100 aufgelistet.

19

Tabelle 1 Anzahlen aller Untergruppen von nicht-zyklischen primen Restklassengruppen *

nZ mit

n ≤≤≤≤ 100 Die nachstehende Tabelle ist nach aufsteigenden Werten von ϕ (n) geordnet, da in den meisten Fällen (siehe zweite Spalte) mehrere n die hinsichtlich Anzahl und Ordnung gleiche Untergruppenstruktur aufweisen. Erläuterung: Die roten Ziffern bezeichnen die Ordnung der betr. Untergruppe. Die erste Ziffer nach dem Doppelpunkt gibt die Anzahl der zyklischen Untergruppen an, die zweite Ziffer die Anzahl der nicht-zyklischen (außer bei Primzahlordnung, da dann nur zyklische Untergruppen möglich sind). Unter ’Summe UG’ sind die beiden trivialen UG mitgezählt. ϕϕϕϕ (n) n Ordnung und Anzahl der (echten) Untergruppen Summe UG 8 15, 16

20, 30 2: 3, 4: 2 + 1 6 + 2 = 8 24 2: 7, 4: 0 + 7 8 + 8 = 16

12 21, 28 36, 42 2: 3, 3: 1, 4: 0 + 1, 6: 3 + 0 8 + 2 = 10 16 32 2: 3, 4: 2 + 1, 8: 2 + 1 8 + 3 = 11 40, 48

60 2: 7, 4: 4 + 7, 8: 0 + 7 12 + 15 = 27 20 33, 44

66 2: 3, 4: 0 + 1, 5: 1, 10: 3 + 0 8 + 2 = 10 24 35, 39

45, 52 70, 78 90 2: 3, 3: 1, 4: 2 + 1, 6: 3 + 0, 8: 0 + 1, 12: 2 + 1 12 + 4 = 16 56, 72 84 2: 7, 3: 1, 4: 0 + 7, 6: 7 + 0, 8: 0 + 1, 12: 0 + 7 16 + 16 = 32

32 51, 64 68 2: 3, 4: 2 + 1, 8: 2 + 1, 16: 2 + 1 10 + 4 = 14 80 2: 7, 4:12 + 7, 8: 0 + 19, 16: 0 + 7 20 + 34 = 54 96 2: 7, 4: 4 + 7, 8: 4 + 7, 16: 0 + 7 16 + 22 = 38

36 57, 76 2: 3, 3: 1, 4: 0 + 1, 6: 3 + 0, 9: 1 + 0, 12: 0 + 1, 18: 3 + 0 12 + 3 = 15 63 2: 3, 3: 4, 4: 0 + 1, 6: 12 + 0, 9: 0 + 1, 12: 0 + 4, 18: 0 + 3 20 + 10 = 30

40 55, 75 100 2: 3, 4: 2 + 1, 5: 1, 8: 0 + 1, 10: 3 + 0, 20: 2 + 1 12 + 4 = 16 88 2: 7, 4: 0 + 7, 5: 1, 8: 0 + 1, 10: 7 + 0, 20: 0 + 7 16 + 16 = 32

44 69, 92 2: 3, 4: 0 + 1, 11: 1, 22: 3 + 0 8 + 2 = 10 48 65 2: 3, 3: 1, 4: 6 + 1, 6: 3 + 0, 8: 0 + 3, 12: 6 + 1, 16: 0 + 1, 24: 0 + 3 56 87 2: 3, 4: 2 + 1, 7: 1, 8: 0 + 1, 14: 3 + 0, 28: 2 + 1 60 77, 93

99 2: 3, 3: 1, 4: 0+1, 5: 1, 6: 3+0, 10: 3+0, 12: 0+1, 15: 1+0, 20: 0+1, 30: 3+0 64 85 2: 3, 4: 6 + 1, 8: 4 + 3, 16: 4 + 3, 32: 0 + 3 72 91 2: 3, 3: 4, 4: 2+1, 6: 12+0, 8: 0+1, 9: 0+1, 12: 8+4, 18: 0+3, 24: 0+4, 36: 0+3 95 2: 3, 3: 1, 4: 2+1, 6: 3+0, 8: 0+1, 9: 1+0, 12: 2+1, 18: 3+0, 24: 0+1, 36: 0+3

20

Die Daten der Tabelle bestätigen folgende Aussagen bezüglich der Anzahl von Untergruppen. Es bedeuten: )n(

UGA (m): Anzahl aller Untergruppen der Ordnung m

)n(zyA (m): Anzahl zyklischer Untergruppen der Ordnung m

)n(nzA (m): Anzahl nicht-zyklischer Untergruppen der Ordnung m

Also: )n(UGA (m) = )n(

zyA (m) + )n(nzA (m)

Analog dem Vorgehen bei den Elementordnungen ist es zweckmäßig zunächst den Fall zu betrachten, dass die Ordnung m Potenz einer Primzahl ist.

• m ist Potenz einer Primzahl: m = p f

– Anzahl zyklischer Untergruppen der Ordnung p f (f > 0)

)n(zyA (p f) =

1p1p

fps

−− ⋅p ΣΣΣΣ mit ΣΣΣΣ = )1s(

1f

0ipi −∑

−

= und 0p

s = 1

Darin ist xps die Anzahl der Faktoren jk

jq in der Zerlegung von n, bei denen ϕ ( jkjq )

durch p x teilbar ist (wobei der Sonderfall p = 2 zu beachten ist).

– Anzahl nicht-zyklischer Untergruppen der Ordnung p f Es sei ϕ (n) = p k ⋅h mit ggT(p k, h) = 1. Für f ≤≤≤≤ k / 2 gilt: ▫ f < 2: )n(

nzA (p f) = 0

▫ f = 2: )n(nzA (p 2) =

2

)p(A )n(zy ⋅

)1p(p2

+⋅ (Deutung: Da für zwei beliebige

(verschiedene) Untergruppen U a, U b mit Ordnung p gilt: U a∩ U b = {1} , ist das Produkt von zwei verschiedenen Untergruppen mit Ordnung p immer eine nicht-zyklische Untergruppe der Ordnung p 2. Von diesen Produkten stellt ein Anteil von p⋅(p+1) / 2 unterschiedliche Untergruppen dar.)

Gemäß der o.a. Formel für )n(zyA (p f) ist )n(

zyA (p) = 1p1p ps

−− .

(Das ist die Lösung der inhomogenen, linearen Rekursion 1. Ordnung zyA (p, s p) = p⋅ zyA (p, s p – 1) + 1 mit zyA (p, 0) = 0.)

▫ f = 3: )n(nzA (p 3) =

−⋅

−

31p

2

)p(A

3

)p(A )n(zy

)n(zy / C p

+ 2

2)n(zy

)n(zy

p

)p(A)1)p(A( ⋅−

C p = p 3⋅⋅⋅⋅ (p 3 + 2⋅⋅⋅⋅p 2 + 2⋅⋅⋅⋅p + 1) / 6 → C 2 = 28; C 3 = 234; C 5 = 3875 usw.

(Der erste Summand der o.a. Formel gibt die Anzahl der Untergruppen an, welche als Produkt von 3 zykl. Untergruppen der Ordnung p darstellbar sind; der zweite Summand diejenigen, die Produkt einer Untergruppe der Ordnung p und einer der Ordnung p 2 sind; weitere Zerlegungen von p 3 gibt es nicht. Nicht jedes Produkt von 3 zykl. Untergruppen der Ordnung p ergibt eine Untergruppe der Ordnung p 3. Diese Fälle erfasst der rechte Term in [....] .)

Zur Berechnung des 2. Summanden: Es ist (s. o.): )n(zyA (p 2) =

1p1p

2ps

−− ⋅ 1spp

−

21

– )n(

UGA (pk – f) = )n(UGA (p f) wobei wie oben ϕ (n) = p k ⋅h mit ggT(p k, h) = 1.

Infolge dieser vorrangigen Symmetriebedingung sind die o.a. Formeln für )n(nzA (p f)

nur für f ≤ k / 2 anzuwenden. Insbesondere ist )n(UGA (pk ) = )n(

UGA (p 0) = 1.

Da die Anzahlen zykl. Untergruppen mit Primzahlpotenzordnung p f für alle f und die der nicht-zyklischen mittels der o.a. Formeln bis f = 3 berechnet werden können, lassen sich mit Hilfe der hier angegebenen Formeln alle )n(

UGA (p x) (x ≤ k)

bestimmen, wenn in ϕ (n) = p k ⋅h k ≤≤≤≤ 7 ist.

Sind die Untergruppen mit Ordnung p f bekannt, können die Werte für zusammengesetztes m leicht bestimmt werden:

• )n(UGA (m) = )n(

UGA (ϕ (n) / m)

Infolge dieser Paarbildung, die Konsequenz der o.a. Symmetriebedingung für die Primzahlpotenzen ist, ist die Anzahl aller Untergruppen von *

nZ stets gerade, außer

wenn ϕ (n) eine Quadratzahl ist und die Anzahl der Untergruppen mit der Ordnung m = )n(ϕ ungerade ist. (siehe ‚grüne’ Zahlen in Tabelle 1.)

• Sei m = v⋅w mit ggT(v, w) = 1. Dann ist )n(

UGA (m) = )n(UGA (v) ⋅ )n(

UGA (w).

Das gilt entsprechend natürlich auch für mehr als zwei teilerfremde Faktoren.

• Aufteilung in zyklisch und nicht-zyklisch

Sei m = v⋅w mit ggT(v, w) = 1. Dann ist )n(zyA (m) = )n(

zyA (v) ⋅ )n(zyA (w).

Alternativ hat man (siehe Ziffer 4.): )n(zyA (m) = A m / (ϕ (m).

(Zyklische Untergruppen gibt es genau dann, wenn m | ε (n). Ist m quadratfrei existieren – wie oben erwähnt – für dieses m ausschließlich zyklische Untergruppen.)

Fazit: Verfügt man über die Primfaktorzerlegung von n, kann man für jeden Teiler von ϕϕϕϕ (n) die Anzahl der zyklischen und nicht-zyklischen Untergruppen angeben. In Anlage 2 sind – in Fortsetzung des Beispiels aus Ziffer 4. – die Anzahlen der Untergruppen für das gesamte Teilersystem angegeben, um einen Eindruck über die Vielzahl von Untergruppen zu vermitteln. (Die Überprüfung der Anzahlen mittels expliziter Berechnung der Untergruppen führt für dieses Beispiel bereits an die Grenzen des Computers (Zeitbedarf)). (Beweise?)

22

7. Die Untergruppe „Quadratische Reste“ Ein a ∈ *

nZ wird als quadratischer Rest (QR) bezeichnet, wenn es ein x ∈ *nZ gibt, so dass

x 2 ≡ a mod n – wenn also diese quadratische Kongruenz für ein vorgegebenes a lösbar ist. Wie für primes oder zusammengesetztes n festgestellt wird, ob a ein QR ist, und wie man eine Lösung der quadratischen Kongruenz bestimmt, ist z.B. im Beitrag „Über quadratische Reste und Kongruenzen“ auf der Netz-Seite des Verfassers ausführlich beschrieben. Hier soll nur auf einige Aspekte im Zusammenhang mit der primen Restklassengruppe eingegangen werden. Üblicherweise werden die QR bzw. QNR durch Angabe des Legendre-Symbols, das für einen QR den Wert 1 und für einen QNR den Wert – 1 ausgibt, gekennzeichnet. Nachfolgend wird ein QR durch ein „+“, ein QNR durch „–“ markiert. • Verteilung der QR in *

nZ

Zunächst einige Beispiele, die die Verteilung der QR innerhalb der Gruppe und Zusammenhänge mit der Ordnung veranschaulichen. n = p = 17 (n ≡ 1 mod 4) a : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 QR: + + – + – – – + + – – – + – + + a – 1: 1 9 6 13 7 3 5 15 2 12 14 10 4 11 8 16 ord a : 1 8 16 4 16 16 16 8 8 16 16 16 4 16 8 2 n = p = 19 (n ≡ 3 mod 4) a : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 QR: + – – + + + + – + – + – – – – + + – a – 1: 1 10 13 5 4 16 11 12 17 2 7 8 3 15 14 6 9 18 ord a : 1 18 18 9 9 9 3 6 9 18 3 6 18 18 18 9 9 2 n = 3⋅⋅⋅⋅5 = 15 (n ≡ 3 mod 4; Produkt der Reste 3 und 1 (mod 4)) a : 1 2 4 7 8 11 13 14

mod 3 : + – + + – – + – a ist genau dann QR, wenn a zu jedem Primteiler mod 5 : + – + – – + – + von n QR ist.

QR : + – + – – – – – Jacobi-S.: + + + – + – – – Ist das Jacobi-Symbol gleich – 1, → a ist QNR ord a : 1 4 2 4 4 2 4 2 n = 3⋅⋅⋅⋅7 = 21 (n ≡ 1 mod 4; Produkt der Reste 3 und 3 (mod 4)) a : 1 2 4 5 8 10 11 13 16 17 19 20 mod 3: + – + – – + – + + – + – mod 7: + + + – + – + – + – – – QR : + – + – – – – – + – – – Quadratzahlen in *

nZ sind immer QR

Jacobi-S.: + – + + – – – – + + – + ord a : 1 6 3 6 2 6 6 2 3 6 6 2

23

Die Beispiele bestätigen: p ≡ 1 mod 4 → ( )pa = ( )p

ap − ; p ≡ 3 mod 4 → ( )pa = – ( )p

ap − ;

( )pa = ( )p

a 1− ; falls *

nZ zyklisch: ord a = ord b ↔ ( )pa = ( )p

b

Sei n quadratfrei und ord a ungerade → a ist QR. • Anordnung der QR in den Untergruppen Beispiel: n = 13 Die von den einzelnen Elementen erzeugten Untergruppen sind: a < a > ord a 1 1 1 2 2 4 8 3 6 12 11 9 5 10 7 1 12 3 3 9 1 3 4 4 3 12 9 10 1 6 5 5 12 8 1 4 6 6 10 8 9 2 12 7 3 5 4 11 1 12 7 7 10 5 9 11 12 6 3 8 4 2 1 12 8 8 12 5 1 4 9 9 3 1 3 10 10 9 12 3 4 1 6 11 11 4 5 3 7 12 2 9 8 10 6 1 12 12 12 1 2 Die rot geschriebenen Elemente sind QR. Die Verteilung der QR folgt aus den Rechenregeln für das Legendre-Symbol: (+1)(+1) = 1; (–1)(+1) = – 1 und (– 1)(–1) = 1. Folglich sind alle Elemente der zyklischen Untergruppe < a > QR, falls a ein QR ist. Ist a ein QNR sind die Elemente mit geraden Exponenten QR. Für alle zyklischen primen Restklassengruppen gilt: Ist *

nZ zyklisch, gibt es ϕ (n ) / 2 QR und es existiert genau eine zyklische Untergruppe der

Ordnung ϕ (n ) / 2 , die alle QR enthält. Sucht man einen erzeugenden QR einer solchen Untergruppe, ist eine Quadratzahl häufig eine gute Wahl. Im weiteren wird jede Untergruppe, deren Elemente ausschließlich QR sind, mit „QR-Unter-gruppe“ bezeichnet. • Anzahl der QR in *

nZ

Die Anzahl AQR(n) der QR in einer primen Restklassengruppe ist für n = k1k1

e p...p2αα ⋅⋅⋅

(n > 2) gegeben durch *)

AQR(n) = f2

)n(ϕ mit f =

ϕ (n ) wird also durch die Anzahl der selbst-inversen Elemente in *

nZ (siehe diesbezügliche

Formel in Ziffer 4.) dividiert. *) siehe z.B. die im Netz einsehbare Diplomarbeit „ Ein neues Identifikations- und Signaturverfahren über imaginär-quadratischen Klassengruppen“ von A. Meyer, 1997

k für e < 2 k + 1 für e = 2 k + 2 für e > 2

24

• QR-Untergruppen, wenn *nZ nicht zyklisch ist

(Die Aussagen zu diesem Unterpunkt beruhen auf experimentellen Befunden.)

– Es gibt stets eine QR-Untergruppe der Ordnung ε (n) / 2, und das ist (natürlich) immer die maximale zyklische QR-Untergruppe.

– Ist AQR(n) = ε (n) / 2 = ϕ (n) / 2 f enthält die max. zyklische QR-Untergruppe

alle QR. Das ist häufig auch dann der Fall, wenn *nZ nicht zyklisch ist; z.B.

bei allen *nZ mit n < 63.

n = 63 = 3 2 ⋅7 → ϕ (63) = (2⋅3)⋅(2⋅3) = 36 → ε (63) = 6 → ε (63) / 2 = 3

→ AQR(63) = ϕ (63) / 2 2 = 9

Die max. zyklische QR-Untergruppe enthält also 3 QR, während es insgesamt 9 QR gibt. Der Fall AQR(n) > ε (n) / 2 tritt u.a. ersichtlich notwendigerweise dann auf, wenn die „Faktordarstellung“ von ϕ (n) in zwei oder mehr Faktoren gleiche ungerade Primzahlen aufweist (im Beispiel die 3).

– Zu jedem Teiler von ε (n) / 2 existieren zyklische QR-Untergruppen; ist der Teiler – also die Untergruppenordnung – ungerade, sind sogar alle zykl. Untergruppen dieser Ordnung QR-Untergruppen.

– Die Ordnung der max. zyklischen QR-Untergruppe teilt die Anzahl der QR;

In Zeichen: ε (n) / 2 | ϕ (n) / 2 f.

– Ist AQR(n) = ϕ (n) / 2 f > ε (n) / 2 gibt es (mindestens) eine nicht-zyklische QR-Untergruppe, die alle QR enthält, also die Ordnung AQR(n) hat.

Fortsetzung des obigen Beispiels: Die 9 QR in *

63Z sind: 1, 4, 16, 22, 25, 37, 43, 46, 58

Zwei der 4 QR-Untergruppen der Ordnung 3 sind: U1 = {1, 4, 16} und U2 = {1, 22, 43} Das Produkt dieser beiden Untergruppen ergibt eine QR-Untergruppe (U3) der Ordnung 9, die somit alle QR enthält: (1⋅1) mod 63 = 1 ; (1⋅22) mod 63 = 22 ; (1⋅43) mod 63 = 43 ; (4⋅1) mod 63 = 4 ; (4⋅22) mod 63 = 25 ; (4⋅43) mod 63 = 46 ; (16⋅1) mod 63 = 16 ; (16⋅22) mod 63 = 37 ; (16⋅43) mod 63 = 58 Es ist U3 = < 4 > ⋅ < 22 >.

25

8. Zu *nZ isomorphe Gruppen

Zwei Gruppen (A,∗) und (B,o) sind isomorph zueinander (in Zeichen: A ≅ B), wenn es eine bijektive Abbildung f: A → B gibt, so dass f (a ∗ a′) = f (a) o f (a′) für alle a, a′ ∈ A. Die bijektive Abbildung bedingt, dass auch die Umkehrabbildung f – 1 existiert und dass isomorphe Gruppen die gleiche Ordnung haben. Das neutrale Element von A wird auf das neutrale Element von B abgebildet, und jedes Paar inverser Elemente von A wird einem Paar inverser Elemente von B zugeordnet. Das alles hat zur Folge, dass isomorphe Gruppen bis auf die Bezeichnungen identisch sind (gleiche Verknüpfungstafeln). Insbesondere gibt es aus dieser Sicht nur eine zyklische Gruppe vorgegebener Ordnung – aber mit vielen unterschiedlichen Bezeichnungen und Verknüpfungen. Als „Prototyp“ einer zykl. Gruppe der Ordnung n wird in der Regel (Zn , +) gewählt. Im Zusammenhang mit Isomorphien ist das „direkte Produkt“ von Gruppen wichtig. Das direkte Produkt (A x B,⋅) zweier Gruppen (A,∗) und (B,o) ist eine Gruppe mit den Tupeln (a, b) a ∈ A, b ∈ B als Elementen und der (komponentenweisen) Verknüpfung (a, b)⋅(a′, b′) = (a∗a′, bob′). Ein wichtiger Sonderfall liegt vor, wenn A und B Untergruppen einer Gruppe G sind: Es sei G = A ⋅ B, A und B Normalteiler von G sowie A∩ B = {1} (1: neutrales Element). Dann gilt: G ≅ A x B . Allgemeiner: Sie G eine abelsche Gruppe mit |G| = 1

1pα ⋅....⋅ sspα und G i Untergruppen mit |G i| = i

ipα . Dann

ist jedes Element g ∈ G ist als g = g1⋅...⋅g s mit g i ∈ G i darstellbar und es ist G ≅ G 1 x G 2 x ..... x G s. In Bezug auf *

nZ hat man folgendes:

a) Isomorphien zum direkten Produkt primer Restklassengruppen

n = 11pα ⋅....⋅ s

spα Dann ist: *nZ ≅ *

p 11

Z αααα x .....x *

p ss

Z αααα

Insbesondere: *wvZ ⋅⋅⋅⋅ ≅ *

vZ x *wZ falls ggT(v, w) = 1 (n ungerade: *n2Z ≅ *

nZ )

In dem obigen direkten Produkt sind alle Faktoren zyklische Gruppen, mit der Ausnahme p 1 = 2 und α 1 > 2: *

2 1Z αααα = < – 1 > ⋅ < 5 > wobei – 1 und 5

Untergruppen von *

2 1Z αααα der Ordnung 2 bzw. 2α1 – 2 erzeugen.

b) Isomorphien zum direkten Produkt additiver Gruppen n = 1

1pα ⋅....⋅ sspα

*nZ ≅

)p( 11

Z ααααϕϕϕϕx .....x

)p( ss

Z ααααϕϕϕϕ falls n ≠ 0 mod 8

*nZ ≅ 2Z x 212

Z −−−−αααα x )p( 2

2Z ααααϕϕϕϕ

x .....x )p( s

sZ ααααϕϕϕϕ

falls n ≡ 0 mod 8, d.h. α1 ≥ 3

Insbesondere: *pZ ≅ Z p – 1. Analog zu a) ist: Zv⋅⋅⋅⋅w ≅ Z v x Z w falls ggT(v, w) = 1

(Im Unterschied zu Ziffer a) handelt es sich hier um eine teilerfremde Zerlegung der Ordnung der additiven Gruppe Z n.) Bezüglich der Zerlegung mit Elementarteilern siehe Ziffer 9.

26

Beispiele: – n = 60 = 2 2 ⋅3 ⋅5 ϕ (60) = 2 ⋅2 ⋅4 = 16 Gemäß a) gilt: *

60Z ≅ *4Z x *

3Z x *5Z

*4Z = {1, 3} *

3Z = {1, 2} *5Z = {1, 2, 3, 4} Das direkte Produkt dieser drei

Gruppen besteht aus den 16 Tripeln / Elementen: (1, 1, 1) → 1 (1, 2, 1) → 41 (3, 1, 1) → 31 (3, 2, 1) → 11 (1, 1, 2) → 37 (1, 2, 2) → 17 (3, 1, 2) → 7 (3, 2, 2) → 47 (1, 1, 3) → 13 (1, 2, 3) → 53 (3, 1, 3) → 43 (3, 2, 3) → 23 (1, 1, 4) → 49 (1, 2, 4) → 29 (3, 1, 4) → 19 (3, 2, 4) → 59 Die Zahlen hinter den Pfeilen stellen insgesamt die primen Restklassen modulo 60 dar. Diese erhält man aus den jeweils davor stehenden Tripeln (a, b, c) durch Lösen des diophantischen Gleichungssystems x ≡ a mod 4; x ≡ b mod 3; x ≡ c mod 5 Der Isomorphismus wird also durch den Chinesischen Restsatz vermittelt.

Alternative: Bestimmung je einer PWi der *

p ii

Z αααα (Im Beispiel: 3, 2, 2) und diese

mittels Chin. Restsatz auf den Modul n ‚liften’. (oben rot markiert.) Alle primen Restklassen modulo n erhält man dann durch Berechnen aller Produkte der PWi-Potenzen (modulo n). Im Beispiel: (31j ⋅ 41k ⋅ 37h) mod 60 mit j, k = 1, 2; h = 1,..,4.

Mehr dazu unter Ziffer 9. – Zu b) *

pZ ≅ Z p – 1 für p = 5 Die Verknüpfungstafeln sind dann

*

5Z Z 4 *5Z

⋅⋅⋅⋅ 1 2 3 4 + 0 1 2 3 ⋅⋅⋅⋅ 1 3 4 2 1 1 2 3 4 0 0 1 2 3 1 1 3 4 2 2 2 4 1 3 1 1 2 3 0 3 3 4 2 1 3 3 1 4 2 2 2 3 0 1 4 4 2 1 3 4 4 3 2 1 3 3 0 1 2 2 2 1 3 4 In der letzten Tafel für *

5Z sind die Zeilen und Spalten so vertauscht, dass der

Isomorphismus sofort abgelesen werden kann: 1 → 0; 2 → 3; 3 → 1; 4 → 2. Eine Möglichkeit, die Abbildung (den Isomorphismus) konkret anzugeben, geht von der Berechnung der Ordnung der Gruppenelemente aus: a: ⋅⋅⋅⋅ 1 2 3 4 + 0 1 2 3 ord a: 1 4 4 2 1 4 2 4 Ein weiterer Isomorphismus ist demnach: 1 → 0; 2 → 1; 3 → 3; 4 → 2. Obwohl im Fall einer Primzahl die „identische“ Gruppe (Z n, +) sofort angegeben werden kann und zu dieser auch ein erzeugendes Element bekannt ist, hilft das nicht bei der Suche nach einer Primitivwurzel; dazu muss der Isomorphismus explizit vorliegen, wozu es auch kein allgemeines Verfahren gibt.

– In der Zahlentheorie wichtig: *

nZ ≅ χ(n) (Gruppe der Dirichlet-Charaktere mod n)

27

– Das folgende Beispiel soll zeigen, wie isomorphe Darstellungen einer abelschen

Gruppe dazu benutzt werden können, um festzustellen, welche Produkte von Untergruppen (Normalteiler) auf unterschiedliche bzw. gleiche Gruppen führen.

Gegeben sei *nZ und 72 | ε (n). Welche Untergruppenprodukte muss man auswerten,

um alle Untergruppen der Ordnung 72 zu erhalten? Die 16 Darstellungen von 72 als Produkt seiner Teiler sind:

(1) 72 x 1 (7) 2 x 2 x 18 (13) 2 x 2 x 2 x 9 (2) 36 x 2 (8) 3 x 3 x 8 (14) 2 x 3 x 3 x 4 (3) 24 x 3 (9) 2 x 4 x 9 (15) 2 x 2 x 3 x 6 (4) 18 x 4 (10) 2 x 6 x 6 (16) 2 x 2 x 2 x 3 x 3 (5) 12 x 6 (11) 2 x 3 x 12 (6) 9 x 8 (12) 3 x 4 x 6

Durch fortgesetzte Anwendung von Zv⋅⋅⋅⋅w ≅ Z v x Z w falls ggT(v, w) = 1 erhält man folgende Isomorphien (in Kurzschreibweise): (1) ≅ (6); (2) ≅ (9); (3) ≅ (8); (4) ≅ (9); → (2) ≅ (4) ≅ (9); (5) ≅ (11) ≅ (12) ≅ (14); (7) ≅ (13); (10) ≅ (15) ≅ (16) Anstatt der 16 möglichen reicht es somit, die 6 rot geschriebenen Produkte von Untergruppen aus *

nZ auszuwerten, da die übrigen zu einer dieser 6 isomorph sind

und daher die gleichen Untergruppen der Ordnung 72 bilden. Diese 6 sind in der Tat auch erforderlich, um alle Untergruppen zu finden.

– Ob man alle Isomorphien bzw. Faktoren berücksichtigt hat, lässt sich mit folgender Formel, welche die Anzahl AIso(m) der ‚Isomorphieklassen’– also der nichtisomorphen Zerlegungen der Gruppenordnung – angibt, feststellen:

m = 11pα ⋅....⋅ s

spα → AIso(m) = ∏=

αs

1ii )(f wobei f (α i) die Anzahl der Möglichkeiten ist,

die α i in Partitionen zu zerlegen. Im Beispiel: 72 = 2 3 ⋅3 2 α 1 = 3 → (3) = (2 + 1) = (1 + 1+ 1) also 3 Partitionen; f (α 1) = 3 α 2 = 2 → (2) = (1 + 1) 2 Partitionen; f (α 2) = 2 → AIso (72) = 2⋅3 = 6 wie oben angegeben.

9. Struktur von *

nZ ; Elementarteiler; Minimale Erzeugendensysteme

Als Erzeugendensystem von *nZ bezeichnet man eine Menge von Elementen aus *

nZ so dass

gilt Zn* = < a 1> ⋅ .....⋅ < a h>, d. h. jedes Element von *nZ ist als Produkt von Elementen aus h

zyklischen Untergruppen darstellbar. Es stellt sich also die Frage, wie viele Erzeuger man in konkreten Fall mindestens benötigt.

Wie oben erwähnt, ist *

nZ für n = 2 e mit e > 2 nicht zyklisch. Es gilt 2ee 22*

2ZZZ −−−−××××≅≅≅≅

28

und alle 2 e – 1 prime Restklassen lassen sich eindeutig in der Form (- 1)i ⋅5 j darstellen, wobei i die Werte 1 und 2, j die Werte 1, .., 2 e – 2 durchläuft. (Begründung: Für n = 2 e (e > 2) gilt in

*nZ : ord 5 = 2 e – 2 und ord (n–1) = 2 (wie üblich).)

Das ist der einzige (nicht-triviale) Fall, in dem die Erzeuger von vornherein explizit angegeben werden können; aber eine Aussage über die erforderliche Mindestanzahl der Erzeuger im allgemeinen Fall ist möglich:

Sei n = k1k1

e p...p2αα ⋅⋅⋅ (n > 2) Die minimale Erzeugendenanzahl g = g (e, k) ist dann

Der Hauptsatz über endliche abelsche Gruppen, nach welchen jede endliche abelsche Gruppe zu einem Produkt zyklischer Gruppen isomorph ist, besagt außerdem folgendes über die Anzahl und die Ordnungen der beteiligten zyklischen Gruppen: Es existiert eine eindeutig bestimmte Darstellung mit g Faktoren ( g = min. Erz.-Anzahl), wobei für die Ordnungen m i der Faktoren gilt: |G| = Π m i; m i + 1| m i mit m 1 = ε (n) und m g ≥ 2. Die zyklischen Gruppen werden meist – so auch im Folgenden – allgemein mit Cy bezeichnet, wobei der Index die Ordnung von C angibt; das Produkt der Indices (= Elementarteiler) muss natürlich gleich ϕ (n) sein. Der Algorithmus, der – ausgehend von einem beliebigen Erzeugendensystem – diese Darstellung berechnet, soll hier nicht beschrieben werden; für *

nZ erhält man die m i (sog.

Elementarteiler) leicht, wenn die Primfaktorzerlegung von n bekannt ist (siehe folgendes Beispiel). Wegen der Eigenschaften von ϕ (n) sind die Elementarteiler im Falle der primen Restklassengruppe alle gerade. n = 2 5⋅ 3 3 ⋅19⋅ 43 → k = 3, e > 2 → g = 5 ϕ (n) = (2)⋅(2 3)⋅(2⋅3 2)⋅(2⋅3 2)⋅(2⋅3⋅7) = 217.728 Nun werden die Potenzen der Primteiler von ϕ (n) – je Primteiler geordnet nach fallenden Potenzen – aus Gründen der Übersichtlichkeit in eine Tabelle eingetragen: p m 1 m 2 m 3 m 4 m 5 Durch Ausmultiplizieren der Spalten erhält man 2 3 1 1 1 1 m 1 = 2 3⋅3 2⋅7 = 504 = ε (n) 3 2 2 1 m 2 = 2⋅3 2 = 18 7 1 m 3 = 2⋅3 = 6

m 4 = 2 = 2 Probe: m1 ⋅.....⋅m5 = ϕ (n) m 5 = 2 = 2

→ *nZ ≅ C 504 x C 18 x C 6 x C 2 x C 2 Dies ist die „Struktur“ von *

nZ .

Die allgemeinen zyklischen Gruppen C werden nun mit zyklischen Untergruppen von *nZ

identifiziert, was nach den Hauptsatz ja immer möglich ist. Als Produkt zykl. Untergruppen findet man im Beispiel etwa: *

nZ = < 5 > ⋅ < 257 > ⋅ < 1585 > ⋅ < 37583 > ⋅ < 58481 > wobei

die Ordnung der Erzeugenden (in fallender Folge) den Elementarteilern entspricht. Ein weiteres Beispiel: *

nZ sei das Produkt zweier zyklischer Untergruppen U1 und U2 mit |U1|

= 30, |U2| = 12. Die Zerlegung der Ordnungen ist 2⋅3⋅5 und 2 2 ⋅3. Das geht ohne Tabelle; die Elementarteiler sind m 1 = 2 2 ⋅3⋅5 = 60, m 2 = 2⋅3 = 6.

k für e < 2 g = k + 1 für e = 2 k + 2 für e > 2

29

Nachstehend wird die Bestimmung der Struktur von *nZ sowie eines min.

Erzeugendensystems im Überblick dargestellt und an Beispielen erläutert. 1. Struktur

– Darstellung von n als n = 2 e⋅ 11pα ⋅....⋅ k

kpα mit pi > 2

– ϕ (n) = 2e–1⋅ϕ( 11pα )⋅.....⋅ϕ( k

kpα ) – Bestimmung der min. Erzeugendenanzahl: g = k + h

mit h = 0 für e ∈ {0, 1}; h = 1 für e = 2 und h = 2 für e > 2.

– Berechnung des Exponenten ε (n)

ε (n) = kgV( f, ϕ( 11pα ), ...., ϕ( k

kpα ))

1 für e < 2 Darin ist f = 2 für e = 2

2e – 2 für e > 2

– Elementarteilerkette (Länge: g) bestimmen aus ε (n) ⋅ m2 ⋅...⋅mg = ϕ (n) und mi+1 | mi ; alle Faktoren gerade.

(In komplizierteren Fällen mit Hilfe des Tabellen-Schemas (s. vorige Seite)) → Struktur: *

nZ ≅ Cε (n) ××××.. ×××× Ci ××××..×××× Cmg

2. Bestimmung von Erzeugenden

– Primitivwurzeln (PW) zu allen Primteilern von n aufsuchen (4 < 2e: n – 1 und 5). – Berechnung von g Elementen aus *

nZ , deren Ordnung denen der einzelnen

Elementarteiler entspricht. Diese erhält man folgendermaßen:

Sei n = ∏ αk

1i

ip und sei ai je ein beliebiges Element aus den einzelnen *

p ii

Z αααα mit der

Ordnung oi. Dann erhält man als Lösung xn der k simultanen Kongruenzen x ≡≡≡≡ ai mod i

ipαααα ein Element aus *nZ mit ord x n = kgV(o1,.. ,ok).

– Prüfung, ob die g Elemente der Ordnungen mi Untergruppen von *

nZ erzeugen, die

(mit Ausnahme des Einselementes) disjunkt sind. Falls das nicht der Fall ist, (mindestens) ein neues Element bestimmen und Prüfung wiederholen; sonst:

→ Min. Erz.-System: (aε(n),...., amg)

Zur Vereinfachung der Schreibweise wird in den folgenden Beispielen ein zu lösendes System simultaner Kongruenzen x ≡ a mod u; ....; x ≡ c mod w dargestellt als [au, .., cw] → xn Die Indizes geben also den Modul an. Ebenso bezeichnet PWv eine Primitivwurzel zum (zyklischen) Modul v. (Ein Programm für simultane Kongr. siehe am Schluss.)

30

– n ungerade Beispiel 1 n = 675 = 33⋅52 ; ϕ(33⋅52) = 18 ⋅ 20 = 360; ε(n) = kgV(18, 20) = 180 n besitzt 2 ungerade Primteiler → g = 2

*675Z ≅ C180 ×××× C2 wegen g = 2 und 180⋅2 = ϕ(n) = 360

Bestimmung von Primitivwurzeln zu den Moduln 33 und 52

PW3: 2; wegen 22 ≠ 1 mod 32 und (2 + 3)2 ≠ 1 mod 32 → PW27: 2, 5 (siehe Seite 14) PW5: 2, 3; 24 ≠ 1 mod 52 ; aber (2 + 5)4 = 1 mod 52 → 7 ist keine PW25

34 ≠ 1 mod 52 und (3 + 5)4 ≠ 1 mod 52 → PW25: 2, 3, 8 (Aufgrund der Struktur reicht hier eine PW zu jeder Primteiler-Potenz.) Bestimmung eines Elements der Ordnung εεεε(n) = 180 Die PW27 bzw. PW25 besitzen definitionsgemäß Ordnung 18 in *

33Z bzw. 20 in *

52Z .

Somit: [227, 225] → 2 besitzt in *675Z Ordnung 180. Oder z.B.: [527, 825] → 383

(Zur Schreibweise [.....] siehe vorige Seite, unten) Insgesamt lassen sich mit den o.a. 5 PW ersichtlich 6 verschiedene Elemente der Ordnung 180 in *

675Z bestimmen.

Bestimmung eines Elements der Ordnung 2 Wegen Anzahl(ord a = 2) = 2g – 1 gibt es hier genau 3 solche Elemente. In *

p ii

Z αααα haben bekanntlich die Elemente iipα – 1 Ordnung 2. Somit findet man die 3 Elemente

in *675Z (da ord 1 = 1) aus [125, 2627] → 26; [127, 2425] → 649; [2425, 2627] → 674 (= n – 1).

Prüfung, ob die Schnittmenge der Untergruppen das Einselement ist Bei der von einem Element a erzeugten Untergruppe gerader Ordnung o hat das Element ao/2 wegen (ao/2)2 = 1 immer die Ordnung 2. Wählt man im vorliegenden Beispiel das oben berechnete Element 2 der Ordnung 180, so zeigt sich, dass 290 mod 675 = 649 ist. Also ist (2, 649) kein Erz.-System; wohl aber sind z.B. (2, 26) oder (2, 674) oder (383, 26) Erz.-Systeme für *

675Z .

Beispiel 2 n = 105 = 3⋅5⋅7; ϕ(105) = 2⋅4⋅6; ε(n) = kgV(2, 4, 6) = 12; g = 3 ϕ(n) / ε(n) = 4 Wegen g = 3 ist die 4 in zwei gerade Faktoren aufzuteilen.

→ *105Z ≅ C12 ×××× C2 ×××× C2

Aus den zyklischen Gruppen *3Z , *5Z und *

7Z sind Elemente so auszuwählen, dass das kgV

aus deren Ordnungen 12 bzw. 2 ergibt. PW3: 2 (ord = 2); PW5: 2, 3 (ord = 4); PW7: 3, 5 (ord = 6) Z.B. besitzen [13, 25, 37] → 52 und [13, 35, 37] → 73 und [23, 25, 57] → 17 Ordnung 12. Ordnung 2: Z.B.: [23, 45, 17] → 29 und [13, 45, 17] → 64 und [13, 45, 67] → 71 Prüfung: Bei allen Elementen der Ordnung 12 gilt: a12/2 = 64 mod 105; d.h. von den drei berechneten Elementen kommen nur 29 und 71 infrage. Da zwei Elemente der Ordnung 2 benötigt werden, ist noch das Produkt dieser zwei Elemente zu überprüfen: (29 ⋅ 71) mod 105 = 64 ≠ 52 ≠ 73 ≠ 17 → *

105Z wird z.B. durch (17, 29, 71) erzeugt.

31

Bemerkungen: • Im vorstehenden Beispiel gibt es 16 Elemente der Ordnung 12 und 7 Elemente der

Ordnung 2. Bei allen Elementen a der Ordnung 12 ist a6 = 64 mod 105. Damit hat man

noch 6 ‚brauchbare’ Elemente der Ordnung 2. Es gibt

6

2 = 15 Möglichkeiten 2

Elemente auszuwählen (ohne Berücksichtigung der Reihenfolge). In drei Fällen führt das Produkt von zweien dieser Elemente (,das ja auch Ordnung 2 hat,) auf 64 mod 105. Somit bleiben noch (15 – 3 =) 12 Möglichkeiten. Insgesamt gibt es also 16⋅12 = 192 Tripel, die *

105Z erzeugen.

• Weist die Struktur mehrere zyklische Gruppen gleicher Ordnung auf – wie im vorigen Beispiel C2 –, ist es vorteilhaft, die betr. Kongruenz-Tupel [....] so zu wählen, dass sie sich in möglichst vielen Komponenten unterscheiden. In Beispiel sind das etwa die Paare [23, 45, 17] und [13, 15, 67] oder [13, 45, 67] und [23, 15, 17]. Solche Kongruenzen führen fast immer auf disjunkte Untergruppen.

• Das sicherste Verfahren, ein Tupel zu testen, ist es, alle Werte (a11..ε(n) ⋅...⋅ag

1..mg) mod n zu berechnen. Erhält man dann ϕ(n) verschiedene Reste, erzeugt das betr. Tupel *

nZ .

– n gerade

a): n = 2⋅∏ αk

1i

ip (pi > 2) Entweder kann die 2 als ‘eigener’ Faktor betrachtet werden, so dass

dann k + 1 simultane Kongruenzen zu lösen sind, oder die 2 wird einer beliebigen Primzahlpotenz i

ipα zugerechnet, (da 2⋅ iipα ebenfalls zyklisch ist,) wobei dann aber die betr.

PW mod 2⋅ iipα zu bestimmen ist.

Beispiel 3 n = 2⋅5⋅7 = 70; ϕ(70) = 1⋅4⋅6 = 24; ε(70) = kgV(4, 6) = 12; g = 2 + 0 = 2; *70Z ≅ C12 ×××× C2

PW5: 2, 3; PW7: 3, 5; PW10: 3, 7; PW14: 3, 5 Ordnung 12: [25, 314] = [12, 25, 37] → 17; 17 ε/2 mod 70 = 29 Ordnung 2 : 70 – 1 = 69 ≠ 29 → (17, 69) erzeugt *

70Z .

b): n = 4⋅∏ αk

1i

ip (pi > 2) Es sind k + 1 Erzeuger erforderlich.

Beispiel 4 n = 4⋅3 = 12; ϕ(12) = 2⋅2 = 4; ε(12) = 2; g = 1 + 1 = 2; → *

12Z ≅ C2 ×××× C2

Da die drei Elemente > 1 alle Ordnung 2 haben müssen, erzeugt jede Kombination von zweien dieser Elemente *12Z ; z.B. (5, 11).

c): n = 2e (e > 2 ); ϕ(2e) = 2e – 1; ε(2e) = 2e – 2; g = 2; → *

2eZ ≅ 2e2C −−−− ×××× C2

Ein Erzeugerpaar für *

2eZ ist stets (5, 2e – 1).

Allgemein gilt: a ≡ ± 1 mod 2e – 1 → ord a = 2 für a > 1 (Anzahl 3) a ≡ ± 3 mod 8 → ord a = 2e – 2 = ε(2e) (Bemerkenswert ist, dass in den einschlägigen Beweisen regelmäßig nur die 5 angegeben wird – und nicht die 3.)

32

d) n = 2e⋅∏ αk

1i

ip (e > 2; pi > 2) Es sind k + 2 Erzeuger erforderlich.

Beispiel 5 n = 32⋅5 = 160; ϕ(160) = 2⋅8⋅4 = 64; ε(160) = 8; g = 3; 64 / 8 = 8. 8 ist in 2 Faktoren aufzuteilen, um eine Elementarteiler-Kette der Länge g = 3 zu erhalten: 8 = 4⋅2 → *

160Z ≅ C8 ×××× C4 ×××× C2

ord 8: 532 ord 4: 25 ord 2: 3132, 1532, 1732 (siehe obige Regel für 2e) Generell gilt: Für alle Elemente der Ordnung 2e – 2 in *

2eZ ist a ε/2 mod 2e = 2e – 1 + 1; daher ist

das Element der Ordnung 2 a = + 1 mod 2e – 1 (hier 17) kein erz. Element. ord 8: [532, 15] → 101; ord 4: [132, 25] → 97; ord 2: [3132, 15] → 31 Da 1014 mod 160 ≠ 31 und 972 mod 160 ≠ 31 sowie 1012 mod 160 ≠ 97 wird *

160Z vom

Tripel (101, 97, 31) erzeugt. Beispiel 6 n = 8⋅7⋅11 = 616; ϕ(616) = 4⋅6⋅10 = 240; ε(616) = kgV(4, 6, 10) = 30; g = 2 + 2 = 4 ϕ(n) / ε(n) = 8. 8 ist in 3 Faktoren aufzuteilen, um eine Elementarteiler-Kette der Länge g = 4 zu erhalten: 8 = 2⋅2⋅2 → *

616Z ≅ C30 ×××× C2 ×××× C2 ×××× C2

PW7: 3, 5; PW11: 2, 6, 7, 8 ord 30: z.B. [18, 57, 211] → 145 ord 2: (Anzahl in *

616Z : 24 – 1 =15) z.B. in *8Z 5 u. 7; in *

7Z die 6; in *11Z die 10

[78, 17, 111] = [78, 177] → 463; [58, 177] → 309; [18⋅7, 1011] → 505 Kontrolle: 145ε/2 mod 616 = 153 ≠ 505, 309, 463, 505⋅309, 505⋅463, 309⋅463, 309⋅463⋅505 je mod 616

→ Ein erz. Tupel für *616Z ist (145, 505, 463, 309).

Das Element der Ordnung 2, das man aus [18, 67, 1011] → 153 erhält, ist also in Verbindung mit 145 (ord 30) nicht brauchbar. Fazit: Die Kenntnis von Primitivwurzeln der Primteiler (> 2) von n reicht aus, um die Struktur sowie min. Erzeugendensysteme von *

nZ zu bestimmen.

------------------------------------------------- Nachstehend ein kleines Programm zur Lösung von beliebig großen Kongruenz–Systemen der Form x ≡ ci mod mi mit teilerfremden Moduln mi (wie das bei obigen Systemen der Fall ist). c1 = 1: m1 = 1 DO WHILE c1 <> 0 ‘Endlos-Schleife LINE INPUT "c ="; br$: c2 = VAL(br$): IF c2 = 0 THEN EXIT ‘Beenden LINE INPUT "m =";mr$: m2 = VAL(mr$) d = m1: e = m2: u1 = 1: v1 = 0: u2 = 0: v2 = 1

DO WHILE e <> 0 ‘ Lösung mittels Euklidischer Algori thmus q = d \ e: r = d MOD e: u3 = u1- q*u2: v3 = v1- q*v2 d = e: e = r: u1 = u2: v1 = v2: u2 = u3: v2 = v3

LOOP IF (c1 - c2) MOD d <> 0 THEN PRINT " Nicht lösbar ": EXIT s = (c1 - c2) \ d: m = (m1* m2) \ d: c = (c1 - u1* m1*s) MOD m: IF c < 0 THEN c = c + m PRINT c;" MOD ";m: c1 = c: m1 = m ‘ simultane Lösung der bis dahin eingegebenen Kongruenzen LOOP: END

33

Anlage 1 Einige Beziehungen zwischen den Teilern einer Zahl und den Inversen eines Elements Zwar ist – wie im Hauptteil vermerkt – der Mittelwert aller Inversendifferenzen unabhängig von der multiplikativen Struktur einer Zahl n, aber es gibt dennoch Zusammenhänge, wie die folgenden einfachen Beispiele zeigen. In folgenden ist zunächst n = p⋅q mit ungeraden Primzahlen p, q.

• Gegeben sei ein a ∈ Z n mit ggT( a, n) ∈ {p, q} Dann gilt: ggT( (a ± 1) – (a ± 1) – 1, n) ∈ {p, q}

• Gegeben sei ein a < n – 1 mit ord a = 2

Dann gilt: a ± 1 ∉ *nZ und als Folge des ersten Punktes hat man:

ggT( a ± 1, n) ∈ {p, q} (was bereits im letzten Punkt von Ziffer 4. des Hauptteils gezeigt wurde) und ggT( (a ± 2) – (a ± 2) – 1, n) ∈ {p, q} Gemäß Ziffer 4. des Hauptteils ist für n = p⋅q die Anzahl der nicht-trivialen Elemente der Ordnung 2 gleich 2 (= 2 2 – 2). Diese beiden Elemente sind also je von zwei Nullteilern „eingerahmt“.

• Gegeben sei ein a mit ord a = 4 Dann gilt: ggT( a + a – 1, n) ∈ {p, q} (Sind p und q je kongruent 3 (mod 4) gibt es keine Elemente der Ordnung 4.)

• Wie viele Elemente mit (1) ggT( a – a – 1, n) ∈ {p, q} bzw.

(2) ggT( a + a – 1, n) ∈ {p, q} gibt es? Die Anzahl G der Nullteiler in Z n \{0} ist n – ϕ (n) – 1. Da die gesuchten Elemente zu (1) ausschließlich unmittelbare ‚linke’ und ‚rechte’ Nachbarn der Nullteiler sind, ist die Anzahl der Elemente mit ggT(a – a – 1, n) ∈ {p, q} gleich 2G – 8. (Die – 8 ist Folge von Überlappungen.) Die Anzahl A der Elemente zu (2) hängt davon ab, wie viele Teiler von n kongruent

1 (mod 4) sind: n = p⋅q besitzt ...... ... keinen Teiler ≡ 1 mod 4 → A = 0.

... einen Teiler ≡ 1 mod 4 → A = 2(p – 1) wobei p der Teiler ≡ 3 mod 4 ist. Hinsichtlich der Ordnung von a findet man: 4 | ord a | 2(p – 1). Alle Ordnungen, die diese Bedingungen erfüllen, kommen auch tatsächlich unter (2) vor (, aber – mit Ausnahme ord a = 4 – erfüllt nicht jedes Element, das die ‚richtige’ Ordnung hat, (2)). Beispiel: n = p⋅q; p = 19 → A = 36; ord a ∈ { 36, 12, 4} ... zwei Teiler ≡ 1 mod 4 → A = 2G – 8 Hinsichtlich der Ordnung findet man: 4 | ord a | (p – 1) und / oder 4 | ord a | (q – 1).

Alle Ordnungen, die diese Bedingungen erfüllen, kommen auch tatsächlich unter (2) vor (, aber – mit Ausnahme ord a = 4 – erfüllt nicht jedes Element, das die ‚richtige’ Ordnung hat, (2)).

Beispiel: n = 17⋅37 → G = 52 → A = 96; ord a ∈ { 36, 16, 12, 8, 4}

34

Sind – in Umkehrung der obigen Fragestellung – die Faktoren p und q bekannt, lassen sich die Elemente a mit ord a = 2 bestimmen: Da eine der beiden Zahlen a ± 1 durch p, die andere durch q teilbar ist, und ihre Differenz ersichtlich gleich 2 ist, hat man die Gleichung x⋅p + y⋅q = 2. Diese lineare diophantische Gleichung ist z.B. mittels EEA oder dem Kettenbruchverfahren lösbar; die allgemeine Lösung ist mit t ∈ Z von der Form (x = x 0 + q⋅t, y = y 0 – p⋅t ). Den Nebenbedingungen |x| < q und |y| < p (wegen a < n) genügen stets genau zwei Lösungen (x, y) und folglich erhält man zwei Werte a = (|x⋅p| + |y⋅q|) / 2, für die ord a = 2 ist. Vorliegend erfüllt die Lösung (x 0, y 0) immer die o.a. Nebenbedingung. Wegen ord a = 2 → ord (n – a) = 2 ergibt sich der zweite a-Wert ‚automatisch’. Beispiel: p = 17; q = 7; n = p⋅q = 17⋅7 = 119 Alle Lösungen der Gleichung x⋅17 + y⋅7 = 2 sind x = – 4 – 7⋅t und y = 10 + 17⋅t. Die einzigen Lösungen, die x < q und y < p erfüllen, sind (– 4, 10) und (3, – 7). Die beiden Elemente mit Ordnung 2 sind also 50 und 69 (= 119 – 50). Besitzt n mehr als zwei Primfaktoren, gilt analog: Sei n = 1

1pα ⋅....⋅ sspα ungerade. Jede der beiden den 2 s – 2 nicht-trivialen Elementen der

Ordnung 2 unmittelbar benachbarten Zahlen ist durch mindestens einen der Faktoren iipα von n teilbar. Besitzt die eine Zahl x der s Faktoren von n als Teiler, so die andere s – x dieser Teiler; d.h.: Ist a ∈ *

nZ mit ord a = 2 → n | (a + 1)(a – 1) = a 2 – 1.

(Letzteres gilt auch, wenn n einen Faktor 2 e besitzt; allerdings spaltet sich dieser im Fall e > 1 in der Regel auf beide Zahlen auf, was für p i > 2 nicht möglich ist.) Die konkrete Berechnung geht im Fall s > 2 ähnlich wie oben gezeigt. Beispiel: p = 3 3; q = 11; r = 13 → n = 3861 Besitzt eine nat. Zahl s teilerfremde Faktoren, so gibt es 2 s – 1– 1 Zerlegungen dieser Zahl in zwei teilerfremde Faktoren f 1, f 2. Hier ist s = 3 und 2 2 – 1 = 3. Die drei Zerlegungen sind: 27⋅(11⋅13); 13⋅(27⋅11) und 11⋅(27⋅13) Damit sind die drei zu lösenden Gleichungen: x⋅27 + y ⋅143 = 2 → (x 0, y0) = (106, – 20) → a = 2861 ; n – a = a’ = 1000 x⋅297 + y ⋅13 = 2 → (x 0, y0) = (12, – 274) → a = 3563 ; n – a = a’ = 298 x⋅351 + y ⋅11 = 2 → (x 0, y0) = (– 2, 64) → a = 703 ; n – a = a’ = 1358 Für die 6 Werte a bzw. a’ gilt a 2 mod 3861 = 1; also ord a = 2. Mehr als zwei Lösungen, die Bedingungen |x⋅f 1| < n und |y⋅f 2| < n erfüllen, existieren nicht.

1

Anlage 2 Beispiel zur Anzahl zyklischer u. nicht-zyklischer Untergruppen

n = 2 5 ⋅3 3 ⋅19 ⋅43 ϕ (n) = 2 7 ⋅3 5 ⋅7 ε (n) = 2 3 ⋅3 2 ⋅7

Teiler von ϕ (n) Anzahl UG Teiler von ϕ (n) Anzahl UG UG-Ordnung zykl. n-zykl. UG-Ordnung zykl. n-zykl.

1 AUG( p 0 ) 1 - ϕ (n) = 217728 - 1 2 31 - 108864 - 31

3 13 - 72576 - 13 4 AUG (2 2 ) nach Formel 16 155 54432 - 171

6 = 2⋅3 → 31⋅13 403 - 36288 - 403 7 1 - 31104 - 1 8 AUG (2 3 ) nach Formel 16 275 27216 - 291

9 36 13 24192 - 49

12 = 3⋅4 → 13⋅16 + 13⋅155 208 2015 18144 - 2233

14 =2⋅7 → 31⋅1 31 - 15552 - 31 16 AUG(2 4 ) = AUG (2 3 ) - 291 13608 - 291

18 (2⋅9 → 31⋅36 + 31⋅13) 1116 403 12096 - 1519

21 = 3⋅7 quadratfrei 13 - 10368 - 13

24 = 3⋅8 208 3575 9072 - 3783 27 AUG(3 3 ) = AUG (3 2 ) - 49 8064 - 49

28 = 4⋅7 16 155 7776 - 171 32 AUG(2 5 ) = AUG (2 2 ) - 171 6804 - 171

36 = 4⋅9 → 171⋅49 576 7803 6048 - 8379

42 = 2⋅3⋅7 quadratfrei 403 - 5184 - 403

48 = 16⋅3 - 3783 4536 - 3783

54 = 2⋅27 - 1519 4032 - 1519 56 16 275 3888 - 291 63 36 13 3456 - 49

64 AUG(2 6 ) = AUG (2 1 ) - 31 3402 - 31 72 576 13683 3024 - 14259

81 - 13 2688 - 13 84 208 2015 2592 - 2223

96 - 2223 2268 - 2223 108 - 8379 2016 - 8379

112 - 291 1944 - 291 126 1116 403 1728 - 1519

128 AUG(2 7 ) = AUG (2 0 ) - 1 1701 - 1 144 - 14259 1512 - 14259 162 - 403 1344 - 403

168 208 3575 1296 - 3783 189 - 49 1152 - 49

192 - 403 1134 - 403 216 - 14259 1008 - 14259

224 - 171 972 - 171 243 - 1 896 - 1

252 576 7803 864 - 8379 288 - 8379 756 - 8379 324 - 2223 672 - 2223

336 - 3783 648 - 3783

378 - 1519 576 = 9⋅64 - 1519

384 = 3⋅128 - 13 567 = 7⋅81 - 13

432 = 16⋅27 - 14259 ε (n) = 504 = 7⋅8⋅9 576 13683

448 = 7⋅64 - 31 486 = 2⋅243 - 31

In der rechten und linken Hälfte der Tabelle sind Teiler und Komplementärteiler je Zeile gegenübergestellt (,da gleiche Gesamt-Anzahlen der UG – aber z.T. unterschiedliche Aufteilung in zyklisch und nicht-zyklisch). Die blau markierten Zahlen sind Teiler von ε (n). In der Zwischen-Spalte sind einige Hinweise zur Berechnung der betr. Anzahlen eingefügt.