de
Seitenbanner
Menu
A-Z
Nachlesen

Modulare Addition

Bei der modularen Addition (auch Addition modulo m) kann der Rest der Summe zweier ganzer Zahlen bei Division durch $m$ alternativ über die kongruente Summe 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 Addition 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 Summe ist kongruent zur Summe der Reste.

Beispiele

Beispiel 1

Es soll die Summe $17 + 23 \bmod{7}$ berechnet werden. Für die Summanden gelten die folgenden Kongruenzen:

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

Für die Summe ergibt sich somit:

\[ \underbrace{17 + 23}_{=\ 40} \equiv 3 + 2 \equiv 5 \pmod{7}. \]

Beispiel 2

Es soll die Summe $123 + 521 + 923 \bmod{11}$ berechnet werden. Für die Summanden gelten die folgenden Kongruenzen:

\begin{align*} \begin{alignedat}{2} 123 &\equiv 2 && \pmod{11} \\[0.5em] 521 &\equiv 4 && \pmod{11} \\[0.5em] 923 &\equiv 10 && \pmod{11}. \end{alignedat} \end{align*}

Für die Summe ergibt sich somit:

\[ \underbrace{123 + 521 + 923}_{=\ 1567} \equiv \underbrace{2 + 4 + 10}_{=\ 16} \equiv 5 \pmod{11}. \]

Eigenschaften

Assoziativität

Die Addition modulo $m$ ist assoziativ:

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

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

Kommutativität

Die Addition modulo $m$ ist kommutativ:

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

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

Neutrales Element

Die $0$ ist das neutrale Element der Addition modulo $m$:

\[ a + 0 \equiv a \equiv 0 + a \pmod{m}. \]

Inverses Element

Das inverse Element einer Zahl $a$ bezüglich der Addition modulo $m$ ist $m-a$:

\[ a + (m-a) \equiv 0 \equiv (m-a) + a \pmod{m}. \]

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 Summe $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$