Modulo, Kongruenzen und der euklidische Algorithmus
Wenn es jetzt 22 Uhr ist, wie spät ist es in 5 Stunden? Natürlich 3 Uhr – und nicht 27 Uhr. Bei der Uhr, bei Wochentagen, bei Prüfziffern und in der Verschlüsselung rechnet man nur mit Resten. Dieses „Rechnen modulo m“ ist ein Grundbaustein der Zahlentheorie und der Informatik.
Division mit Rest und „mod“
Zu jeder ganzen Zahl $a$ und jeder natürlichen Zahl $m \geq 1$ gibt es genau eine Zerlegung
$q$ ist der (ganzzahlige) Quotient, $r$ der Rest. Man schreibt $r = a \bmod m$ und spricht „a modulo m“. Die Zahl $m$ heißt Modul.
Beispiele
- $17 = 3 \cdot 5 + 2$, also $17 \bmod 5 = 2$.
- $40 = 8 \cdot 5 + 0$, also $40 \bmod 5 = 0$ – genau dann ist $a$ durch $m$ teilbar.
- $27 \bmod 24 = 3$: 27 Uhr ist 3 Uhr am nächsten Tag.
- Negative Zahlen: $-17 = (-4) \cdot 5 + 3$, also $-17 \bmod 5 = 3$. Der Rest liegt immer zwischen $0$ und $m - 1$, deshalb geht man hier bis $-20$ hinunter und dann $3$ wieder hinauf.
Achtung beim Programmieren
In vielen Programmiersprachen (C, Java, JavaScript) liefert -17 % 5 den Wert $-2$, weil dort Richtung 0 gerundet wird. In der Mathematik (und in Python) ist $-17 \bmod 5 = 3$. Beide Ergebnisse unterscheiden sich genau um $m$.
Kongruenzen
Zwei ganze Zahlen heißen kongruent modulo m, wenn sie bei Division durch $m$ denselben Rest lassen. Gleichwertig: Ihre Differenz ist durch $m$ teilbar.
Zum Beispiel ist $38 \equiv 3 \ (\text{mod } 7)$, denn $38 - 3 = 35 = 5 \cdot 7$. Und $-1 \equiv 6 \ (\text{mod } 7)$. Alle Zahlen mit demselben Rest bilden eine Restklasse; modulo 7 gibt es die sieben Restklassen $0, 1, \ldots, 6$.
Rechenregeln
Gilt $a \equiv a'$ und $b \equiv b' \ (\text{mod } m)$, dann auch
$a + b \equiv a' + b', \qquad a - b \equiv a' - b', \qquad a \cdot b \equiv a' \cdot b', \qquad a^k \equiv a'^k \ (\text{mod } m).$
Du darfst also jederzeit zwischendurch reduzieren – das hält die Zahlen klein. Teilen ist dagegen nicht ohne Weiteres erlaubt (siehe unten).
Beispiel: Welcher Wochentag?
Heute ist Freitag. Welcher Wochentag ist in 100 Tagen? Wochentage wiederholen sich alle 7 Tage: $100 = 14 \cdot 7 + 2$, also $100 \equiv 2 \ (\text{mod } 7)$. In 100 Tagen ist derselbe Wochentag wie in 2 Tagen: Sonntag.
Beispiel: Rest eines Produkts
Welchen Rest lässt $123 \cdot 456$ bei Division durch 7? Statt erst zu multiplizieren, reduzierst Du zuerst: $123 = 17 \cdot 7 + 4$, also $123 \equiv 4$, und $456 = 65 \cdot 7 + 1$, also $456 \equiv 1$. Damit ist $123 \cdot 456 \equiv 4 \cdot 1 = 4 \ (\text{mod } 7)$.
Der euklidische Algorithmus
Der größte gemeinsame Teiler zweier Zahlen lässt sich ohne Primfaktorzerlegung bestimmen – auch für sehr große Zahlen. Die Idee: Ein gemeinsamer Teiler von $a$ und $b$ teilt auch den Rest $a \bmod b$. Also ist $\operatorname{ggT}(a, b) = \operatorname{ggT}(b,\ a \bmod b)$.
- Teile die größere Zahl durch die kleinere mit Rest.
- Ersetze die größere Zahl durch die kleinere und die kleinere durch den Rest.
- Wiederhole, bis der Rest 0 ist. Der letzte Rest ungleich 0 ist der ggT.
Beispiel: $\operatorname{ggT}(252, 198)$
$252 = 1 \cdot 198 + 54$
$198 = 3 \cdot 54 + 36$
$54 = 1 \cdot 36 + 18$
$36 = 2 \cdot 18 + 0$
Der letzte Rest ungleich 0 ist 18, also $\operatorname{ggT}(252, 198) = 18$. Daraus folgt auch $\operatorname{kgV}(252, 198) = \frac{252 \cdot 198}{18} = 2772$.
Erweiterter euklidischer Algorithmus und Lemma von Bézout
Der ggT lässt sich immer als ganzzahlige Kombination der beiden Zahlen schreiben (Lemma von Bézout):
Die Zahlen $s$ und $t$ findest Du, indem Du die Gleichungen von unten nach oben einsetzt – oder übersichtlicher mit einer Tabelle, in der zu jedem Rest $r_k$ zwei Zahlen $s_k, t_k$ mit $r_k = s_k \cdot a + t_k \cdot b$ mitlaufen. Start sind die Zeilen $(a;\ 1;\ 0)$ und $(b;\ 0;\ 1)$, danach gilt jeweils: neue Zeile = vorletzte Zeile − q · letzte Zeile.
Beispiel: $a = 252$, $b = 198$
| $k$ | Rest $r_k$ | Quotient $q_k$ | $s_k$ | $t_k$ |
|---|---|---|---|---|
| 0 | 252 | 1 | 0 | |
| 1 | 198 | 1 | 0 | 1 |
| 2 | 54 | 3 | 1 | -1 |
| 3 | 36 | 1 | -3 | 4 |
| 4 | 18 | 2 | 4 | -5 |
| 5 | 0 | -11 | 14 |
In der markierten Zeile steht der ggT 18 mit $s = 4$ und $t = -5$: $\ 18 = 4 \cdot 252 + (-5) \cdot 198 = 1008 - 990$. ✓
Rückwärts eingesetzt ergibt sich dasselbe: $18 = 54 - 36 = 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198 = 4 \cdot (252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198$.
Das modulare Inverse
Eine Zahl $x$ heißt Inverses von $a$ modulo $m$, wenn $a \cdot x \equiv 1 \ (\text{mod } m)$ gilt. Man schreibt $x = a^{-1} \bmod m$. Ein Inverses gibt es genau dann, wenn $\operatorname{ggT}(a, m) = 1$ ist. Gefunden wird es mit dem erweiterten euklidischen Algorithmus: Aus $1 = s \cdot m + t \cdot a$ folgt $t \cdot a \equiv 1 \ (\text{mod } m)$.
Beispiel: Inverses von 7 modulo 26
| $k$ | Rest $r_k$ | Quotient $q_k$ | $s_k$ | $t_k$ |
|---|---|---|---|---|
| 0 | 26 | 1 | 0 | |
| 1 | 7 | 3 | 0 | 1 |
| 2 | 5 | 1 | 1 | -3 |
| 3 | 2 | 2 | -1 | 4 |
| 4 | 1 | 2 | 3 | -11 |
| 5 | 0 | -7 | 26 |
$1 = 3 \cdot 26 + (-11) \cdot 7$, also $7 \cdot (-11) \equiv 1 \ (\text{mod } 26)$. In den Bereich 0 … 25 gebracht: $-11 + 26 = 15$. Probe: $7 \cdot 15 = 105 = 4 \cdot 26 + 1$. ✓
Ist $m$ eine Primzahl, hat jede Zahl, die kein Vielfaches von $m$ ist, ein Inverses. Modulo 10 dagegen haben 2, 4, 5, 6 und 8 keines.
Lineare Kongruenzen lösen
Gesucht sind alle $x$ mit $a \cdot x \equiv b \ (\text{mod } m)$. Sei $d = \operatorname{ggT}(a, m)$.
- Ist $d$ kein Teiler von $b$, gibt es keine Lösung.
- Ist $d = 1$, gibt es genau eine Lösung zwischen 0 und $m - 1$: $x \equiv a^{-1} \cdot b$.
- Ist $d > 1$ ein Teiler von $b$, teilst Du $a$, $b$ und $m$ durch $d$, löst die kleinere Kongruenz und erhältst $d$ Lösungen zwischen 0 und $m - 1$.
Beispiel 1: $7x \equiv 3 \ (\text{mod } 26)$
$\operatorname{ggT}(7, 26) = 1$, das Inverse von 7 ist 15 (siehe oben). Also $x \equiv 15 \cdot 3 = 45 \equiv 19 \ (\text{mod } 26)$. Probe: $7 \cdot 19 = 133 = 5 \cdot 26 + 3$. ✓
Beispiel 2: $4x \equiv 6 \ (\text{mod } 10)$
$d = \operatorname{ggT}(4, 10) = 2$ teilt 6. Durch 2 teilen: $2x \equiv 3 \ (\text{mod } 5)$. Das Inverse von 2 modulo 5 ist 3 (denn $2 \cdot 3 = 6 \equiv 1$), also $x \equiv 3 \cdot 3 = 9 \equiv 4 \ (\text{mod } 5)$. Zwischen 0 und 9 sind das die zwei Lösungen $x = 4$ und $x = 9$. Probe: $4 \cdot 4 = 16 \equiv 6$ und $4 \cdot 9 = 36 \equiv 6 \ (\text{mod } 10)$. ✓
Die Kongruenz $4x \equiv 5 \ (\text{mod } 10)$ hätte dagegen keine Lösung: $4x$ ist immer gerade, $4x - 5$ also nie durch 10 teilbar.
Achtung: Kürzen in Kongruenzen
Aus $2 \cdot 3 \equiv 2 \cdot 8 \ (\text{mod } 10)$ folgt nicht $3 \equiv 8 \ (\text{mod } 10)$. Durch eine Zahl $c$ darfst Du nur teilen, wenn $\operatorname{ggT}(c, m) = 1$ ist – oder Du teilst den Modul mit (wie in Beispiel 2).
Große Potenzen und der kleine Satz von Fermat
Für eine Primzahl $p$ und eine Zahl $a$, die nicht durch $p$ teilbar ist, gilt der kleine Satz von Fermat:
Damit darfst Du den Exponenten modulo $p - 1$ verkleinern.
Beispiel: $3^{100} \bmod 7$
7 ist eine Primzahl, also $3^6 \equiv 1 \ (\text{mod } 7)$. Wegen $100 = 16 \cdot 6 + 4$ gilt $3^{100} = (3^6)^{16} \cdot 3^4 \equiv 1^{16} \cdot 81 \ (\text{mod } 7)$. Und $81 = 11 \cdot 7 + 4$, also $3^{100} \equiv 4 \ (\text{mod } 7)$.
Ohne Primzahl-Modul hilft wiederholtes Quadrieren: $a^2, a^4, a^8, \ldots$ jeweils sofort reduzieren und die passenden Potenzen multiplizieren. Für die letzte Ziffer einer Zahl rechnest Du modulo 10, für die letzten zwei Ziffern modulo 100. Der Modulo-Rechner zeigt Dir das Schritt für Schritt.
Mehrere Kongruenzen: der chinesische Restsatz
Gesucht ist eine Zahl, die bei Division durch 3 den Rest 2, durch 5 den Rest 3 und durch 7 den Rest 2 lässt. Sind die Moduln – wie hier – paarweise teilerfremd, gibt es nach dem chinesischen Restsatz genau eine Lösung zwischen 0 und dem Produkt der Moduln minus 1, hier zwischen 0 und 104.
Beispiel: $x \equiv 2 \ (\text{mod } 3)$, $x \equiv 3 \ (\text{mod } 5)$, $x \equiv 2 \ (\text{mod } 7)$
Aus der ersten Kongruenz folgt $x = 2 + 3t$, also $x \in \{2, 5, 8, \ldots\}$. Davon erfüllt 8 auch die zweite: $x \equiv 8 \ (\text{mod } 15)$, also $x \in \{8, 23, 38, \ldots\}$. Und $23 = 3 \cdot 7 + 2$ erfüllt die dritte. Ergebnis: $x \equiv 23 \ (\text{mod } 105)$.
Haben die Moduln gemeinsame Teiler, ist das System nur lösbar, wenn die Reste dazu passen: $x \equiv 1 \ (\text{mod } 4)$ und $x \equiv 2 \ (\text{mod } 6)$ widersprechen sich, denn das erste $x$ ist ungerade, das zweite gerade. Mehr dazu und die Anwendung beim Verschlüsseln findest Du unter RSA und chinesischer Restsatz; Systeme bis zu acht Kongruenzen löst der Modulo-Rechner.
Wo man das braucht
- Prüfziffern: Bei Strichcodes (EAN), ISBN und IBAN wird eine gewichtete Summe der Ziffern modulo 10, 11 bzw. 97 gebildet. So werden Tippfehler erkannt – siehe Prüfziffern.
- Verschlüsselung: Das RSA-Verfahren rechnet mit großen Potenzen modulo einer Zahl $n = p \cdot q$; der private Schlüssel ist ein modulares Inverses – siehe RSA-Verschlüsselung.
- Informatik: Hashfunktionen, Zufallszahlengeneratoren und Ringpuffer arbeiten mit Resten.
- Teilbarkeitsregeln: Weil $10 \equiv 1 \ (\text{mod } 9)$ ist, hat jede Zahl modulo 9 denselben Rest wie ihre Quersumme – das steckt hinter den Teilbarkeitsregeln.
Typische Fehler
- Negativer Rest: $-17 \bmod 5$ ist $3$, nicht $-2$ und nicht $2$.
- ggT ist nicht der letzte Rest: Der ggT ist der letzte Rest ungleich 0.
- Inverses ohne Prüfung: Erst den ggT prüfen. Ist er nicht 1, gibt es kein Inverses.
- Negatives $t$ nicht angepasst: Aus $t = -11$ wird modulo 26 das Inverse $15$.
- Lösungen vergessen: Bei $d = \operatorname{ggT}(a, m) > 1$ gibt es $d$ Lösungen zwischen 0 und $m - 1$.
- Fermat falsch angewendet: Der Satz gilt nur für einen Primzahl-Modul, und man reduziert den Exponenten modulo $p - 1$ – nicht modulo $p$.
Grundlagen zu Teilern, ggT und kgV findest Du unter ggT und kgV, Rechnen in anderen Basen unter Zahlensysteme.
Online üben
Reste immer zwischen 0 und $m - 1$ angeben. Bei Kongruenzen mit mehreren Lösungen alle Lösungen zwischen 0 und $m - 1$ mit Semikolon trennen; gibt es keine Lösung, schreibe keine.
Stufe 1: Rest, Wochentage und Kongruenzen
-
Aufgabe 1
\(\text{Freitag} + 169\text{ Tage}\)\(169 \text{ mod } 7 = 1 \Rightarrow \text{Samstag}\)
-
Aufgabe 2
\(5\text{ Uhr} + 120\text{ Stunden}\)Uhr\((5 + 120) \text{ mod } 24 = 5\text{ Uhr}\)
-
Aufgabe 3
\((303 + 503) \text{ mod } 6\)\((3 + 5) \text{ mod } 6 = 2\)
-
Aufgabe 4
\(\text{Freitag} + 189\text{ Tage}\)\(189 \text{ mod } 7 = 0 \Rightarrow \text{Freitag}\)
-
Aufgabe 5
\(630 \text{ mod } 9\)\(630 = 70 \cdot 9 + 0 \Rightarrow 0\)
-
Aufgabe 6
\(823 \text{ mod } 4\)\(823 = 205 \cdot 4 + 3 \Rightarrow 3\)
-
Aufgabe 7
\((-42) \text{ mod } 10\)\(-42 = (-5) \cdot 10 + 8 \Rightarrow 8\)
-
Aufgabe 8
Mittwoch \(+ 342\text{ Tage}\)\(342 \text{ mod } 7 = 6\) \(\Rightarrow\) Dienstag
Tippe Deine Lösung ein und klicke auf „Prüfen“ (oder drücke Enter). Brüche als 3/4, Dezimalzahlen mit Komma, mehrere Lösungen mit ; trennen, Potenzen als x^2, Wurzeln als sqrt(5). Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp, 0 wenn Du Dir vorher die Lösung anschaust. Deine Punkte und Abzeichen siehst Du unter Mein Training.
Arbeitsblatt: Modulo-Rechnen und euklidischer Algorithmus
Eine volle DIN-A4-Seite Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 13.
Weiterlesen: Division mit Rest, Kongruenz (Zahlentheorie), Euklidischer Algorithmus bei Wikipedia