Nachlesen

Kongruenzrelation

Bei der Kongruenzrelation handelt es sich um eine Äquivalenzrelation auf der Menge der ganze Zahlen. Zwei Zahlen heißen kongruent modulo m, wenn sie bei Division durch den Modul m denselben ganzzahligen Rest lassen; andernfalls heißen sie inkongruent.

Definition

Gegeben seien zwei ganze Zahlen $a,b \in \Z$ sowie eine natürliche Zahl $m \in \N$. Man nennt $a$ und $b$ kongruent modulo m und schreibt $a \equiv b \pmod{m}$, falls $a$ und $b$ bei der Division durch den Modul $\mathbf{m}$ denselben ganzzahligen Rest lassen – dies ist genau dann der Fall, wenn es sich bei $m$ um einen Teiler der Differenz $a-b$ bzw. $b-a$ handelt. Andernfalls sind die Zahlen inkongruent modulo m und man schreibt $a \not\equiv b \pmod{m}$.

Mithilfe der Teilbarkeitsrelation kann dies wie folgt formuliert werden:

a \equiv b \pmod{m} \quad\Leftrightarrow\quad m \mid (a-b).

Es handelt sich bei der Kongruenzrelation $\equiv (\bmod{m})$ um eine Äquivalenzrelation – also um eine symmetrische, reflexive und transitive Relation.

Beispiele

Es gelten exemplarisch die folgenden Kongruenzen und Inkongruenzen:

Es gilt $12 \equiv 23 \pmod{11}$, da $11 \mid \underbrace{(23 - 12)}_{=\ 11}$ gilt.
Es gilt $123 \equiv 144 \pmod{7}$, da $7 \mid \underbrace{(144 - 123)}_{=\ 21}$ gilt.
Es gilt $25 \equiv -26 \pmod{17}$, da $17 \mid \underbrace{(25 - (-26))}_{=\ 51}$ gilt.
Es gilt $23 \not\equiv 42 \pmod{2}$, da $2 \nmid \underbrace{(42 - 23)}_{=\ 19}$ gilt.

Jetzt üben!

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

Restklassen

Hauptartikel: Restklasse

Betrachtet man einen bestimmten Modul $m$, so wird die Menge $\Z$ der ganzen Zahlen durch die Kongruenzrelation $\equiv$ in genau $m$ disjunkte Teilmengen, die Restklassen, aufgeteilt; alle Elemente innerhalb einer Restklasse besitzen dabei stets denselben Rest bei Division durch $m$.

Bei den Restklassen handelt es sich um die Äquivalenzklassen der Kongruenzrelation. Die Menge aller Restklassen modulo $m$ bildet den Restklassenring $\Z_m = \Z/m\Z$.

Rechenregeln

Für alle $a,b,c,d \in \Z$ und $m \in \N$ gelten die folgenden Rechenregeln:

(I)	$a \equiv a \pmod{m}$
(II)	$a \equiv b \pmod{m} \Leftrightarrow b \equiv a \pmod{m}$
(III)	$a \equiv b \pmod{m} \wedge b \equiv c \pmod {m} \Rightarrow a \equiv c \pmod{m}$
(IV)	$a_1 \equiv b_1 \pmod{m} \wedge a_2 \equiv b_2 \pmod{m} \Rightarrow a_1+a_2 \equiv b_1+b_2 \pmod{m}$
(V)	$a_1 \equiv b_1 \pmod{m} \wedge a_2 \equiv b_2 \pmod{m} \Rightarrow a_1-a_2 \equiv b_1-b_2 \pmod{m}$
(VI)	$a_1 \equiv b_1 \pmod{m} \wedge a_2 \equiv b_2 \pmod{m} \Rightarrow a_1 \cdot a_2 \equiv b_1 \cdot b_2 \pmod{m}$
(VII)	$a \equiv b \pmod{m} \Leftrightarrow -a \equiv -b \pmod{m}$
(VIII)	Gilt $\ggT(c,m)=1$, so folgt aus $c \cdot a \equiv c \cdot b \pmod{m}$ die Kongruenz $a \equiv b \pmod{m}$.

Beweis

Um zu beweisen, dass $a \equiv b \pmod{m}$ genau dann gilt, wenn $m \mid (a-b)$ gilt, sind zwei Aussagen zu zeigen:

\begin{align*} \text{(I)} &\quad a \equiv b \pmod{m} \Rightarrow m \mid \bigl( a-b \bigr) \\[0.5em] \text{(II)} &\quad a \equiv b \pmod{m} \Leftarrow m \mid \bigl( a-b \bigr). \end{align*}

Beweis von (I)

Es sei $a \equiv b \pmod{m}$. Dann existieren für $a$ und $b$ die folgenden Zerlegungen mit Rest (mit $q_a,q_b,r \in \Z$ und $0 \leq r \lt m$):

\begin{align*} a &= q_a \cdot m + r \\[0.5em] b &= q_b \cdot m + r \end{align*}

Für die Differenz $a-b$ ergibt sich somit:

\begin{align*} a-b &= \bigl( q_a \cdot m + r \bigr) - \bigl( q_b \cdot m + r \bigr) \\[0.5em] &= q_a \cdot m - q_b \cdot m + r -r \\[0.5em] &= \bigl( q_a - q_b \bigr) \cdot m \end{align*}

Hieraus folgt direkt, dass $m \mid (a-b)$ gilt.

Beweis von (II)

Es sei $m \mid (a-b)$. Für $a$ und $b$ existieren die folgenden Zerlegungen mit Rest (mit $q_a,q_b,r_a,r_b \in \Z$ und $0 \leq r_a \lt m$ sowie $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$ ergibt sich somit:

\begin{align*} a-b &= \bigl( q_a \cdot m + r_a \bigr) - \bigl( q_b \cdot m + r_b \bigr) \\[0.5em] &= \underbrace{\bigl( q_a - q_b \bigr) \cdot m}_{\equiv 0 \pmod{m}} + \bigl( r_a - r_b \bigr) \\[0.5em] &\equiv r_a - r_b \pmod{m} \end{align*}

Wegen $m \mid (a-b)$ muss also $m \mid (r_a-r_b)$ gelten. Aufgrund der Voraussetzungen $0 \leq r_a \lt m$ und $0 \leq b \lt m$ gilt

-m \lt r_a - r_b \lt m.

Das einzige ganzzahlige Vielfache von $m$ im Intervall $(-m,m)$ ist $0$ – dies entspricht dem Fall $r_a=r_b$, woraus direkt $a \equiv b \pmod{m}$ folgt.