Modulare Arithmetik intuitiv verstehen (Uhrenrechnen und warum Reste alles entscheiden)

Es ist neun Uhr, und in fünf Stunden geht ein Flug. Niemand antwortet vierzehn Uhr. Du sagst zwei, und du hast es ohne Nachdenken getan, weil ein Uhrenblatt keine Vierzehn kennt. Die Stunden laufen bei zwölf um und beginnen wieder von vorn. Du rechnest modular, seit du die Uhr lesen kannst; du hast nur die Schreibweise nie kennengelernt.

Das ist das ganze Thema. Wähle eine Zahl, bei der umgelaufen wird, vergiss jede vollständige Runde und behalte nur, wo du landest. Einen Artikel wert ist es deshalb, weil diese eine Gewohnheit, nur den Rest zu behalten, Aufgaben löst, die frontal unmöglich aussehen: die letzte Ziffer einer Zahl mit siebzig Stellen, ob eine riesige Zahl durch 9 teilbar ist, warum eine Kreditkartennummer gültig ist oder nicht, und wie eine Nachricht so verschlüsselt werden kann, dass nur der gewünschte Leser sie entschlüsseln kann.

Dieser Artikel liefert das Bild: was ein Rest wirklich ist, warum du vor dem Rechnen reduzieren darfst, was mit negativen Zahlen und mit Potenzen passiert, und woher die eine ehrliche Schwierigkeit kommt, die Division.

Ein Rest ist dort, wo du landest, nicht was übrig bleibt

Die Standarddefinition sagt, $a \bmod n$ sei der Rest, wenn $a$ durch $n$ geteilt wird. Das ist richtig, und es ist gleichzeitig der Grund, warum sich das Thema wie eine Pflichtübung anfühlt, denn Rest klingt nach dem Abfall, der nach einer Division liegen bleibt, nach einem Nachgedanken.

Besseres Bild: eine Kreisbahn mit $n$ Markierungen, durchnummeriert von $0$ bis $n-1$. Um $a \bmod n$ zu finden, starte bei $0$ und gehe $a$ Schritte um die Bahn. Wo du stehen bleibst, ist die Antwort. 17 Schritte auf einer Bahn mit 5 Markierungen führen dreimal ganz herum (15 Schritte) und dann 2 Schritte weiter, du bleibst also auf Markierung 2 stehen. Daher $17 \bmod 5 = 2$. Die vollen Runden sind der Quotient; wo du landest, ist der Rest.

Dieses Bild leistet zwei Dinge, die die Definition nicht leistet. Es lässt den Rest immer im Bereich $0$ bis $n-1$ landen, denn andere Markierungen gibt es nicht. Und es erklärt, warum zwei Zahlen modulo $n$ dieselbe sein können, obwohl sie völlig verschieden aussehen: $2$, $17$, $102$ und $5{,}000{,}002$ halten auf einer Bahn mit 5 Markierungen alle bei Markierung 2. Sie unterscheiden sich um Runden, und die Bahn erinnert sich nicht an Runden.

Mathematiker schreiben diesen Gedanken als Kongruenz:

$$17 \equiv 2 \pmod{5}$$

Lies das als: 17 landet dort, wo 2 landet, auf der 5er-Bahn. Der Dreifachstrich ist kein Gleichheitszeichen, denn 17 und 2 sind nicht gleich. Er sagt, dass die beiden für jede Frage austauschbar sind, die sich nur für die Position auf der Bahn interessiert. Die präzise Fassung: $a \equiv b \pmod{n}$ bedeutet, dass $n$ die Differenz $a - b$ teilt, und das heißt nichts anderes, als dass sich die beiden Zahlen um eine ganze Anzahl von Runden unterscheiden.

Addieren und Multiplizieren interessiert nur, wo du stehst

Hier ist die Tatsache, die modulare Arithmetik zu einem Werkzeug macht statt zu einer Kuriosität. Willst du zwei Zahlen addieren und dann den Rest bestimmen, darfst du zuerst die Reste bestimmen, diese addieren und erneut reduzieren. Das Ergebnis ist identisch. Dasselbe gilt für Subtraktion und Multiplikation.

Auf der Bahn ist es offensichtlich. 17 zu addieren heißt 17 Schritte zu gehen, also drei Runden plus 2. Die drei Runden bringen dich dorthin zurück, wo du gestartet bist, und ändern nichts, 17 zu addieren wirkt also genauso wie 2 zu addieren. Die in einer Zahl versteckten Runden sind totes Gewicht, und sie bleiben totes Gewicht durch die Addition und durch die Multiplikation hindurch, denn ein Vielfaches von $n$ mal irgendetwas ist immer noch ein Vielfaches von $n$.

Ausgeschrieben, mit $a = qn + r$ und $b = pn + s$:

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

Alles in der ersten Klammer sind Runden. Nur $rs$ überlebt, also ist $ab \bmod n$ dasselbe wie $rs \bmod n$. Die Reste tragen die gesamte Information, die die Frage braucht.

Deshalb sagt der Tipp im Arithmetik-Themengebiet von Math Zen, man solle Schritt für Schritt reduzieren statt den vollen Wert auszurechnen. Angenommen, du willst $123 \times 456 \bmod 7$. Du könntest auf 56.088 ausmultiplizieren und schriftlich durch 7 teilen. Oder du bemerkst $123 = 119 + 4$, also $123 \equiv 4$, und $456 = 455 + 1$, also $456 \equiv 1$, und die Antwort ist $4 \times 1 = 4$. Zwei kleine Reduktionen ersetzen eine vierstellige Multiplikation. Die Gewohnheit lautet: Lass eine Zahl nie über $n$ hinauswachsen, wenn dich nur ihr Rest interessiert.

Negative Zahlen gehen in die andere Richtung

Das Bild der Bahn erledigt auch den Fall, über den die meisten stolpern. Was ist $-3 \bmod 5$?

Gehe von 0 aus 3 Schritte rückwärts auf einer Bahn mit 5 Markierungen. Du passierst 4, dann 3, und landest auf 2. Also $-3 \equiv 2 \pmod{5}$. Eine negative Zahl ist nur ein Gang in die andere Richtung, dieselbe Idee wie in Negative Zahlen intuitiv verstehen, und der Rest ist weiterhin dort, wo du landest, weiterhin zwischen $0$ und $n-1$.

Die Abkürzung: Addiere Runden, bis die Zahl positiv ist. $-3 + 5 = 2$. Für $-14 \bmod 5$ addiere 15 (drei Runden) und erhalte 1. Taschenrechner und Programmiersprachen sind sich über negative Reste uneinig, manche liefern $-4$ für $-14 \bmod 5$, gib in einer Klausur die Antwort also immer als die nichtnegative Markierung auf der Bahn an und prüfe die Konvention deines Rechners, bevor du ihm vertraust.

Bei der Subtraktion ist es dieselbe Geschichte. $3 - 8 \pmod{5}$ ist $-5$, also genau eine Runde rückwärts, die Antwort ist somit 0. Oder reduziere zuerst: $8 \equiv 3$, also $3 - 3 = 0$.

Die letzte Ziffer einer riesigen Potenz

Das ist die Aufgabe, die Leute davon überzeugt, dass das Thema es wert ist, und sie folgt direkt aus der Regel, zuerst zu reduzieren.

Die letzte Ziffer einer Zahl ist die Zahl modulo 10, denn die Zehner, Hunderter und alles darüber sind Vielfache von 10 und landen auf einer Bahn mit 10 Markierungen wieder bei 0. Die Frage, was die letzte Ziffer von $7^{100}$ ist, lautet also: Was ist $7^{100} \bmod 10$, und du musst $7^{100}$ nie ausrechnen.

Beobachte stattdessen, wie die Potenzen von 7 über die 10er-Bahn wandern, und reduziere jedes Mal:

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

Sobald du bei 1 angekommen bist, beginnt der Zyklus von neuem: 7, 9, 3, 1, 7, 9, 3, 1, mit der Periode 4. Da $100 = 4 \times 25$ ist, sitzt die hundertste Potenz am Ende eines vollständigen Zyklus, auf derselben Stelle wie $7^4$, und ihre letzte Ziffer ist 1.

Jede Basis hat einen Zyklus modulo 10, und die meisten sind kurz. Potenzen von 2 laufen durch 2, 4, 8, 6. Potenzen von 3 durch 3, 9, 7, 1. Potenzen von 5 und 6 rühren sich nie. Die Methode ist immer dieselbe: Finde die Zykluslänge, indem du unterwegs reduzierst, teile den Exponenten durch die Zykluslänge, und der Rest dieser Division sagt dir, wo im Zyklus du stehst. Es ist die Idee der Potenzen als wiederholte Multiplikation, nur auf einer Kreisbahn statt auf einer Gerade ausgeführt.

Warum die Ziffernsummen-Regel für die 9 funktioniert

Alle lernen, dass eine Zahl durch 9 teilbar ist, wenn ihre Ziffern sich zu einem Vielfachen von 9 addieren, und fast niemand lernt, warum. Modulare Arithmetik macht daraus ein einzeiliges Argument.

Zehn ist eine Runde plus eins auf der 9er-Bahn: $10 \equiv 1 \pmod{9}$. Dann ist $100 = 10 \times 10 \equiv 1 \times 1 = 1$, und jede Potenz von 10 ist ebenfalls kongruent zu 1. Eine Zahl wie $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ ist also kongruent zu $4 + 5 + 2 + 7 = 18 \pmod{9}$, und 18 ist auf der 9er-Bahn die $0$, somit ist 4.527 durch 9 teilbar. Die Ziffernsumme ist kein Trick. Sie ist die Zahl selbst, modulo 9 betrachtet.

Die Regel für die 3 funktioniert aus demselben Grund, denn auch $10 \equiv 1 \pmod{3}$. Die Regel für die 11 kommt von $10 \equiv -1 \pmod{11}$, wodurch die Potenzen von 10 zwischen $1$ und $-1$ wechseln, was die alternierende Ziffernsumme ergibt. Alle Teilbarkeitsregeln, die du auswendig lernen solltest, sind eine einzige Tatsache, reduziere die Potenzen von 10, angewandt auf verschiedene Bahnen.

Prüfziffern: modulare Arithmetik in deiner Geldbörse

Jede ISBN, jede Kreditkartennummer und jeder Barcode endet mit einer Ziffer, deren einzige Aufgabe es ist, ein Rest zu sein.

Die letzte Ziffer einer 13-stelligen ISBN wird so gewählt, dass eine gewichtete Summe aller dreizehn Ziffern, mit abwechselnden Gewichten 1 und 3, kongruent zu $0 \pmod{10}$ ist. Vertippe dich bei einer einzigen Ziffer, und die Summe landet irgendwo anders auf der 10er-Bahn, und der Scanner weist sie ab. Kreditkarten verwenden den Luhn-Algorithmus, eine etwas raffiniertere Gewichtung, die zusätzlich die meisten Fälle erkennt, in denen zwei benachbarte Ziffern vertauscht sind, wieder durch die Prüfung einer Summe modulo 10.

Das sind die bescheidenen Verwandten einer viel größeren Anwendung. Moderne Verschlüsselung beruht darauf, dass es leicht ist, eine Zahl modulo eines sehr großen $n$ zu potenzieren, während der umgekehrte Weg ohne geheimen Schlüssel es nicht ist. Die Zyklussuche, die du oben für $7^{100}$ durchgeführt hast, ist dieselbe Operation, nur hochskaliert auf Zahlen mit hunderten von Stellen, und die Regel, unterwegs zu reduzieren, ist der einzige Grund, warum sie überhaupt berechenbar ist.

Bei der Division wird die Bahn holprig

Addition, Subtraktion und Multiplikation verhalten sich auf einer Bahn genau wie auf der Zahlengeraden. Die Division nicht, und hier verdient sich das Thema seinen Ruf.

Auf der gewöhnlichen Zahlengeraden heißt durch 4 teilen, mit $\tfrac{1}{4}$ zu multiplizieren, also mit der Zahl, die mal 4 gleich 1 ergibt. Gibt es auf der 12er-Bahn eine Markierung, die mal 4 auf 1 landet? Probiere alle durch: $4 \times 1 = 4$, $4 \times 2 = 8$, $4 \times 3 = 12 \equiv 0$, $4 \times 4 = 16 \equiv 4$, und das Muster 4, 8, 0 wiederholt sich für immer. Es trifft die 1 nie. Auf der 12er-Bahn gibt es also so etwas wie das Teilen durch 4 nicht.

Der Grund ist, dass 4 und 12 einen Faktor teilen. Beginne mit einem Vielfachen von 4, füge Runden von 12 hinzu oder nimm sie weg, und du hast weiterhin ein Vielfaches von 4, du kannst also nie 1 hinter einem Vielfachen von 12 landen. Probiere stattdessen die 5: $5 \times 5 = 25 = 24 + 1 \equiv 1$, die 5 ist auf der 12er-Bahn also ihr eigenes Inverses, und durch 5 teilen ist in Ordnung. Die Regel: $a$ hat genau dann ein Inverses modulo $n$, wenn $a$ und $n$ außer 1 keinen gemeinsamen Faktor haben.

Diese Regel hat eine bemerkenswerte Folge. Ist $n$ prim, so teilt nichts von $1$ bis $n - 1$ einen Faktor mit ihm, jede Markierung außer null hat also ein Inverses und du darfst frei dividieren. Primzahl-Bahnen sind die, auf denen alle vier Rechenarten funktionieren, und das ist ein großer Teil des Grundes, warum Primzahlen, deren Vorrat die Unendlichkeit der Primzahlen garantiert, im Zentrum der Zahlentheorie und der Kryptographie stehen.

Wo die typischen Fehler entstehen

Modulare Arithmetik hat wenige bewegliche Teile, und die Fehler sind entsprechend spezifisch.

Der erste ist, den Exponenten statt der Basis zu reduzieren. Bei $7^{100} \bmod 10$ darfst du 7 modulo 10 reduzieren (das ist es schon), und du darfst den Exponenten modulo der Zykluslänge reduzieren, sobald du sie kennst, aber du darfst nicht 100 modulo 10 reduzieren und $7^0$ berechnen. Exponenten leben auf einer anderen Bahn, auf der, deren Größe die Zykluslänge ist, und die beiden Bahnen zu vermischen ist der mit Abstand häufigste Fehler in diesem Thema.

Der zweite ist ein negativer Rest. $-14 \bmod 5$ ist 1, nicht $-4$. Dieselbe Position auf der Bahn, aber nur eine der beiden ist der konventionelle Name, und Lösungsschlüssel wollen die nichtnegative.

Der dritte ist, ohne Prüfung auf ein Inverses zu dividieren. Einen gemeinsamen Faktor auf beiden Seiten einer Kongruenz zu kürzen ist nur erlaubt, wenn dieser Faktor nichts mit dem Modul teilt. Aus $4 \times 2 \equiv 4 \times 5 \pmod{12}$, was wahr ist, da beide Seiten 8 ergeben, darfst du nicht die 4 kürzen und auf $2 \equiv 5$ schließen, was falsch ist. Die Runden, die du beim Kürzen wegwirfst, müssen Runden der ursprünglichen Bahn sein.

Der vierte ist, am Ende das Reduzieren zu vergessen. Auf einer 7er-Bahn $rs = 21$ zu erhalten und 21 hinzuschreiben ist nicht genau falsch, aber es ist auch keine Antwort. Die Antwort ist eine Markierung auf der Bahn, und 21 sind drei Runden, die Markierung ist also 0.

Wo Math Zen ansetzt

Das Arithmetik-Themengebiet von Math Zen hat einen eigenen Abschnitt für modulare Arithmetik, und der Aufbau ist um die Gewohnheit, zuerst zu reduzieren, gelegt und nicht um die Schreibweise. Frühe Aufgaben fragen nach schlichten Resten und Kongruenzen mit kleinen Moduln, bis das wo lande ich automatisch geworden ist. Die mittleren Abschnitte mischen negative Zahlen und Produkte hinein, wo es darauf ankommt, jeden Faktor vor dem Multiplizieren zu reduzieren und den nichtnegativen Rest anzugeben. Die späteren Abschnitte sind die Aufgaben zu letzten Ziffern und Zykluslängen, also die, die in Wettbewerbsklausuren und Aufnahmetests auftauchen und jeden bestrafen, der versucht, die volle Potenz auszurechnen.

Weil die Sitzungen kurz sind und die Aufgaben in zeitlichen Abständen zurückkommen, wie in verteiltes Wiederholen beim Mathe-Üben beschrieben, wird der Griff zur Zyklussuche zum Reflex statt zu einem Verfahren, das man nachschlägt. Die meisten Menschen haben keine Lücke in modularer Arithmetik, die ein Kapitel schließen würde. Sie haben ein Bild, die Bahn, das nie für sie gezeichnet wurde, und etwa vierzig Wiederholungen, die nie gemacht wurden.

Das Fazit

Modulare Arithmetik ist Rechnen auf einer Kreisbahn mit $n$ Markierungen. Ein Rest ist dort, wo du nach $a$ Schritten landest, vollständige Runden werden vergessen, und zwei Zahlen sind kongruent, wenn sie auf derselben Markierung landen. Weil Runden zu Summen und Produkten nichts beitragen, darfst du jede Zahl vor dem Addieren oder Multiplizieren auf ihren Rest reduzieren, und diese eine Erlaubnis verwandelt unmögliche Rechnungen, etwa die letzte Ziffer von $7^{100}$, in kurze Zyklen, die du mit der Hand nachgehen kannst. Teilbarkeitsregeln sind die Potenzen von 10, reduziert modulo 9, 3 oder 11. Prüfziffern sind Reste, die Tippfehler abfangen. Die Division funktioniert nur, wenn die Zahl mit der Bahn keinen Faktor teilt, und deshalb sind Primzahl-Bahnen etwas Besonderes.

Wenn eine modulare Aufgabe stockt, zeichne die Bahn. Frage, wo jedes Stück landet, reduziere unterwegs, und halte den Exponenten auf seiner eigenen Bahn. Die Antwort ist eine Markierung zwischen $0$ und $n - 1$, und das Bild bringt dich dorthin, bevor es die Formel tut.