Grundlagen

Multiplikative Gruppe modulo n

 aufwärts

Die Menge ganze Zahlen10 = {0, ..., 9} bildet mit der Addition modulo 10 als Verknüpfung eine Gruppe. Mit der Multi­plikation modulo 10 als Verknüpfung bildet ganze Zahlen10 jedoch keine Gruppe, auch nicht, wenn die 0 ausgenommen wird, die bekanntlich kein inverses Element hat. Es stellt sich heraus, dass noch mehr Zahlen ausgenommen werden müssen, die ebenfalls kein inverses Element haben, nämlich 2, 4, 5, 6 und 8. Dieses sind genau die Zahlen, die einen echten Teiler mit 10 gemeinsam haben. Die schließlich ver­bleibenden vier Elemente bilden die multi­plikative Gruppe ganze Zahlen10*.

Die Gruppe ganze Zahlenn*

Definition:  Sei n Element natürliche Zahlen. Die Menge ganze Zahlenn* besteht aus allen Elementen von ganze Zahlenn, die teilerfremd zu n sind. Mit φ(n) wird die Anzahl der Elemente von ganze Zahlenn* bezeichnet.

ganze Zahlenn*  =  { k Element ganze Zahlenn  |  ggt(k, n) = 1 }

φ(n)  =  |ganze Zahlenn*|

Die Menge ganze Zahlenn* bildet mit der Multi­plikation modulo n als Verknüpfung und der 1 als neutralem Element eine abelsche Gruppe. Die Anzahl der Elemente von ganze Zahlenn* wird durch die eulersche Phi-Funktion φ(n) (nach L. Eulerzur Person) angegeben.

Beispiel:   

Satz:  Sei n Element natürliche Zahlen, n > 1. Dann ist

φ(n)  =  n ·Produkt p | n  (1 – 1/p)

Hierbei durchläuft p alle Primzahlen, die Teiler von n sind, einschließ­lich n selber, falls n eine Primzahl ist.

Beweis:  Von den anfänglich n Zahlen 1, ..., n ist jede p-te durch die erste Primzahl p teilbar; werden diese gestrichen, verbleiben n·(1-1/p) Zahlen. Von diesen ist wiederum ein Anteil von 1/q durch die zweite Primzahl q teilbar; werden diese gestrichen, verbleiben n·(1-1/p)·(1-1/q) Zahlen usw.

Beispiel:  φ(10)   =   10 · (1 – 1/2) · (1 – 1/5)   =   10 · 1/2 · 4/5   =   4

Korollar:  Wenn n eine Primzahl ist, gilt

φ(n)  =  n-1

Korollar:  Wenn n das Produkt zweier ver­schiedener Primzahlen p, q ist, also n = p·q, so gilt

φ(n)  =  (p-1)(q-1)

Zyklische Gruppe

Eine zyklische Gruppe wird von einem einzelnen Element erzeugt, d.h. G ist zyklisch, wenn es ein a Element G gibt mit G = spitze Klammer aufaspitze Klammer zu.

Beispiel:  Die Gruppe ganze Zahlen10* ist zyklisch, denn

ganze Zahlen10*  =  spitze Klammer auf3spitze Klammer zu  =  { 31, 32, 33, 34 }  =  { 3, 9, 7, 1 }

 

Die Gruppe ganze Zahlen7* ist zyklisch, denn

ganze Zahlen7*  =  spitze Klammer auf5spitze Klammer zu  =  { 51, ..., 56 }  =  { 5, 4, 6, 2, 3, 1 }

 

Die Gruppe ganze Zahlen15* ist nicht zyklisch. Jedes einzelne Element von ganze Zahlen15* erzeugt eine echte Untergruppe.

Satz:  Die Gruppe ganze Zahlenn* ist genau dann zyklisch, wenn n gleich 2, 4, pk oder 2pk mit p Primzahl, p>2 und k Element natürliche Zahlen ist. Insbesondere ist ganze Zahlenp* zyklisch, wenn p eine Primzahl ist.

Untergruppen

Auch wenn eine Gruppe G zyklisch ist, bedeutet dies nicht, dass jedes Element die Gruppe erzeugt. Manche Elemente erzeugen auch echte Untergruppen von G.

Beispiel:  Das Erzeugnis von 2 in der Gruppe ganze Zahlen7* ist

spitze Klammer auf2spitze Klammer zu  =  { 21, 22, 23 }  =  { 2, 4, 1 },

also eine echte Untergruppe. Allgemein sind, sofern ganze Zahlenn* selbst mehr als zwei Elemente enthält, stets

spitze Klammer auf1spitze Klammer zu  =  { 1 }   und

spitze Klammer aufn-1spitze Klammer zu  =  { n-1, 1 }

echte Untergruppen.

Die Anzahl der erzeugenden Elemente einer Gruppe G = ganze Zahlenp* mit p Primzahl und p>2 hängt von der Anzahl der echten Untergruppen von G ab. Je weniger echte Untergruppen, desto mehr erzeugende Elemente hat G.

Nach dem Satz von Lagrange teilt die Anzahl der Elemente einer Untergruppe U einer endlichen Gruppe G die Anzahl der Elemente von G:

|U|  |  |G|

Bei zyklischen Gruppen gehört zu jedem Teiler von |G| genau eine Untergruppe. Je weniger Teiler also |ganze Zahlenp*| = p-1 hat, desto weniger Untergruppen sind vorhanden und desto mehr erzeugende Elemente.

Da p ungerade ist, gilt

p-1  =  2·q

Somit sind 1, 2, q und 2q Teiler von p-1. Ist q Primzahl, so gibt es darüber hinaus keine weiteren Teiler.

Beispiel:  Es sei p = 7. Dann ist p-1 = 2·q mit q = 3 Primzahl. Die Untergruppen von ganze Zahlen7* ergeben sich als Erzeugnisse spitze Klammer aufaspitze Klammer zu der Elemente a Element G. Es gibt vier Untergruppen mit 1, 2, q = 3 und 2q = 6 Elementen:

U0  =  spitze Klammer auf1spitze Klammer zu  =  { 1 }

U1  =  spitze Klammer auf6spitze Klammer zu  =  { 1, 6 }

U2  =  spitze Klammer auf2spitze Klammer zu  =  spitze Klammer auf4spitze Klammer zu  =  { 1, 2, 4 }

U3  =  spitze Klammer auf3spitze Klammer zu  =  spitze Klammer auf5spitze Klammer zu  =  { 1, 2, 3, 4, 5, 6 }

 

Allgemein erzeugt je das Element 1 die UntergruppeU0 und das Element p-1 die Untergruppe U1. Von den ver­bleibenden p-3 Elementen erzeugen q-1 Elemente die Untergruppe U2. Wegen p-3  =  2(q-1) erzeugen also die Hälfte dieser p-3 Elemente eine echte Untergruppe und die andere Hälfte die gesamte Gruppe.

 

Genau die Hälfte aller p-3 Elemente von ganze Zahlenp*, die zwischen 2 und p-2 liegen, sind also erzeugende Elemente, wohlgemerkt jedoch nur, wenn p-1 = 2q mit q Primzahl ist, sonst sind es weniger. Eine Primzahl p dieser Form wird als starke Primzahl bezeichnet.

Starke Primzahl

Definition:  Eine Primzahl p heißt starke Primzahl, wenn sie von der Form

p  = 2·q + 1

mit q Primzahl ist.

Beispiel:  Die Primzahlen 5, 7, 11, 23, ... sind starke Primzahlen. Dagegen ist z.B. die Primzahl 13 keine starke Primzahl, weil 13 = 2·6 + 1 ist und 6 keine Primzahl ist.

Satz:  Sei p eine starke Primzahl und sei a Element {2, ..., p-2}. Dann ist a erzeugendes Element von ganze Zahlenp* genau dann, wenn gilt

a(p-1)/2 mod p  ≠  1

Um ein erzeugendes Element zu finden, wählt man solange zufällig ein a Element {2, ..., p-2}, bis a(p-1)/2 mod p  ≠  1 gilt. Die Wahr­schein­lich­keit, dabei ein erzeugendes Element zu wählen, beträgt wie oben gesehen jedesmal 1/2.

 

 

Weiter mit:   [Sätze von Fermat und Euler]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 29.04.2002   Updated: 16.10.2016
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik