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.

Inhalt

Definition
Beispiele
Eigenschaften
Beweis

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}.

Jetzt üben!

Nutze den individuell konfigurierbaren Aufgabengenerator, um unbegrenzt Aufgaben zum Thema Modulare Multiplikation zu erzeugen und zu üben.

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)	$m$ ausklammern und zusammenfassen mithilfe der Assoziativ-, Kommutativ- und Distributivgesetze für ganze Zahlen
(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$

Erklärungen zu den Schritten
(1)	Ersetzen von \(a\) und \(b\) durch die Zerlegungen mit Rest
(2)	Ausmultiplizieren mithilfe des allgemeinen Distributivgesetzes
(3)	\(m\) ausklammern und zusammenfassen mithilfe der Assoziativ-, Kommutativ- und Distributivgesetze für ganze Zahlen
(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\)