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

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