Rechnen mit Kongruenzen

Studium

a \equiv a',\ b \equiv b' \!\!\pmod m \;\Rightarrow\; a \pm b \equiv a' \pm b',\ \ a \cdot b \equiv a' \cdot b' \!\!\pmod m

Voraussetzung: $a, a', b, b' \in \mathbb{Z},$ $m \in \mathbb{N},$ $m \geq 2$

$a, b$: ganze Zahlen
$a', b'$: ganze Zahlen mit demselben Rest modulo m wie a bzw. b
$m$: Modul, die natürliche Zahl, durch die geteilt wird
$a \equiv b \pmod m$: a ist kongruent zu b modulo m, das heißt m teilt a − b

Summen, Differenzen, Produkte und Potenzen darf man modulo m mit beliebigen Vertretern gleichen Rests ausrechnen.

Erklärung

Zwei ganze Zahlen heißen kongruent modulo $m$ , geschrieben $a \equiv b \pmod m$ , wenn $m$ die Differenz $a - b$ teilt. Gleichwertig: $a$ und $b$ lassen bei Division durch $m$ denselben Rest. Die Zahlen mit gleichem Rest bilden eine Restklasse.

Die Kongruenz verträgt sich mit Addition, Subtraktion und Multiplikation: Man darf jede Zahl durch einen Vertreter mit gleichem Rest ersetzen, ohne dass sich das Ergebnis modulo $m$ ändert. Daraus folgt auch $a^k \equiv a'^k \pmod m$ für jedes $k \in \mathbb{N}$ . In der Praxis reduziert man deshalb nach jedem Rechenschritt, damit die Zahlen klein bleiben.

Division ist nur eingeschränkt erlaubt: Aus $c \cdot a \equiv c \cdot b \pmod m$ folgt $a \equiv b \pmod m$ nur, wenn $\operatorname{ggT}(c, m) = 1$ . Dann gibt es ein Inverses von $c$ modulo $m$ , mit dem man multiplizieren kann.

Beispiele

Neunerprobe: Ist $123 \cdot 456$ durch $9$ teilbar? Es gilt $123 \equiv 6$ und $456 \equiv 6 \pmod 9$ , also

123 \cdot 456 \equiv 6 \cdot 6 = 36 \equiv 0 \pmod 9

Tatsächlich ist $123 \cdot 456 = 56\,088$ , und die Quersumme $27$ ist durch $9$ teilbar.

Letzte Ziffer von $7^{100}$ : Gesucht ist der Rest modulo $10$ . Wegen $7^4 = 2401 \equiv 1 \pmod{10}$ gilt

7^{100} = \left(7^4\right)^{25} \equiv 1^{25} = 1 \pmod{10}

Die letzte Ziffer ist $1$ .

Typische Fehler

Unerlaubt kürzen. $2 \cdot 3 \equiv 2 \cdot 8 \pmod{10}$ , denn $6$ und $16$ haben beide den Rest $6$ . Trotzdem ist $3 \not\equiv 8 \pmod{10}$ , weil $8 - 3 = 5$ nicht durch $10$ teilbar ist. Kürzen durch $2$ ist hier verboten, da $\operatorname{ggT}(2, 10) = 2$ .
Im Exponenten modulo $m$ reduzieren. Es ist $3^{10} = 59\,049 \equiv 9 \pmod{10}$ . Wer den Exponenten durch $10 \bmod 10 = 0$ ersetzt, erhält fälschlich $3^0 = 1$ . Exponenten darf man nur modulo einer Periode reduzieren, etwa modulo $\varphi(m)$ , falls $\operatorname{ggT}(a, m) = 1$ (Satz von Euler): $\varphi(10) = 4$ und $3^{10 \bmod 4} = 3^2 = 9$ .
Negative Zahlen falsch reduzieren. $-3 \equiv 7 \pmod{10}$ , nicht $3$ . Der Rest liegt immer zwischen $0$ und $m - 1$ .

Rechnen mit Kongruenzen