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 Eigenschaft zu prüfen, wird bei algebraischen Strukturen oft ü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, Mächtigkeit und Index

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_{n}=\{a_{1},a_{2},\dots ,a_{n}\}$ ist die Ordnung ($n=ord(G)$) die Anzahl $n$ der Gruppenelemente. Sei $U$ Untergruppe der endlichen Gruppe $G_{n}$, also $U\leq G$. Die Anzahl der Links- bzw. Rechtsnebenklassen von $U$ in $G$ wird als Index $\vert G\colon U\vert$ von $G$ nach $U$ bezeichnet.

Eigenschaften additiver Restklassen

Alle Restklassen-Gruppen $\left\langle \mathbb {Z} _{n},\oplus \right\rangle$ mit $n=\{\;1,\dots ,12\;\}$ mit der Addition ${\bmod {n}}$ haben folgende Eigenschaften:

• in allen Gruppen gilt das Assoziativgesetz.
• es existiert ein neutrales Element $0$.
• zu jedem Element $a\in \mathbb {Z} _{n}$ existiert ein Inverses Element (bei der Addition schreiben wir $\mathbf {-a}$ anstelle von $\mathbf {a^{-1}}$).
• alle Gruppen $\mathbb {Z} _{n}$ sind zyklisch mit erzeugendem Element $1$.
• es gilt das Kommutativgesetz.

Additive Restklassen (n=6) - Operationstafel

$n=6\colon \ \left\langle \mathbb {Z} _{6},\oplus \right\rangle$ mit $\mathbb {Z} _{6}=\{\;0,1,2,3,4,5\;\}$

$\oplus$	$\color {green}0$	$1$	$2$	$3$	$4$	$5$
$\color {green}0$	$\color {green}0$	$\color {green}1$	$\color {green}2$	$\color {green}3$	$\color {green}4$	$\color {green}5$
$1$	$\color {green}1$	$2$	$3$	$4$	$5$	$0$
$2$	$\color {green}2$	$3$	$4$	$5$	$0$	$1$
$3$	$\color {green}3$	$4$	$5$	$0$	$1$	$2$
$4$	$\color {green}4$	$5$	$0$	$1$	$2$	$3$
$5$	$\color {green}5$	$0$	$1$	$2$	$3$	$4$

Eigenschaften multiplikativer Restklassen

Alle Restklassen-Monoide $\left\langle \mathbb {Z} _{n},\odot \right\rangle$ mit $n=\{\;1,\dots ,12\;\}$ mit der Multiplikation ${\bmod {n}}$ haben folgende Eigenschaften:

• in allen Strukturen gilt das Assoziativgesetz.
• es existiert ein neutrales Element $1$. Daher sind alle $\left\langle \mathbb {Z} _{n},\circ \right\rangle$ Monoide.
• nur für $n=1$ gibt es ein Inverses Element und somit ist nur $\mathbb {Z} _{1}$ eine Gruppe.
• nur für $n=1$ ist das Monoid zyklisch.
• es gilt das Kommutativgesetz.

Multiplikative Restklassen (n=6) - Operationstafel

$n=6\colon \ \left\langle \mathbb {Z} _{6},\odot \right\rangle$ mit $\mathbb {Z} _{6}=\{\;0,1,2,3,4,5\;\}$

$\odot$	$0$	$\color {green}1$	$2$	$3$	$4$	$5$
$0$	$0$	$\color {green}0$	$0$	$0$	$0$	$0$
$\color {green}1$	$\color {green}0$	$\color {green}1$	$\color {green}2$	$\color {green}3$	$\color {green}4$	$\color {green}5$
$2$	$0$	$\color {green}2$	$4$	$0$	$2$	$4$
$3$	$0$	$\color {green}3$	$0$	$3$	$0$	$3$
$4$	$0$	$\color {green}4$	$2$	$0$	$4$	$2$
$5$	$0$	$\color {green}5$	$4$	$3$	$2$	$1$

Multiplikative Restklassen (n=9) - Operationstafel

$n=9\colon \;\left\langle \mathbb {Z} _{9},\odot \right\rangle$ mit $\mathbb {Z} _{9}=\{\;0,1,2,3,4,5,6,7,8\;\}$

$\odot$	$0$	$\color {green}1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$0$	$0$	$\color {green}0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$\color {green}1$	$\color {green}0$	$\color {green}1$	$\color {green}2$	$\color {green}3$	$\color {green}4$	$\color {green}5$	$\color {green}6$	$\color {green}7$	$\color {green}8$
$2$	$0$	$\color {green}2$	$4$	$6$	$8$	$1$	$3$	$5$	$7$
$3$	$0$	$\color {green}3$	$6$	$0$	$3$	$6$	$0$	$3$	$6$
$4$	$0$	$\color {green}4$	$8$	$3$	$7$	$2$	$6$	$1$	$5$
$5$	$0$	$\color {green}5$	$1$	$6$	$2$	$7$	$3$	$8$	$4$
$6$	$0$	$\color {green}6$	$3$	$0$	$6$	$3$	$0$	$6$	$3$
$7$	$0$	$\color {green}7$	$5$	$3$	$1$	$8$	$6$	$4$	$2$
$8$	$0$	$\color {green}8$	$7$	$6$	$5$	$4$	$3$	$2$	$1$

Multiplikative Restklassen (n=9) - Eigenschaften zusammengefasst

${\begin{aligned}&{\text{algebraische Struktur: }}&{\text{kommutatives Monoid, keine Gruppe (da nicht alle Elemente invertierbar))}}\\&{\text{Restklassen: }}&\{\;{\overline {0}},\;{\overline {1}},\;{\overline {2}},\;{\overline {3}},\;{\overline {4}},\;{\overline {5}},\;{\overline {6}},\;{\overline {7}},\;{\overline {8}}\;\}\\&{\text{Operation: }}&{\text{Multiplikation modulo }}9\\&{\text{Neutrales Element: }}&\color {green}1\\&{\text{Assoziativität: }}&{\text{Ja}}\\&{\text{Kommutativität: }}&{\text{Ja}}\\&{\text{Inverse Elemente: }}&{\text{nur von den Einheiten: }}\{\;1,\;2,\;4,\;5,\;7,\;8\;\}\\&{\text{Nicht invertierbare Elemente: }}&\{\;0,\;3,\;6\;\}\end{aligned}}$

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\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:

$\cdot$	${\overline {1}}$	${\overline {2}}$	${\overline {4}}$	${\overline {5}}$	${\overline {7}}$	${\overline {8}}$
${\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}}$
${\overline {2}}$	$\color {green}{\overline {2}}$	${\overline {4}}$	${\overline {8}}$	${\overline {1}}$	${\overline {5}}$	${\overline {7}}$
${\overline {4}}$	$\color {green}{\overline {4}}$	${\overline {8}}$	${\overline {7}}$	${\overline {2}}$	${\overline {1}}$	${\overline {5}}$
${\overline {5}}$	$\color {green}{\overline {5}}$	${\overline {1}}$	${\overline {2}}$	${\overline {7}}$	${\overline {8}}$	${\overline {4}}$
${\overline {7}}$	$\color {green}{\overline {7}}$	${\overline {5}}$	${\overline {1}}$	${\overline {8}}$	${\overline {4}}$	${\overline {2}}$
${\overline {8}}$	$\color {green}{\overline {8}}$	${\overline {7}}$	${\overline {5}}$	${\overline {4}}$	${\overline {2}}$	${\overline {1}}$

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) Alle multiplikativen Restklassensysteme modulo $n$ sind assotiativ. Diese sind für alle $n$ zumindest kommutative Monoide.

Beweis (AG) (mit der Modulo-Operation $\odot$ nur für diesen Beweis)

Sei $a,b,c\in \mathbb {Z} _{n}=\{\;0,\dots ,\;(n-1)\;\}$, dann definieren wir die Multiplikation modulo $n$ (geschrieben als $\odot )$ wie folgt

$a\odot b\,\colon =(a\cdot b){\bmod {n}}$. 

Wir prüfen nun die Assoziativität der modulo-Multiplikation

$(a\odot b)\odot c=a\odot (b\odot c)$.

Da die Ganzzahlmultiplikation in ganz $\mathbb {Z}$ assoziativ ist, gilt $\;(a\cdot b)\cdot c=a\cdot (b\cdot c)\;$, mit $a,b,c\in \mathbb {Z} \;$ und für die Restklassendarstellung folgt daraus

$(a\odot b)\odot c=((a\cdot b){\bmod {n}})\odot c=(((a\cdot b){\bmod {n}})\cdot c){\bmod {n}}=\mathbf {((a\cdot b)\cdot c){\bmod {n}}=(a\cdot (b\cdot c)){\bmod {n}}} =(a\cdot ((b\cdot c){\bmod {n}}){\bmod {n}})=a\cdot (b\odot c){\bmod {n}}=a\odot (b\odot c)$.

(2) Wir berechnen beide Seiten und vergleichen die Resultate. Da wir in einer abgeschlossenen Unterstruktur des Restklassenmonoides $\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=((\color {red}9\cdot a_{k}\color {black}+\color {green}a_{r}\color {black})\cdot (\color {red}9\cdot b_{k}\color {black}+\color {green}b_{r}\color {black}))\cdot (\color {red}9\cdot c_{k}\color {black}+\color {green}c_{r}\color {black})\equiv (a_{r}\cdot b_{r})\cdot (\color {red}9\cdot c_{k}\color {black}+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 $9$ 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}}}={\overline {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