Modulare Arithmetik: Rechnen mit Resten, Kongruenz, mod

Die modulare Arithmetik ist das Rechnen mit Resten. Du kennst sie von der Uhr: Fünf Stunden nach 9 Uhr ist es nicht 14 Uhr, sondern 2 Uhr. Auf dem Zifferblatt zählt nur der Rest, der beim Teilen durch 12 übrig bleibt. Man sagt: Du rechnest modulo 12. Die Zahl 12 heißt dabei Modul.

Dieselbe Idee steckt in den Wochentagen (modulo 7), in Teilbarkeitsregeln, in den Prüfziffern auf Büchern und Kontonummern und in der Verschlüsselung. Du brauchst nur die Division mit Rest und den größten gemeinsamen Teiler.

Division mit Rest

Teilst du a durch m, passt m eine ganze Zahl q mal in a, und es bleibt ein Rest r übrig, der kleiner als m ist. Das schreibst du als $a = q \cdot m + r$ mit $0 \leq r < m$ . Den Rest bezeichnet man mit $a mod m$ („a modulo m“).

Beispiele zur Division mit Rest
a	m	Zerlegung	Rest
47	5	$47 = 9 \cdot 5 + 2$	2
123	7	$123 = 17 \cdot 7 + 4$	4
−7	5	$- 7 = (- 2) \cdot 5 + 3$	3

Der Rest ist nie negativ. Bei $- 7$ geht man deshalb nicht bis $- 5$ hoch, sondern bis $- 10$ hinunter und hat dann den Rest 3.

Uhrenrechnen

Auf dem Zifferblatt kehrt man nach 12 Stunden zum Anfang zurück. Rechnest du Stunden, behältst du nur den Rest nach dem Teilen durch 12 (die 12 selbst steht dabei für den Rest 0).

Uhrenrechnen: 5 Stunden nach 9 Uhr ist es 2 Uhr. Man rechnet 9 + 5 = 14 und behält nur den Rest bei der Division durch 12. Das schreibt man 14 ≡ 2 (mod 12).

Mit 24-Stunden-Uhr rechnest du modulo 24, bei Wochentagen modulo 7. Wenn heute Mittwoch ist, welcher Tag ist in 100 Tagen? Es ist $100 = 14 \cdot 7 + 2$ , also bleibt der Rest 2: Es ist Freitag.

Kongruenz

Zwei Zahlen, die bei der Division durch m denselben Rest lassen, heißen kongruent modulo m. Diese Schreibweise führte Carl Friedrich Gauß 1801 ein (Disquisitiones Arithmeticae).

Rechenregeln

Das Wichtigste an der Kongruenz: Du darfst Zahlen durch kongruente Zahlen ersetzen. Sind $a \equiv a'$ und $b \equiv b' (\mod m)$ , dann gilt auch

a + b \equiv a' + b' a - b \equiv a' - b' a \cdot b \equiv a' \cdot b' a^{k} \equiv a'^{k} (\mod m)

Das spart viel Rechenarbeit, denn du rechnest nur mit den kleinen Resten.

Beim Teilen musst du aufpassen. Aus $a \cdot c \equiv b \cdot c$ darfst du nicht einfach $a \equiv b$ folgern. Es ist $4 \cdot 2 = 8$ und $4 \cdot 5 = 20$ , und beide haben modulo 12 den Rest 8. Aber 2 und 5 sind modulo 12 nicht kongruent. Kürzen geht nur, wenn c und m teilerfremd sind. Das behandelt der Abschnitt über modulare Inverse.

Restklassen

Alle Zahlen mit demselben Rest bilden eine Restklasse. Modulo 5 gibt es fünf: die Zahlen mit Rest 0 (…, −5, 0, 5, 10, …), mit Rest 1 (…, −4, 1, 6, 11, …) und so weiter. Man rechnet mit Vertretern aus ${0, 1, \dots, m - 1}$ . Die folgende Tabelle zeigt die Multiplikation modulo 7.

Multiplikation modulo 7
·	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

In jeder Zeile steht die 1 genau einmal. Das heißt: Zu jeder Zahl von 1 bis 6 gibt es eine Zahl, mit der sie multipliziert den Rest 1 ergibt. Zum Beispiel ist $3 \cdot 5 = 15 \equiv 1 (\mod 7)$ . Man nennt 5 das Inverse von 3 modulo 7. Das klappt bei 7, weil 7 eine Primzahl ist.

Teilbarkeitsregeln begründen

Die Regeln aus der Schule folgen aus der Kongruenz. Eine Zahl wie 4872 ist $4 \cdot 10^{3} + 8 \cdot 10^{2} + 7 \cdot 10 + 2$ . Modulo 9 ist $10 \equiv 1$ , also auch $10^{2} \equiv 1$ und $10^{3} \equiv 1$ . Damit ist

4872 \equiv 4 \cdot 1 + 8 \cdot 1 + 7 \cdot 1 + 2 = 21 (\mod 9)

Jede Zahl ist modulo 9 kongruent zu ihrer Quersumme. Weil 3 ein Teiler von 9 ist, gilt dasselbe modulo 3. Modulo 11 ist $10 \equiv - 1$ . Dann wechseln die Vorzeichen: Jede Zahl ist kongruent zu ihrer alternierenden Quersumme.

Teilbarkeitsregeln und ihr Grund
Teiler	Regel	Grund
2, 5, 10	letzte Ziffer	$10 \equiv 0 (\mod 2)$ , $(\mod 5)$ , $(\mod 10)$
4	letzte zwei Ziffern	$100 \equiv 0 (\mod 4)$
3, 9	Quersumme	$10 \equiv 1 (\mod 9)$
11	alternierende Quersumme	$10 \equiv - 1 (\mod 11)$

Prüfziffern

Eine Prüfziffer ist eine Ziffer, die aus den anderen berechnet wird. Tippst du dich einmal, stimmt die Rechnung nicht mehr, und der Fehler fällt auf. Dahinter steckt modulare Arithmetik.

ISBN-13

Bei der ISBN-13 (und der Strichcode-Nummer EAN-13) multiplizierst du die Ziffern abwechselnd mit 1 und 3, addierst und rechnest modulo 10. Das Ergebnis muss 0 sein. Die letzte Ziffer ist die Prüfziffer.

Warum 1 und 3 abwechselnd? Vertauscht du zwei benachbarte Ziffern a und b, ändert sich die Summe um $2 (b - a)$ . Das fällt auf, es sei denn, a und b unterscheiden sich um 5 (zum Beispiel 2 und 7). Dann ist die Änderung durch 10 teilbar.

IBAN

Die IBAN, die internationale Kontonummer, benutzt Prüfziffern modulo 97. So prüfst du sie: Stelle die ersten vier Zeichen ans Ende, ersetze Buchstaben durch Zahlen (A = 10, B = 11, bis Z = 35) und rechne die entstehende lange Zahl modulo 97. Für eine gültige IBAN muss der Rest 1 sein.

Modulare Inverse und Teilen

Das Inverse von a modulo m ist eine Zahl x mit $a \cdot x \equiv 1 (\mod m)$ . Es gibt es genau dann, wenn a und m teilerfremd sind, also $ggT (a, m) = 1$ . Mit dem Inversen kannst du „teilen“: Aus $a \cdot x \equiv b$ folgt durch Multiplikation mit dem Inversen von a die Lösung.

Gefunden wird das Inverse mit dem erweiterten euklidischen Algorithmus (Euklidischer Algorithmus). Er rechnet den ggT aus und liefert dazu Zahlen x und y mit $a \cdot x + m \cdot y = 1$ . Modulo m ist dann $a \cdot x \equiv 1$ .

Der kleine Satz von Fermat

Die Potenzen einer Zahl wiederholen sich modulo einer Primzahl nach spätestens $p - 1$ Schritten. Das beschrieb Pierre de Fermat um 1640 (Kleiner fermatscher Satz).

Leonhard Euler verallgemeinerte den Satz 1763 auf beliebige Moduln (Eulers Zahlentheorie). Das ist die Grundlage der Verschlüsselung RSA, die Reste großer Potenzen nutzt. Wie das mit kleinen Zahlen aussieht, zeigt der Magazinbeitrag Primzahlen und Verschlüsselung.

Der chinesische Restsatz

Was tust du, wenn eine Zahl gleichzeitig mehrere Reste vorgibt? Im chinesischen Buch Sunzi Suanjing steht eine Aufgabe, die man so formulieren kann: Eine Zahl lässt beim Teilen durch 3 den Rest 2, durch 5 den Rest 3 und durch 7 den Rest 2. Welche Zahl ist es? (Sunzis Restaufgabe.)

Typische Fehler

Übungen

Mehr Aufgaben findest du unter Modulo-Rechnung: Aufgaben. Zum Nachrechnen eignen sich der Modulo-Rechner und der ggT-kgV-Rechner.

Geschichte: von Sunzi bis Gauß

Die älteste Aufgabe dieser Art steht im Sunzi Suanjing, einem chinesischen Rechenbuch, das vermutlich im 3. Jahrhundert entstand. Es fragt nach der Zahl mit den Resten 2, 3 und 2. Im Jahr 1247 verallgemeinerte Qin Jiushao das Verfahren in seiner Mathematischen Abhandlung in neun Kapiteln. Der „chinesische Restsatz“ trägt deshalb seinen Namen.

In Europa dachten Pierre de Fermat und Leonhard Euler über Reste nach. Eine eigene Schreibweise und Theorie schuf der junge Carl Friedrich Gauß: In seinen Disquisitiones Arithmeticae von 1801 führte er das Kongruenzzeichen ≡ ein und machte aus der Zahlentheorie eine geordnete Wissenschaft. Heute steckt die Idee in jedem Computer und in jeder verschlüsselten Nachricht.

Häufige Fragen

Was bedeutet „mod“?

Es steht für „modulo“, lateinisch „mit dem Maß“. Man schreibt $a mod m$ für den Rest und $a \equiv b (\mod m)$ für „a und b haben denselben Rest“.

Wozu braucht man modulare Arithmetik im Alltag?

Bei Uhrzeiten, Wochentagen und Kalendern, bei Prüfziffern auf Büchern, Produkten und Kontonummern und bei der Verschlüsselung im Internet. Auch Zufallszahlengeneratoren und Hashfunktionen in Computern nutzen sie.

Warum nimmt man bei Verschlüsselung große Primzahlen?

Mit Primzahlen als Modul funktioniert das Teilen und der Satz von Fermat, und große Zahlen in Primfaktoren zu zerlegen ist sehr aufwendig. Das nutzt RSA aus, siehe den Magazinbeitrag.

Quellen und weiterführende Literatur

Wikipedia: Modulare Arithmetik
Wikipedia: Chinesischer Restsatz
Wikipedia: Internationale Bankkontonummer
Wikipedia: ISBN (englisch)
Carl Friedrich Gauß: Disquisitiones Arithmeticae, Leipzig 1801.