TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 404

Man bestimme die "primen" Restklassen modulo 9, d.h. alle Restklassen ${\overline {a}}$ mit ggT(a, 9)=1. Man zeige, daß die Menge $\Gamma _{9}$ dieser primen Restklassen bezüglich der Restklassenmultiplikation eine Gruppe bildet.

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Hilfreiches

Gruppe

Gruppe

Eine Gruppe $(G,\circ )$ mit Funktion $\circ :G\times G\rightarrow G$ ist

• abgeschlossen bzgl. der Operation $\circ$ in $G$ mit $a,b\in G$ gilt $a\circ b\in G$
• assoziativ: $\forall a,b,c\in G:a\circ (b\circ c)=(a\circ b)\circ c$
• besitzt ein neutrales Element $e$: $\exists e\in G:\forall a\in G:a\circ e=e\circ a=a$
• sowie besitzt inverse Elemente $a^{-1}$ bzw. $a'$: $\forall a\in G:\exists a^{-1}\in G:a\circ a^{-1}=a^{-1}\circ a=e$

Lösung von Baccus

$\Gamma _{9}$= {1,2,4,5,7,8}

Operationstafel:

${\begin{array}{c|cccccc}*&1&2&4&5&7&8\\\hline 1&1&2&4&5&7&8\\2&2&4&8&1&5&7\\4&4&8&7&2&1&5\\5&5&1&2&7&8&4\\7&7&5&1&8&4&2\\8&8&7&5&4&2&1\end{array}}$

Hieraus kann man ablesen:

• Die Operation ist abgeschlossen
• $\exists$ neutrales Element ("1")
• $\forall$ Elemente $\exists$ inverses Element (in allen Zeilen/Spalten kommt "1" vor)

Da $\Gamma _{9}<\mathbb {Z}$ und Assoziativität schon in $\mathbb {Z}$ gegeben ist, auch in $\Gamma _{9}$.

Alle Gruppenbedingungen sind erfüllt.

Hilfsmittel von Har203

Gruppe

Eine Gruppe ist ein geordnetes Paar $\left\langle G,\circ \right\rangle$ bestehend aus einer Menge $G$ und einer inneren zweistelligen Verknüpfung

$\circ \colon \,G\times G\to {G},\,(a,b)\mapsto {a}\circ b\,\in G\,,$

die „abgeschlossen“ ist (diese wichtige Voraussetzung zu prüfen wird oft bei algebraischen Strukturen übersehen)

$a,b\in G\implies \mathbf {a\circ b\in G}$

und, die die drei geforderten Gruppenaxiome erfüllt:

1. Assoziativität
   • $\forall \,a,b,c\,\in G$ gilt$\colon \;(a\circ b)\circ c=a\circ (b\circ c)$
2. Existenz eines neutralen Elementes
   • Es gibt ein neutrales Element $e\in G$ mit $\forall \,a\in G$ gilt$\colon \;a\circ e=e\circ a=a$ (falls dieses existiert, ist dieses eindeutig).
3. Für alle Gruppenelemente $a$ existent ein inverses Element
   • $\forall \,a\in G$ gilt$\colon \;\exists \,a^{-1}\in G$ mit$\colon \;a\circ a^{-1}=a^{-1}\circ a=e$.

Die Elemente einer Gruppe $\left\langle G,\circ \right\rangle$ heißen kurz Gruppenelemente.

Ordnung und Mächtigkeit einer Gruppe

Sei $\left\langle G,\circ \right\rangle$ eine Gruppe. Die Mächtigkeit $|G|$ wird auch als Ordnung der Gruppe bezeichnet. Für eine endliche Gruppe $G=\{a_{1},a_{2},\dots ,a_{n}\}$ ist die Ordnung die Anzahl $n$ der Gruppenelemente.

Teiler und Teilbarkeit

Seien $a,b\in \mathbb {Z}$. Gibt es eine ganze Zahl $k\in \mathbb {Z}$ mit $a\cdot k=b$, so sagen wir, dass $a$ die Zahl $b$ teilt und schreiben $a\mid {b}$. Insbesondere heißt in diesem Fall $a$ ein Teiler von $b$, bzw. $b$ ein Vielfaches von $a$.

In der Notation: $a\mid {b}\iff \exists \,k\in \mathbb {Z}$ mit$\colon \;a\cdot k=b$. Ist $a$ kein Teiler von $b$, so schreiben wir $a\nmid {b}$.

Restklasse

Es sei $m\in \mathbb {Z} \setminus {\{0\}}$ eine ganze Zahl und $a\in \mathbb {Z}$ eine beliebige ganze Zahl. Die Restklasse von $a$ modulo $m$, geschrieben als

$a+m\cdot \mathbb {Z} ,$

ist die Äquivalenzklasse von $a$ bezüglich der Kongruenz modulo $m$, also die Menge der Ganzzahlen, die bei Division durch $m$ den gleichen Rest wie $a$ ergeben. Sie besteht somit aus allen ganzen Zahlen $b$, die sich aus $a$ durch die Addition ganzzahliger Vielfacher von $m$ ergeben:

$a+m\cdot \mathbb {Z} =\{b\,|\,b=a+k\cdot m\,$, für ein $\,k\in \mathbb {Z} \}=\{b\,|\,b\equiv a{\bmod {m}})\}$.

Ein Element einer Restklasse bezeichnet man auch als Repräsentant der Restklasse. Häufig verwendet man die Standardrepräsentanten $\{{\overline {0}},{\overline {1}},{\overline {2}},\dots ,{\overline {m-1}}\}$.

Die Menge aller Restklassen modulo $m$ schreibt man häufig als $\mathbb {Z} /m\mathbb {Z}$ oder $\mathbb {Z} _{m}$. Sie hat $m$ Elemente und die Struktur eines algebraischen Ringes und wird deshalb Restklassenring genannt. Genau dann, wenn $m$ eine Primzahl ist, ergibt sich sogar die Struktur eines endlichen Körpers.

Eine Restklasse modulo $m$ heißt prime Restklasse, wenn ihre Elemente teilerfremd zu $m$ sind. Die Menge der primen Restklassen ist die Einheitengruppe $(\mathbb {Z} /m\mathbb {Z} )^{\times }$ oder $\left(\mathbb {Z} _{m}\right)^{*}$ im Restklassenring $\mathbb {Z} /m\cdot \mathbb {Z}$. Sie wird prime Restklassengruppe genannt und umfasst die multiplikativ und invertierbaren Restklassen.

ggT

Der größte gemeinsame Teiler $\operatorname {ggT}$ zweier ganzer Zahlen $a$ und $b$, von denen mindestens eine ungleich Null ist, ist die größte ganze Zahl $m$, so dass $m$ ein Teiler sowohl von $a$ als auch von $b$ ist. D.h.,

$\exists \,k,l\in \mathbb {Z}$ mit$\colon \;a=m\cdot k$ und $b=m\cdot l$

und $m$ die größte Zahl mit dieser Eigenschaft ist. Als Operator wird der $\operatorname {ggT} (a,\ b)$ geschrieben. Ist eine der beiden Zahlen $a$ und $b$ Null, so ist der $\operatorname {ggT}$ der absolute Wert der betragsmäßig größeren Zahl:

$\operatorname {ggT} (0,\ a)=\operatorname {max} (|0|,\ |a|)=\operatorname {max} (0,\ |a|)=|a|$,

da $|a|\geq 0$ ist und was auch mit $0=|a|\cdot 0$ und $a=|a|\cdot \operatorname {sgn} (a)$ übereinstimmt, wobei $\operatorname {sgn} (a)$ hier für $+1$ für positive und $-1$ für negative Zahlen steht. Dieser Fall ist weiterhin wichtig für den Abschluss des euklidischen Algorithmus.

Sind beide Zahlen Null, so ergibt letztere Regel

$\operatorname {ggT} (0,\ 0)=\operatorname {max} (|0|,\ |0|)=\operatorname {max} (0,\ 0)=0$,

was wiederum mit $0=0\cdot 0$ und $0=0\cdot 0$ übereinstimmt, auch wenn die Zahl $0$ mit dem Begriff größter gemeinsamer Teiler nicht harmonisiert. Einige Autoren lassen $\operatorname {ggT} (0,\ 0)$ jedoch ähnlich wie ${\tfrac {0}{0}}$ undefiniert.

Lösung von Har203

Die primen Restklassen modulo 9, d.h. alle Restklassen ${\overline {a}}$ für die gilt $\operatorname {ggT} (a,\ 9)=1$, werden durch die Repräsentanten angegeben:

$\mathbb {\Gamma _{9}} =\{{\overline {1}},{\overline {2}},{\overline {4}},{\overline {5}},{\overline {7}},{\overline {8}}\}$

Zu zeigen ist, dass $\left\langle \mathbb {\Gamma _{9}} ,\cdot \right\rangle$ eine Gruppe ist.

Wir werden die Abgeschlossenheit und die drei Gruppenaxiome zeigen:

1. Assoziativität
   • $\forall \,a,b,c\,\in \mathbb {\Gamma _{9}}$ gilt$\colon \;(a\cdot b)\cdot c=a\cdot (b\cdot c)$
2. Existenz eines neutralen Elementes
   • Es gibt ein neutrales Element $e\in G$ mit $\forall \,a\in G$ gilt$\colon \;a\circ e=e\circ a=a$ (falls dieses existiert ist dieses eindeutig).
3. Für alle Gruppenelemente $a$ existent ein inverses Element
   • $\forall \,a\in G$ gilt$\colon \;\exists \,a^{-1}\in G$ mit$\colon \;a\circ a^{-1}=a^{-1}\circ a=e$.

Abgeschlossenheit

Die Operationstafel für diese algebraische Struktur ist:

${\begin{array}{c|cccccc}\mathbf {\cdot } &\mathbf {\overline {1}} &\mathbf {\overline {2}} &\mathbf {\overline {4}} &\mathbf {\overline {5}} &\mathbf {\overline {7}} &\mathbf {\overline {8}} \\\hline \mathbf {\overline {1}} &\color {green}{\overline {1}}&\color {green}{\overline {2}}&\color {green}{\overline {4}}&\color {green}{\overline {5}}&\color {green}{\overline {7}}&\color {green}{\overline {8}}\\\mathbf {\overline {2}} &\color {green}{\overline {2}}&{\overline {4}}&{\overline {8}}&{\overline {1}}&{\overline {5}}&{\overline {7}}\\\mathbf {\overline {4}} &\color {green}{\overline {4}}&{\overline {8}}&{\overline {7}}&{\overline {2}}&{\overline {1}}&{\overline {5}}\\\mathbf {\overline {5}} &\color {green}{\overline {5}}&{\overline {1}}&{\overline {2}}&{\overline {7}}&{\overline {8}}&{\overline {4}}\\\mathbf {\overline {7}} &\color {green}{\overline {7}}&{\overline {5}}&{\overline {1}}&{\overline {8}}&{\overline {4}}&{\overline {2}}\\\mathbf {\overline {8}} &\color {green}{\overline {8}}&{\overline {7}}&{\overline {5}}&{\overline {4}}&{\overline {2}}&{\overline {1}}\end{array}}$ 

Die Abgeschlossenheit ist erfüllt, da für je zwei Elemente $a,b\in \mathbb {\Gamma _{9}}$ gilt$\colon \;a\cdot b\in \mathbb {\Gamma _{9}}$.

Assoziativität

Seien $a,b,c\in \mathbb {\Gamma _{9}}$ drei beliebigen Gruppenelemente. Zu prüfen ist, ob $\colon \;a\cdot (b\cdot c)=(a\cdot b)\cdot c.$.

Wir werden diese drei Elemente $a,b,c\;$ als Vertreter der Restklassen ($\{{\overline {a_{r}}},{\overline {b_{r}}},{\overline {c_{r}}}\}$) darstellen:

$a=9\cdot a_{k}+a_{r}\,,\qquad b=9\cdot b_{k}+b_{r}\,,\qquad c=9\cdot c_{k}+c_{r}\quad$ mit $\,a_{k},b_{k},c_{k}\in \mathbb {Z}$ und $\,a_{r},b_{r},c_{r}\in \{1,2,4,5,7,8\}$.

Hier können wir drei unterschiedliche Varianten des Beweises heranziehen:

1. Die Struktur von $\left\langle \mathbb {\Gamma _{9}} ,\cdot \right\rangle$ ist eine Untergruppe von der Restklassengruppe $\left\langle \mathbb {Z} _{9},\cdot \right\rangle$ ($\mathbb {\Gamma _{9}} \leqslant \mathbb {Z_{9}}$) und somit natürlich genauso wie $\mathbb {Z_{9}}$ assoziativ. Auch eine Einbettung in ganz $\mathbb {Z}$ ist kein Beweis für das Assoziativgesetz.
2. Wir berechnen beide Seiten und vergleichen die Resultate. Da wir quasi im Restklassenring $\mathbb {Z_{9}}$ rechnen, können wir Vielfache von $9$ einfach weglassen (z.B. $9\cdot a_{k}\cdot b_{k},\dots$).
   • ${\begin{aligned}(a\cdot b)\cdot c=((9\cdot a_{k}+\color {green}a_{r}\color {black})\cdot (9\cdot b_{k}+\color {green}b_{r}\color {black}))\cdot (9\cdot c_{k}+\color {green}c_{r}\color {black})\equiv (a_{r}\cdot b_{r})\cdot (9\cdot c_{k}+c_{r}){\bmod {9}}\equiv \color {green}a_{r}\cdot b_{r}\cdot c_{r}\color {black}{\bmod {9}}\end{aligned}}$
3. Wir berechnen beide Seiten genau und vergleichen ebenfalls die Resultate. Wegen der modulo-Operationen ist $m\in \mathbb {Z}$ irrelevant und passend zu wählen.

${\begin{aligned}a\cdot (b\cdot c)=&(9\cdot a_{k}+a_{r})\cdot ((9\cdot b_{k}+b_{r})\cdot (9\cdot c_{k}+c_{r}))=\\[1ex]&(9\cdot a_{k}+a_{r})\cdot (9\cdot 9\cdot b_{k}\cdot c_{k}+9\cdot b_{r}\cdot c_{k}+9\cdot b_{k}\cdot c_{r}+b_{r}\cdot c_{r})=\\&\,\,9\cdot (81\cdot a_{k}\cdot b_{k}\cdot c_{k}+9\cdot a_{k}\cdot b_{r}\cdot c_{k}+9\cdot a_{k}\cdot b_{k}\cdot c_{r}+9\cdot a_{r}\cdot b_{k}\cdot c_{k}+a_{k}\cdot b_{r}\cdot c_{r}+a_{r}\cdot b_{r}\cdot _{k}+a_{r}\cdot b_{k}\cdot c_{r})+(a_{r}\cdot b_{r}\cdot c_{r})=\\[1ex]&\,\,9\cdot m+(a_{r}\cdot b_{r}\cdot c_{r})\equiv \color {green}a_{r}\cdot b_{r}\cdot c_{r}\color {black}{\bmod {9}}\end{aligned}}$

D.h. auch die Resultate der zweiten und dritten Variante stimmen überein und zeigen, dass diese Struktur assoziativ ist.

Neutrales Element

In der Operationstafel sehen wir sofort, dass in der Zeile und der Spalte der Restklasse ${\overline {1}}$ mit den grünen Elementen gilt:

$\forall \,{\overline {a}}\in \mathbb {\Gamma _{9}}$ gilt$\colon \;{\overline {1}}\cdot {\overline {a}}={\overline {a}}\cdot {\overline {1}}$

Diese Eigenschaft ist leicht zu erkennen, da die Zeilen- und Spaltenüberschriften mit den Elementen an diesen Stellen übereinstimmen.

Inverses Element

In der Operationstafel sehen wir sofort, dass in jeder Zeile und jeder Spalte das neutrale Elementen vorkommt:

$\forall \,{\overline {a}}\in \mathbb {\Gamma _{9}}$ gilt$\colon \;\exists \,{\overline {a^{-1}}}$ mit$\colon \,{\overline {a^{-1}}}\cdot {\overline {a}}={\overline {a}}\cdot {\overline {a^{-1}}}$

Da die Abgeschlossenheit und die drei Gruppenaxiome nachgewiesen wurden, wissen wir, dass es sich um eine Gruppe handelt. $\qquad \blacksquare$

Links

• Diskussion im UE-Forum

Ähnliche Beispiele:

• TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 280
• TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 281

Wikipädia:

• Gruppen
• Assoziativität
• Neutrale Elemente
• Inverse Elemente