de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Zahlentheorie
  • Modulare Arithmetik
  • Restklassenring
  • Operationen
  • Multiplikation von Restklassen
Nachlesen

Multiplikation von Restklassen

Bei der Multiplikation von Restklassen (auch Restklassenmultiplikation) wird das Produkt zweier Restklassen bestimmt, indem die Restklasse des Produkts ihrer Repräsentanten bestimmt wird.

Inhalt

Definition

Gegeben seien ganze Zahlen \(x,y \in \Z\) sowie eine natürliche Zahl \(m \in \N\). Für Elemente \({[x]}_m\) und \({[y]}_m\) des Restklassenrings \(\Z_m\) wird die Restklassenmultiplikation \(\odot\) wie folgt definiert:

\[ \begin{array}{c} \odot: \Z_m \times \Z_m \rightarrow \Z_m \\[0.5em] {[x]}_m \odot {[y]}_m = {[x \cdot y]}_m \end{array} \]

In Worten: Beim Produkt der Restklassen \({[x]}_m\) und \({[y]}_m\) handelt es sich um die Restklasse des Produkts \(x \cdot y\) ihrer (ganzzahligen) Repräsentanten.

Hinweis: Anstelle des Operators \(\odot\) wird für die Restklassenmultiplikation häufig auch vereinfachend der Operator \(\cdot\) verwendet.

Beispiele

Beispiel 1

Es soll das Produkt der Restklassen \({[3]}_5\) und \({[4]}_5\) berechnet werden. Gemäß der Definition der Multiplikation von Restklassen ergibt sich:

\begin{align*} {[3]}_5 \odot {[4]}_5 &= {[3 \cdot 4]}_5 \\[0.5em] &= {[12]}_5 \\[0.5em] &= {[2]}_5 \end{align*}

Da es sich bei \({[12]}_5\) nicht um den Standardvertreter der Restklasse handelt, wird das Zwischenergebnis im letzten Schritt entsprechend umgerechnet.

Beispiel 2

Es soll das Produkt der Restklassen \({[7]}_{13}\), \({[11]}_{13}\) und \({[2]}_{13}\) berechnet werden. Gemäß der Definition der Multiplikation von Restklassen ergibt sich:

\begin{align*} {[7]}_{13} \odot {[11]}_{13} \odot {[2]}_{13} &= {[7 \cdot 11 \cdot 2]}_{13} \\[0.5em] &= {[154]}_{13} \\[0.5em] &= {[11]}_{13} \end{align*}

Da es sich bei \({[154]}_{13}\) nicht um den Standardvertreter der Restklasse handelt, wird das Zwischenergebnis im letzten Schritt entsprechend umgerechnet.

Eigenschaften

Assoziativität

Die Multiplikation von Restklassen modulo \(m\) ist assoziativ.

\begin{align*} \Bigl( {[x]}_m \odot {[y]}_m \Bigr) \odot {[z]}_m &= {[x]}_m \odot \Bigl( {[y]}_m \odot {[z]}_m \Bigr) \\[0.5em] &= {[x]}_m \odot {[y]}_m \odot {[z]}_m \end{align*}

Wie üblich kann aufgrund der Assoziativität auch eine klammerfreie Notation verwendet werden.

Die Assoziativität kann durch direktes Nachrechnen gezeigt werden. In den Schritten (1), (2), (4) und (5) wird die Definition der Multiplikation von Restklassen verwendet. Die Gültigkeit von (3) folgt aus der Assoziativität der Multiplikation von ganzen Zahlen.

\begin{align*} \bigl( {[x]}_m \odot {[y]}_m \bigr) \odot {[z]}_m &\overset{(1)}{=} {[x \cdot y]}_m \odot {[z]}_m \\[0.5em] &\overset{(2)}{=} {[(x \cdot y) \cdot z]}_m \\[0.5em] &\overset{(3)}{=} {[x \cdot (y \cdot z)]}_m \\[0.5em] &\overset{(4)}{=} {[x]}_m \odot {[y \cdot z]}_m \\[0.5em] &\overset{(5)}{=} {[x]}_m \odot \bigl( {[y]}_m \odot {[z]}_m \bigr) \end{align*}

Kommutativität

Die Multiplikation von Restklassen modulo \(m\) ist kommutativ.

\[ {[x]}_m \odot {[y]}_m = {[y]}_m \odot {[x]}_m \]

Die Kommutativität kann durch direktes Nachrechnen gezeigt werden. In den Schritten (1) und (3) wird die Definition der Multiplikation von Restklassen verwendet. Die Gültigkeit von (2) folgt aus der Kommutativität der Multiplikation von ganzen Zahlen.

\begin{align*} {[x]}_m \odot {[y]}_m &\overset{(1)}{=} {[x \cdot y]}_m \\[0.5em] &\overset{(2)}{=} {[y \cdot x]}_m \\[0.5em] &\overset{(3)}{=} {[y]}_m \odot {[x]}_m \end{align*}

Distributivität

Für die Multiplikation und die Addition bzw. die Subtraktion von Restklassen modulo \(m\) gelten die Distributivgesetze.

\begin{align*} {[x]}_m \odot \Bigl( {[y]}_m \oplus {[z]}_m \Bigr) &= {[x]}_m \odot {[y]}_m \oplus {[x]}_m \odot {[z]}_m \\[0.5em] {[x]}_m \odot \Bigl( {[y]}_m \ominus {[z]}_m \Bigr) &= {[x]}_m \odot {[y]}_m \ominus {[x]}_m \odot {[z]}_m \end{align*}

Die Distributivität kann durch direktes Nachrechnen gezeigt werden. In den Schritten (1) und (4) wird die Definition der Addition von Restklassen verwendet. In den Schritten (2) und (5) wird die Definition der Multiplikation von Restklassen verwendet. Die Gültigkeit von (3) folgt aus der Distributivität der Addition/Multiplikation von ganzen Zahlen.

\begin{align*} {[x]}_m \odot \bigl( {[y]}_m \oplus {[z]}_m \bigr) &\overset{(1)}{=} {[x]}_m \odot {[y+z]}_m \\[0.5em] &\overset{(2)}{=} {[x \cdot (y+z)]}_m \\[0.5em] &\overset{(3)}{=} {[x \cdot y + x \cdot z]}_m \\[0.5em] &\overset{(4)}{=} {[x \cdot y]}_m \oplus {[x \cdot z]}_m \\[0.5em] &\overset{(5)}{=} {[x]}_m \odot {[y]}_m \oplus {[x}]_m \odot {[z]}_m \end{align*}

Der Beweis für die Subtraktion funktioniert analog.

Neutrales Element

Beim Element \({[1]}_m\) handelt es sich um das neutrale Element der Multiplikation. Für alle \({[x]}_m \in \Z_m\) gilt:

\[ {[1]}_m \odot {[x]}_m = {[x]}_m = {[x]}_m \odot {[1]}_m. \]

Dies kann durch direktes Nachrechnen gezeigt werden. In den Schritten (1) und (4) wird die Definition der Multiplikation von Restklassen verwendet. Die Gültigkeit von (2) und (3) folgt aus der Tatsache, dass es sich bei \(1\) um das neutrale Element der Multiplikation von ganzen Zahlen handelt.

\begin{align*} {[1]}_m \odot {[x]}_m &\overset{(1)}{=} {[1 \cdot x]}_m \\[0.5em] &\overset{(2)}{=} {[x]}_m \\[0.5em] &\overset{(3)}{=} {[x \cdot 1]}_m \\[0.5em] &\overset{(4)}{=} {[x]}_m \odot {[1]}_m \end{align*}

Inverse Elemente

Hauptartikel: Multiplikative Inverse von Restklassen

Ein Element \({[x]}_m \in \Z_m\) besitzt nur dann ein multiplikatives Inverses, wenn es sich bei \({[x]}_m\) um eine prime Restklasse modulo \(\mathbf{m}\) handelt, d. h., falls \(x\) und \(m\) teilerfremd sind; für den größten gemeinsamen Teiler von \(x\) und \(m\) gilt dann entsprechend \(\ggT(x,m)=1\). Das multiplikatives Inverses kann in diesem Fall mithilfe des erweiterten euklidischen Algorithmus ermittelt werden.