de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Zahlentheorie
  • Modulare Arithmetik
  • Operationen
  • Modulare Subtraktion
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.

Inhalt

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\)