| (6) | Gruppen |

anchored to [[104.00_anchor_math]] was covered in [[math2_gruppen]] too

| Overview |

Die grundlegende Definition einer Gruppe, haben wir folgend bereits bestimmt, möchten in diesem Konzept jetzt aber weitere Betrachtung dieser festlegen und notieren:

![[math2_gruppen#Definition]]

| Definition (6.1) | Potenzen | Vielfache von Gruppenelementen |

Betrachten wir eine Gruppe $(G,\cdot )$ welche ein neutrales Element $e$ aufweist. Weiterhin möchten wir jetzt ein Element aus $G$ betrachten: $a\in G$:

Wir haben jetzt folgende Eigenschaften, die wir bei der Hintereinanderausführung der Gruppen-Operation, hier also Multiplikation $\cdot$, betrachten und beschreiben können:

[!Definition] Potenzen von Gruppenelementen: Wir definieren jetzt folgende Eigenschaften für Potenzen:

1. $a^0:=e$ –> denn dieser Wert existiert technically nicht

2. $a^1:=a$ –> den Wert einmalig abrufen, wird uns den Wert geben /

3. $a^m:=\{\begin{array}{ll}{a}^{m-1}\cdot a& \text{ falls }m\in \mathbb{N}\\ (a^{-1}{)}^{-m}& \text{ falls}m\in {\mathbb{Z}}^{-}\end{array}$

[!Definition] Vielfache von Gruppenelementen: Wir möchten jetzt noch die Vielfache von einem Gruppenelement definieren und die Eigenschaften notieren: Sei dafür jetzt $(G,+)$ eine Gruppe mit der Gruppenoperation +!

1. $0\cdot a:=e$

2. $1\cdot a:=a$

3. $m\cdot a:=\{\begin{array}{ll}(m-1)\cdot a+a& \text{fu¨r }m\in \mathbb{N}\\ -m\cdot (-a)& \text{ fu¨r }m\in {\mathbb{Z}}^{-}\end{array}$ Dabei meinen wir mit $-a$ das Inverse von $a$ bezüglich der Addition

| Satz (6.2) |

Ferner können wir jetzt noch ein paar Eigenschaften betrachten, die sich auf die Eigenschaften von Potenzen beziehen:

[!Definition] Eigenschaften für Potenzen: Diese Eigenschaften sind prinzipiell bekannt und nachollziehbar, jedoch haben wir sie jetzt genommen und definieren sie für alle möglichen Gruppen, die wir konstruieren können. Damit entbinden wir uns etwa dem Zahlenraum $\mathbb{Z},\mathbb{R}$ !

1. $(a^{-1}{)}^m=(a^m{)}^{-1}=a^{-m},\forall m\in \mathbb{Z}$

2. $a^m\cdot a^n=a^{m+n},\forall m,n\in \mathbb{Z}$

3. $(a^m{)}^{nn}=a^{m\cdot n},\forall m,n\in \mathbb{Z}$

Folgenden Satz können wir anschließend noch beweisen, und dabei sehen, dass wir so in einer Gruppe arbeiten könne, obwohl sie nicht wirklich eine Multiplikation definiert hat.

| Beweis (zu [[#Satz (6.2)|6.2]])

Wir möchten folgend die Aussage 1. aus dem Satz [[#Satz (6.2)]] Beweisen: Es gilt also zu zeigen, dass $(a^{-1}{)}^m=(a^m{)}^{-1}=a^{-m}$ ist: Sei dafür jetzt $m\in \mathbb{N}$ sodass dann $$\begin{array}{rl}(a^{-1}{)}^m\cdot a^m=& (a^{-1}\cdot \dots \cdot a^{-1}{)}_{m-mal}\cdot (a\cdot \dots \cdot a{)}_{m-mal}\\ =& a\cdot a_{inverse}^{-1}\dots a\cdot a^{-1}\\ =& e\\ ⟹& (a^{-1}{)}^m=(a^m{)}^{-1}\end{array}$$ und somit follgt dann jetzt: $a^{-m}=(a^{-}{)}^m$ -> und es gilt somit $\forall m\in \mathbb{N}$! Unter weiterer Betrachtung ist: $a^{-m},m=0⟹e$

Weiterhin wollen wir noch $m\in {\mathbb{Z}}^{-}$ anschauen: Da jetzt hier $-m\in \mathbb{N}$ ist, wenden wir den vorher umgesetzten Beweis für $a$ jetzt für $a^{-1}$, sowie $-m$ an. Es folgt dann jetzt: $$((a^{-}{)}^{-1}{)}^{-m}⟺((a^{-1}{)}^{-m}{)}^{-1}=(a^{-1}{)}^{-(-m)}=(a^{-1}{)}^m$$ 2., sowie 3 lassen sich anschließend via Induktion beweisen, bauen aber auf ähnlicher Umformung auf!

| Definition / Satz (6.3) | Ordnung, zyklischer Gruppen |

Betrachten wir eine Gruppe $G$, welche endlich ist und weiterhin $g\in G$:

[!Definition] Exponent der das neutrale Element resultieren lässt Es existiert für ein gegebenes Element $g\in G$ eine kleinste natürliche Zahl $n$, sodass dann: $$g^n=e,\text{ wenn multiplikative Verknu¨pfung}$$ Hierbei heißt das $n$ dann entsprechend Ordnung $o(g)$ von $g$ ! Bei einer additiven Verknüpfung gilt: $$n\cdot g=e$$

Da die Gruppe endlich ist, wird bei der Verknüpfung des Elementes mit sich selbst immer ein neues Element innerhalb der Gruppe auftreten. Weiterhin wird man irgendwann eine Grenze erreichen, etwa $6\in {\mathbb{Z}}_6$ und danach werden wir wieder innerhalb dieser Gruppe resultieren –> wir werden sicher irgendwann das neutrale Element $e$ erreichen!

Wir betrachten jetzt noch eine spezifische Menge, die resultieren / auftreten kann:

| erzeugte zyklische Gruppen |

[!Definition] erzeugte zyklische Gruppe $⟨g⟩$ Mit der folgenden Menge:

• $\{g^0=e,g^1=g,g^2,\dots ,g^{n-1}\}$ ( in der Multiplikativen Gruppe)
• $\{0\cdot g=e,1\cdot g=g,2g,\dots ,(n-1)\cdot g\}$ ( in der additiven Gruppe) beschreiben wir eine Untergruppe von $G$, welche durch g erzeugt wird. Wir wissen, aus a bereits, dass diese Operation zyklisch ist und sich irgendwann wiederholen wird. Wir nennen diese erzeugte, endliche, Gruppe jetzt von $g$ erzeugte zyklische Gruppe $⟨g⟩$.

| Ordnung $\mid g\mid$ teilt $\mid G\mid$

[!Important] $o(g)=|⟨g⟩|=n$ teilt $\mid G\mid$! Es folgt hierbei jetzt, dass$o(g)=|⟨g⟩|=n$ weiterhin die Ordnung der Obergruppe $G$ teilen wird –> Also die Menge von Elementen der Gruppe $G$ wird entsprechend geteilt von der Ordnung dieser Subgruppe $⟨g⟩$

Da wir jetzt gesehen, betrachten konnten, dass die Ordnung gleich $n$ ist und weiterhin die Ordnung der Obergruppe $\mid G\mid$ teilt, können wir jetzt noch folgende Eigenschaften betrachten:

| Zusammenhang Ordnung Gruppe und Untergruppe |

[!Definition] Zusammenhang Ordnung der Gruppe und Ordnung der Untergruppe Es folgt: $g^{\mid G\mid }=e$ Warum? Weil wir wissen, dass $\mid G\mid =k\cdot n$ ist und somit folgt dann: $g^n\cdot k=e\cdot e\cdot \cdots \cdot e$ –> und somit haben wir folgend eine Wiederholung gefunden. Das liegt daran, dass $n\mid |G|$ !

| Folgerungen für zyklische Gruppen |

[!Important] Folgerung für zyklische Gruppen Folgend nennen wir eine folgende Gruppe zyklisch, falls sie von einem ELement erzeugt werden kann!

Als Beispiel hier etwa: $({\mathbb{Z}}_3,\oplus )$ ist zyklisch! $\{0,1,2\}$ -> $⟨1⟩=\{0\cdot 1=0,1\cdot 1=1,2\cdot 2=2\}$ -> ist zyklisch!

| Beweisen von ([[#Definition / Satz (6.3) Ordnung, zyklischer Gruppen|6.3]])

// Der Beweis dieser Aussagen // #refactor #nachtragen -> Existenz einer Zahl $n$, die eine zyklische Wiederholung verursachen wird!

Wir möchten jetzt noch [[#erzeugte zyklische Gruppen]] zeigen / beweisen:

Betrachten wir zuerst für eine multiplikative Gruppe. Gefordert ist folgend: $\{g^0,g^1,g^2,\dots ,g^n\}$ und dass das Produkt zweier Elemente $\in ⟨g⟩$ wieder in $⟨g⟩$ liegen muss! Folgende Betrachtung: $(g^i\cdot g^j=g^{i+j}=g^{k\cdot n+r}=(g^n{)}^k\cdot g^r=g^r)$ Und mit dieser Berechnung können wir jetzt fortfahren, und so alle Elemente entsprechend konstruieren.

Weiter brauchen wir noch neutrales, inverse Element eines jeden Eintrages in unserer Gruppe / Menge neutrales Element: $g^0=e(=g^n)$ inverses Element: $g^i:(g^i{)}^{-1}=g^{n-i}$ –> also wir können durch die Subtraktion der Ordnung, die gegeben ist, dann einfach das Inverse bilden / konstruieren.

Aus diesen Forderungen folgt jetzt; $⟹⟨g⟩\le G$ –> also $⟨g⟩$ bildet eine Untergruppe von $G$ !

| Exkurs | Satz von Lagrange

Um die obige Aussage beweisen zu können, benötigen wir ferner den Satz von Lagrange: Weitere Informationen: here

[!Definition] Exkurs | Satz von Lagrange Bei endlichen Gruppe teil die Ordnung jeder Untergruppe immer die Gruppenordnung selbst!

Das heißt jetzt also: $$(G\text{ endlich}.U\le G\text{ ist Untergruppe}⟹|U|\mid |G|)$$ –> Also gilt dann folgend: $n=o(g)=|⟨g⟩|\mid |G|$

–> Unter dieser Betrachtung können wir dann den Beweis für [[#erzeugte zyklische Gruppen]] beenden bzw. begründen!

| Beweis von ([[#Definition / Satz (6.3) Ordnung, zyklischer Gruppen|6.3]])

Wir möchten jetzt noch [[#Zusammenhang Ordnung Gruppe und Untergruppe]] beweisen! Aus der vorherigen Betrachtung können wir jetzt folgern: $\mid G\mid =n\cdot k$ für ein beliebiges $k\in \mathbb{N}$! und dadurch folgt jetzt: $g^{\mid G\mid }=g^{n\cdot k}=(g^n{)}^k=e^k=e$ –> und somit haben wir das gezeigt ( so hab ich es auch schon bei Der Vorlesung überlegt! woow)

| Beispiele für [[#Definition / Satz (6.3) Ordnung, zyklischer Gruppen]] |

Betrachten wir: $$\begin{array}{rl}& ({\mathbb{Z}}_3\setminus \{0\},\odot )\\ g& =1:⟨1⟩=\{1^1=1,1^1=1,1^2=1,\dots \}=\{1\}\\ & ⟹o(1)=1!\\ g& =2:⟨2⟩=\{2^0=1,2^1=2,\underline{2^2=4=1}\}={\mathbb{Z}}_3\setminus \{0\},\\ & ⟹o(2)=2\\ & ⟹\text{ das heißt jetzt folgend }({\mathbb{Z}}_3\setminus \{0\}.\odot )\text{ ist zyklisch mit erzeuengendem Element: }2\end{array}$$

Wir möchten ferner noch ein Beispiel betrachten: $$\begin{array}{rl}({\mathbb{Z}}_5\setminus \{0\},\odot )& \\ ⟨2⟩=& \{2^0=1,2^1=2,2^2=4,2^3=3,2^4=1\}=\{1,2,3,4\}\\ & ⟹o(2)=4\\ & ⟹\text{ist yklische Gruppe mit erzeugendem Element}2\end{array}$$

$$\begin{array}{rl}({\mathbb{Z}}_7\setminus \{0\},\odot )& \\ ⟨2⟩=& \{2^0=1,2^1=2,2^2=4,\underline{2^3=8=1}\}=\{1,2,4\}\\ & ⟹o(2)=3\\ & ⟹\text{ ist nicht erzeugend! denn wir treffenn nicht alle Elemente hier!}\\ & \text{es existiert dennoch ein element:}\\ ⟨?⟩=& ({\mathbb{Z}}_7\setminus \{0\},\odot )\end{array}$$

| Korollar (6.5) |

Es folgen zwei Sätze, die in ihrer Ausführung für die Anwendung bei [[104.11_elementare_zahlentheorie#Anwendung Zahlentheorie RSA|RSA]] bzw [[netSec_RSA]] notwendig bzw. wichtig sind, weil man so beim Ent/Verschlüsseln hohe Potenzen verkleinern / vereinfachen kann :)

| Satz von Euler |

[!Definition] Satz von Euler Sei $n\in \mathbb{N}$ und $a\in \mathbb{Z}$, und weiterhin gilt bei beiden: $\gcd (a,n)=1$ -> sie sind teilerfremd!

Es folgt jetzt: Es ist jetzt $a^{\phi (n)}\equiv 1\mathrm{mod}(n)$ (Anwendung etwa bei [[netsec_ElGamal]]!) Wenn wir in so einer Potenz $a^{12345}\mathrm{mod}(n)$ sehen, dass in dieser Potenz $\phi (n)$ zu finden ist, dann wird da halt $1$ rauskommen und wir können es somit einfach berechnen! ->> Man muss also in dieser Potenz entsprechend dieses $\phi (n)$ finden!

| Kleiner Satz von Fermat |

[!Definition] Primzahl Berechnung Ist $p$ eine Primzahl, $a\in \mathbb{Z},p\nmid a$ dann gilt jetzt: $a^{p-1}\equiv 1\mathrm{mod}(p)$

-> Wir sehen hier, dass diese Berechnung ähnlich zu [[#Satz von Euler]] ist, aaber ein gewisser Spezialfall dessen ist!

Beweis beider Aussagen |

Wir möchten zuerst [[#Satz von Euler]] beweisen: Wir könne vorerst annehmen, dass $1\le a<n$ und da wir jetzt aus dem $\gcd (a,n)=1$ wissen, gilt weiter, dass $a\in {\mathbb{Z}}_n^{\ast }$ –> Es muss also invertierbar sein, in ${\mathbb{Z}}_n^{\ast }$, weiterhin wissen wir, dass diese Menge eine endliche Gruppe ist. Und in endlichen Gruppen gilt folgend wieder [[#Zusammenhang Ordnung Gruppe und Untergruppe]] Das können wir jetzt anwenden: $$\begin{array}{rlr}⟹& a^{\mid {\mathbb{Z}}_n^{\ast }\mid }=1& \odot \\ ⟹& a^{\phi (n)}\equiv 1\mathrm{mod}(n)& \end{array}$$ Ferner betrachten wir noch den Beweis für [[#Kleiner Satz von Fermat]]: Prinzipiell folgt es noch aus dem Beweis, den wir soeben betrachtet haben, aber wir haben noch weitere Invarianten: $$(n=p,\phi (p)=p-1)$$