de
Seitenbanner
Menu
A-Z
Nachlesen

Modulare Subtraktion

Bei der modularen Subtraktion (auch Subtraktion modulo m) kann der Rest der Differenz zweier ganzer Zahlen bei Division durch $m$ alternativ über die kongruente Differenz 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 Subtraktion gilt die folgende Kongruenz:

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

In Worten lässt sich dies wie folgt ausdrücken: Der Rest der Differenz ist kongruent zur Differenz der Reste.

Beispiele

Beispiel 1

Es soll die Differenz $23 - 42 \bmod{5}$ berechnet werden. Für Minuend und Subtrahend gelten die folgenden Kongruenzen:

\begin{align*} \begin{alignedat}{2} 23 &\equiv 3 && \pmod{5} \\[0.5em] 42 &\equiv 2 && \pmod{5}. \end{alignedat} \end{align*}

Für die Differenz ergibt sich somit:

\[ \underbrace{23 - 42}_{=\ -19} \equiv 3 - 2 \equiv 1 \pmod{5}. \]

Beispiel 2

Es soll $4711 - 1337 \bmod{42}$ berechnet werden. Für Minuend und Subtrahend gelten die folgenden Kongruenzen:

\begin{align*} \begin{alignedat}{2} 4711 &\equiv 7 && \pmod{42} \\[0.5em] 1337 &\equiv 35 && \pmod{42}. \end{alignedat} \end{align*}

Für die Differenz ergibt sich somit:

\[ \underbrace{4711 - 1337}_{=\ 3374} \equiv \underbrace{7 - 35}_{=\ -28} \equiv 14 \pmod{42}. \]

Eigenschaften

Assoziativität

Die Subtraktion modulo $m$ ist im Allgemeinen nicht assoziativ, wie das folgende Beispiel zeigt:

\begin{align*} \begin{alignedat}{2} \bigl( 1 - 1 \bigr) - 1 = -1 &\equiv 2 && \pmod{3} \\[0.5em] 1 - \bigl( 1 - 1 \bigr) = 1 &\equiv 1 && \pmod{3}. \end{alignedat} \end{align*}

Kommutativität

Die Subtraktion modulo $m$ ist im Allgemeinen nicht kommutativ, wie das folgende Beispiel zeigt:

\begin{align*} \begin{alignedat}{2} 1 - 0 = 1 &\equiv 1 && \pmod{3} \\[0.5em] 0 - 1 = -1 &\equiv 2 && \pmod{3}. \end{alignedat} \end{align*}

Neutrales Element

Es existiert kein neutrales Element bzgl. der Subtraktion modulo $m$.

Inverses Element

Das inverse Element einer Zahl $a$ bezüglich der Subtraktion modulo $m$ existiert nicht. Das Verknüpfen eines Elements mit seinem Inversen muss stets das neutrale Element ergeben, welches für die Subtraktion aber nicht existiert.

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 die Differenz $a-b$ gilt folglich:

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