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

Man bestimme die "primen" Restklassen modulo 16, d.h. alle Restklassen ${\overline {a}}$ mit ggT(a, 16)=1. Man zeige, dass die Menge $\Gamma _{16}$ 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[Bearbeiten | Quelltext bearbeiten]

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 Zatoby[Bearbeiten | Quelltext bearbeiten]

Zunächst betrachten wir die Restklassen modulo 16, also $\mathbb {Z} _{16}=\{{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}},{\overline {5}},{\overline {6}},{\overline {7}},{\overline {8}},{\overline {9}},{\overline {10}},{\overline {11}},{\overline {12}},{\overline {13}},{\overline {14}},{\overline {15}}\}$

Aus dieser Liste kann nun jede Zahl gestrichen werden, die mod 16 = 1 ergibt. Das sind in diesem Fall alle geraden Zahlen. D.h. übrig bleiben die Primzahlen sowie 9 und 15.

$\mathbb {\Gamma } _{16}=\{{\overline {1}},{\overline {3}},{\overline {5}},{\overline {7}},{\overline {9}},{\overline {11}},{\overline {13}},{\overline {15}}\}$

Gruppe[Bearbeiten | Quelltext bearbeiten]

Um zu zeigen, dass es sich um eine Gruppe handelt, müssen wir beweisen, dass sie

abgeschlossen und
assoziativ ist, sowie
ein neutrales Element und
zu jedem Element ein Inverses besitzt.

Alles bezüglich der Restklassenmultiplikation.

Abgeschlossenheit[Bearbeiten | Quelltext bearbeiten]

Da wir hier nur ungerade Zahlen miteinander multiplizieren, ist die Abgeschlossenheit eigentlich gegeben, weil bei einer Multiplikation zweier ungerader Zahlen immer eine ungerade Zahl herauskommt.

Wir können allerdings trotzdem die Operationstafel betrachten, da diese ohnehin für die restliche Übung nützlich (allerdings nicht nötig) ist.

${\begin{array}{c|cccccc}*&{\overline {1}}&{\overline {3}}&{\overline {5}}&{\overline {7}}&{\overline {9}}&{\overline {11}}&{\overline {13}}&{\overline {15}}\\\hline {\overline {1}}&{\overline {1}}&{\overline {3}}&{\overline {5}}&{\overline {7}}&{\overline {9}}&{\overline {11}}&{\overline {13}}&{\overline {15}}\\{\overline {3}}&{\overline {3}}&{\overline {9}}&{\overline {15}}&{\overline {5}}&{\overline {11}}&{\overline {1}}&{\overline {7}}&{\overline {13}}\\{\overline {5}}&{\overline {5}}&{\overline {15}}&{\overline {9}}&{\overline {3}}&{\overline {13}}&{\overline {7}}&{\overline {1}}&{\overline {11}}\\{\overline {7}}&{\overline {7}}&{\overline {5}}&{\overline {3}}&{\overline {1}}&{\overline {15}}&{\overline {13}}&{\overline {11}}&{\overline {9}}\\{\overline {9}}&{\overline {9}}&{\overline {11}}&{\overline {13}}&{\overline {15}}&{\overline {1}}&{\overline {3}}&{\overline {5}}&{\overline {7}}\\{\overline {11}}&{\overline {11}}&{\overline {1}}&{\overline {7}}&{\overline {13}}&{\overline {3}}&{\overline {9}}&{\overline {15}}&{\overline {5}}\\{\overline {13}}&{\overline {13}}&{\overline {7}}&{\overline {1}}&{\overline {11}}&{\overline {5}}&{\overline {15}}&{\overline {9}}&{\overline {3}}\\{\overline {15}}&{\overline {15}}&{\overline {13}}&{\overline {11}}&{\overline {9}}&{\overline {7}}&{\overline {5}}&{\overline {3}}&{\overline {1}}\end{array}}$

Es lässt sich erkennen, dass wir weiterhin in $\mathbb {\Gamma } _{16}$ bleiben. Damit ist die Abgeschlossenheit bewiesen.

Assoziativität[Bearbeiten | Quelltext bearbeiten]

Die Assoziativität ist durch die Restklassenmultiplikation bereits geben und daher trivial.

Neutrales Element[Bearbeiten | Quelltext bearbeiten]

${\overline {1}}$ verknüpft mit allen anderen Zahlen ergibt jeweils wieder die ursprüngliche Zahl, daher ist ${\overline {1}}$ das neutrale Element.

Inverse Elemente[Bearbeiten | Quelltext bearbeiten]

Da die gesamte Operationstafel eigentlich nicht nötig ist, um die Abgeschlossenheit zu beweisen (und es in diesem Beispiel ziemlich aufwändig ist, jeden Wert einzeln zu berechnen), können wir auch einfach nur die Stellen betrachten, die das neutrale Element, also ${\overline {1}}$ ergeben.

${\begin{array}{c|cccccc}*&{\overline {1}}&{\overline {3}}&{\overline {5}}&{\overline {7}}&{\overline {9}}&{\overline {11}}&{\overline {13}}&{\overline {15}}\\\hline {\overline {1}}&{\overline {1}}&{\overline {3}}&{\overline {5}}&{\overline {7}}&{\overline {9}}&{\overline {11}}&{\overline {13}}&{\overline {15}}\\{\overline {3}}&{\overline {3}}&&&&&{\overline {1}}&&\\{\overline {5}}&{\overline {5}}&&&&&&{\overline {1}}&\\{\overline {7}}&{\overline {7}}&&&{\overline {1}}&&&&\\{\overline {9}}&{\overline {9}}&&&&{\overline {1}}&&&\\{\overline {11}}&{\overline {11}}&{\overline {1}}&&&&&&\\{\overline {13}}&{\overline {13}}&&{\overline {1}}&&&&&\\{\overline {15}}&{\overline {15}}&&&&&&&{\overline {1}}\end{array}}$

Da in jeder Zeile und in jeder Spalte einmal das neutrale Element vorkommt, hat jede Zahl ein Inverses.

Damit ist bewiesen, dass es sich bei $\Gamma _{16}$ um eine Gruppe handelt.

Links[Bearbeiten | Quelltext bearbeiten]

Ähnliche Beispiele:

Wikipädia: