de
Seitenbanner
Menu
A-Z
Nachlesen

Modulare Multiplikation

Bei der modularen Multiplikation (auch Multiplikation modulo m) kann der Rest des Produkts zweier ganzer Zahlen bei Division durch $m$ alternativ über das kongruente Produkt der Reste der beiden Zahlen bestimmt werden.

Definition

Gegeben seien zwei ganze Zahlen $a,b \in \Z$ sowie eine natürliche Zahl $m \in \N$. Mit $r_a$ und $r_b$ seien die ganzzahligen Reste der Division von $a$ bzw. $b$ durch $m$ bezeichnet. Für die modulare Multiplikation gilt die folgende Kongruenz:

\[ a \cdot b \equiv r_a \cdot r_b \pmod{m}. \]

In Worten lässt sich dies wie folgt ausdrücken: Der Rest des Produkts ist kongruent zum Produkt der Reste.

Beispiele

Beispiel 1

Es soll das Produkt $47 \cdot 73 \bmod{15}$ berechnet werden. Für die Faktoren gelten die folgenden Kongruenzen:

\begin{align*} \begin{alignedat}{2} 47 &\equiv 2 && \pmod{15} \\[0.5em] 73 &\equiv 13 && \pmod{15}. \end{alignedat} \end{align*}

Für das Produkt ergibt sich somit:

\[ \underbrace{47 \cdot 73}_{=\ 3431} \equiv \underbrace{2 \cdot 13}_{=\ 26} \equiv 11 \pmod{15}. \]

Beispiel 2

Es soll das Produkt $235 \cdot 47 \cdot 1386 \bmod{23}$ berechnet werden. Für die Faktoren gelten die folgenden Kongruenzen:

\begin{align*} \begin{alignedat}{2} 235 &\equiv 5 && \pmod{23} \\[0.5em] 47 &\equiv 1 && \pmod{23} \\[0.5em] 1386 &\equiv 6 && \pmod{23}. \end{alignedat} \end{align*}

Für das Produkt ergibt sich somit:

\[ \underbrace{235 \cdot 47 \cdot 1386}_{=\ 15\,308\,370} \equiv \underbrace{5 \cdot 1 \cdot 6}_{=\ 30} \equiv 7 \pmod{23}. \]

Eigenschaften

Assoziativität

Die Multiplikation modulo $m$ ist assoziativ:

\[ \bigl( a \cdot b \bigr) \cdot c \equiv a \cdot \bigl( b \cdot c \bigr) \equiv a \cdot b \cdot c \pmod{m}. \]

Dies folgt direkt aus der Assoziativität der Multiplikation von ganzen Zahlen.

Kommutativität

Die Multiplikation modulo $m$ ist kommutativ:

\begin{align*} a \cdot b \equiv b \cdot a \pmod{m}. \end{align*}

Dies folgt direkt aus der Kommutativität der Multiplikation von ganzen Zahlen.

Neutrales Element

Die $1$ ist das neutrale Element der Multiplikation modulo $m$:

\[ a \cdot 1 \equiv a \equiv 1 \cdot a \pmod{m}. \]

Inverses Element

Das inverse Element einer Zahl $a$ bezüglich der Multiplikation modulo $m$ existiert im Allgemeinen nicht; beispielsweise besitzt die $2$ kein Inverses bezüglich der Multiplikation modulo $4$:

\begin{align*} 2 \cdot 0 &\equiv 0 \pmod{4} \\[0.5em] 2 \cdot 1 &\equiv 2 \pmod{4} \\[0.5em] 2 \cdot 2 &\equiv 0 \pmod{4} \\[0.5em] 2 \cdot 3 &\equiv 2 \pmod{4}. \end{align*}

Ist der größte gemeinsame Teiler $\ggT(a,m)$ der Zahlen $a$ und $m$ gleich Eins (d. h. die Zahlen $a$ und $m$ sind teilerfremd), so existiert das multiplikative Inverse modulo $m$, und kann beispielsweise mithilfe des erweiterten euklidischen Algorithmus berechnet werden. Dies ist insbesondere der Fall, falls es sich beim Modul $m$ um eine Primzahl $p$ handelt und der zu invertierende Wert $a$ kein Vielfaches der Primzahl $p$ ist.

Beweis

Gegeben seien zwei ganze Zahlen $a,b \in \Z$ sowie eine natürliche Zahl $m \in \N$. Für $a$ und $b$ existieren die folgenden Zerlegungen mit Rest (mit $q_a,q_b,r_a,r_b \in \Z$ sowie $0 \leq r_a \lt m$ und $0 \leq r_b \lt m$):

\begin{align*} a &= q_a \cdot m + r_a \\[0.5em] b &= q_b \cdot m + r_b. \end{align*}

Für das Produkt $a \cdot b$ gilt folglich:

\begin{align*} a \cdot b &\overset{(1)}{=} \bigl( q_a \cdot m + r_a \bigr) \cdot \bigl( q_b \cdot m + r_b \bigr) \\[0.5em] &\overset{(2)}{=} q_a \cdot m \cdot q_b \cdot m + q_a \cdot m \cdot r_b + r_a \cdot q_b \cdot m + r_a \cdot r_b \\[0.5em] &\overset{(3)}{=} \underbrace{\bigl( q_a \cdot q_b \cdot m + q_a \cdot r_b + q_b \cdot r_a \bigr) \cdot m}_{\equiv\ 0 \pmod{m}} + \bigl( r_a \cdot r_b \bigr) \\[0.5em] &\overset{(4)}{\equiv} r_a \cdot r_b \pmod{m}. \end{align*}
Erklärungen zu den Schritten
(1)
  • Ersetzen von $a$ und $b$ durch die Zerlegungen mit Rest
(2)
  • Ausmultiplizieren mithilfe des allgemeinen Distributivgesetzes
(3)
(4)
  • Die Darstellung in (3) entspricht einer Zerlegung mit Rest für den Term $a \cdot b$ mit dem Rest $r_a \cdot r_b$