Modulare Arithmetik

**Modulare Arithmetik** (auch Restklassenrechnung) ist Rechnen mit Resten. Du legst eine ganze Zahl $n \geq 2$ fest, den **Modul**, und behältst von einer Zahl nur ihren **Rest** bei der Division durch $n$: $$a = q \times n + r, \qquad a \bmod n = r, \qquad 0 \leq r \leq n - 1$$ Zum Beispiel ist $17 \bmod 5 = 2$, denn $17 = 3 \times 5 + 2$. Zwei Zahlen heißen **kongruent modulo n**, wenn sie denselben Rest lassen. Das ist dasselbe wie: $n$ teilt ihre Differenz. $$a \equiv b \pmod{n} \iff n \text{ teilt } a - b$$ Also ist $38 \equiv 14 \pmod{12}$, denn $38 - 14 = 24 = 2 \times 12$ (beide lassen den Rest $2$). Eine Uhr funktioniert genau so: Nach 12 Stunden steht der Zeiger wieder am Anfang, also sind 15 Uhr und 3 Uhr dieselbe Stelle, $15 \equiv 3 \pmod{12}$. In Summen, Differenzen und Produkten darfst du jede Zahl zuerst durch ihren Rest ersetzen und das Ergebnis am Ende noch einmal reduzieren.

Einen Rest bestimmen

Bestimme $47 \bmod 6$.

Finde das größte Vielfache von 6, das nicht größer als 47 ist: $6 \times 7 = 42$, während $6 \times 8 = 48$ schon zu groß ist = $42$

Schreibe 47 als Quotient mal 6 plus Rest: $47 = 7 \times 6 + 5$ = Rest $5$

Prüfe, dass der Rest zwischen 0 und 5 liegt: $0 \leq 5 \leq 5$, also ist es ein gültiger Rest = $47 \bmod 6 = 5$

Answer: $47 \bmod 6 = 5$, also $47 \equiv 5 \pmod{6}$. Der Quotient $7$ gehört nicht zur Antwort.

100 Stunden auf der Uhr

Es ist 9 Uhr. Wohin zeigt der Stundenzeiger in 100 Stunden?

Entferne die vollen Runden: Eine Runde der Uhr sind 12 Stunden: $100 = 8 \times 12 + 4$, und 8 volle Runden ändern nichts = $100 \bmod 12 = 4$

Addiere die übrigen Stunden zum Start: $9 + 4 = 13$ = $13$

Reduziere noch einmal, denn auf dem Zifferblatt gibt es keine 13: $13 = 1 \times 12 + 1$ = $13 \bmod 12 = 1$

Answer: Der Zeiger zeigt auf 1. In einer Zeile: $9 + 100 = 109 = 9 \times 12 + 1$, also $109 \equiv 1 \pmod{12}$.

Erst reduzieren, dann multiplizieren

Bestimme $(38 \times 27) \bmod 5$, ohne die großen Zahlen zu multiplizieren.

Reduziere jeden Faktor modulo 5: $38 = 7 \times 5 + 3$ und $27 = 5 \times 5 + 2$ = $38 \equiv 3$ und $27 \equiv 2 \pmod{5}$

Multipliziere die Reste: $3 \times 2 = 6$ = $6$

Reduziere das Produkt: $6 = 1 \times 5 + 1$ = $1$

Kontrolle mit dem vollen Produkt: $38 \times 27 = 1026 = 205 \times 5 + 1$ = derselbe Rest $1$

Answer: $(38 \times 27) \bmod 5 = 1$. Mit dem Reduzieren reichte die Rechnung $3 \times 2$.

Im Kalender zurückgehen

Heute ist Mittwoch. Welcher Wochentag war vor 30 Tagen? Nummeriere die Tage Montag $= 0$, Dienstag $= 1$ und so weiter bis Sonntag $= 6$.

Gib dem heutigen Tag seine Nummer: Montag $= 0$, Dienstag $= 1$, Mittwoch $= 2$ = $2$

Zurück in der Zeit heißt subtrahieren: $2 - 30 = -28$ = $-28$

Bestimme den Rest 0 bis 6 der negativen Zahl: $-28 = (-4) \times 7 + 0$ = $-28 \bmod 7 = 0$

Übersetze die Nummer zurück in einen Tag: Tag $0$ ist Montag = Montag

Answer: Vor 30 Tagen war Montag. Kontrolle: Vor 28 Tagen war Mittwoch (genau 4 Wochen), zwei Tage weiter zurück ist Montag.

Die letzte Ziffer einer riesigen Potenz

Was ist die letzte Ziffer von $3^{100}$?

Die letzte Ziffer ist der Rest modulo 10. Schreibe die ersten Potenzen auf: $3^1 = 3$, $3^2 = 9$, $3^3 = 27$, $3^4 = 81$ = Endziffern $3, 9, 7, 1$

Erkenne den Zyklus: $3^5 = 243$ endet wieder auf 3, denn die nächste Endziffer hängt nur von der vorigen ab = Zykluslänge $4$

Finde, wo der Exponent 100 im Zyklus landet: $100 = 25 \times 4 + 0$ = $100 \bmod 4 = 0$

Rest 0 bedeutet die letzte Stelle des Zyklus: $3^{100} = (3^4)^{25} \equiv 1^{25} = 1 \pmod{10}$ = letzte Ziffer $1$

Answer: $3^{100}$ endet auf $1$, obwohl die Zahl 48 Stellen hat.

Modulare Arithmetik ist die Mathematik von allem, was sich im Kreis dreht: - **Zeit**: Uhren zählen modulo 12 oder 24, Wochentage modulo 7. Wie spät ist es in 100 Stunden? Welcher Tag ist in 100 Tagen? - **Prüfziffern**: Die letzte Ziffer eines Strichcodes (EAN-13) wird modulo 10 gewählt, eine ISBN-10 modulo 11, und die IBAN eines Bankkontos wird modulo 97 geprüft. Eine falsch getippte Ziffer, und die Prüfung schlägt fehl. - **Riesige Zahlen**: Die letzte Ziffer von $3^{100}$ (einer Zahl mit 48 Stellen) findest du im Kopf, denn Endziffern sind Reste modulo 10 und sie wiederholen sich in einem Zyklus. - **Informatik**: Hashtabellen, Zufallszahlengeneratoren und die RSA-Verschlüsselung hinter dem Onlinebanking rechnen alle modulo $n$. Einen Fall kennst du schon: **gerade und ungerade** ist einfach Rechnen modulo 2 (Rest 0 oder 1).

Mistake: $-3 \bmod 12 = -3$ (oder $3$) schreiben

Why: Ein Rest muss eine der Zahlen $0, 1, \ldots, n - 1$ sein. Wenn du von 12 Uhr 3 Stunden zurückgehst, landest du weder bei einer negativen Zahl noch bei 3.

Correct: Addiere den Modul, bis die Zahl im Bereich liegt: $-3 + 12 = 9$, also $-3 \bmod 12 = 9$.

Mistake: Sagen, dass 9 Uhr plus 4 Stunden auf einer 12-Stunden-Uhr 13 Uhr ist

Why: Die Summe $9 + 4 = 13$ stimmt, aber das letzte Reduzieren fehlt. Jedes Ergebnis muss noch einmal reduziert werden.

Correct: $13 \bmod 12 = 1$: Die Uhr zeigt 1.

Mistake: Den Quotienten statt des Rests angeben: $47 \bmod 6 = 7$

Why: $47 : 6 = 7$ Rest $5$. Die Operation mod behält nur, was übrig bleibt, nicht wie oft 6 in 47 passt.

Correct: $47 \bmod 6 = 5$, denn $47 = 7 \times 6 + 5$.

Mistake: Den Exponenten durch den Modul reduzieren: aus $2^9 \bmod 7$ wird $2^2 = 4$, weil $9 \bmod 7 = 2$

Why: Die Basis darfst du modulo $n$ reduzieren, den Exponenten aber nicht. Der Exponent richtet sich nach der Länge des Potenzzyklus, und die ist hier 3, nicht 7.

Correct: Die Potenzen von 2 modulo 7 sind $2, 4, 1, 2, 4, 1, \ldots$ (Zykluslänge 3). $9 \bmod 3 = 0$, also $2^9 \equiv 1 \pmod{7}$. Kontrolle: $512 = 73 \times 7 + 1$.

Kalender: Welcher Tag wird es sein?

Eine Woche hat 7 Tage, also wiederholen sich die Wochentage modulo 7. Kalender-Apps, Fahrpläne und Geburtstagsrätsel nutzen das ständig.

Ein normales Jahr hat $365$ Tage und $365 = 52 \times 7 + 1$. Ein Geburtstag, der dieses Jahr auf einen Montag fällt, fällt nächstes Jahr also auf einen Dienstag (außer der 29. Februar liegt dazwischen).

Strichcodes und Prüfziffern

Die letzte Ziffer jedes EAN-13-Strichcodes ist eine Prüfziffer, die mit Rechnen modulo 10 gewählt wird. Der Scanner berechnet sie neu und lehnt einen Code mit einer falsch gelesenen Ziffer ab.

Für den Buchcode $978030640615$ ist die gewichtete Summe (Gewichte $1, 3, 1, 3, \ldots$) gleich $93$, und $93 \bmod 10 = 3$. Die Prüfziffer ist $10 - 3 = 7$, der vollständige Code lautet $9780306406157$.

Schichtarbeit und die 24-Stunden-Uhr

Fahrpläne, Klinikschichten und Flugpläne verwenden die 24-Stunden-Uhr, also Rechnen modulo 24.

Eine Nachtschicht beginnt um 22:00 Uhr und dauert 9 Stunden: $22 + 9 = 31$ und $31 \bmod 24 = 7$, sie endet also um 07:00 Uhr.

$a \bmod n$ ist der Rest von $a : n$ und immer eine der Zahlen $0, 1, \ldots, n - 1$

$a \equiv b \pmod{n}$ bedeutet, dass $a$ und $b$ denselben Rest lassen, und das heißt dasselbe wie: $n$ teilt $a - b$

Eine Uhr rechnet modulo 12, die 24-Stunden-Uhr modulo 24, die Wochentage modulo 7 und gerade/ungerade modulo 2

In Summen, Differenzen und Produkten darfst du jede Zahl zuerst reduzieren und das Ergebnis danach noch einmal

Bei einer negativen Zahl addierst du $n$, bis sie in $0, \ldots, n - 1$ landet: $-3 \bmod 12 = 9$

Potenzen wiederholen sich modulo $n$ in Zyklen: Bestimme die Zykluslänge und reduziere den Exponenten modulo dieser Länge, nicht modulo $n$

Q: Ist $a \bmod n$ derselbe Rest, den mein Taschenrechner oder Computer zeigt?

A: Für positive Zahlen ja. Für negative Zahlen liefern viele Programmiersprachen ein negatives Ergebnis, zum Beispiel $-3$ für $-3$ geteilt durch $12$. In der Mathematik liegt der Rest immer zwischen $0$ und $n - 1$, also ist $-3 \bmod 12 = 9$. Der Rechner auf dieser Seite arbeitet so: mod(-3, 12) ergibt 9.

Q: Was bedeutet das Zeichen $\equiv$?

A: Man liest es als „ist kongruent zu“. $17 \equiv 5 \pmod{12}$ sagt, dass 17 und 5 bei Division durch 12 denselben Rest lassen (beide den Rest 5). Es ist schwächer als $=$: Kongruente Zahlen können verschiedene Zahlen sein, die an derselben Stelle des Zifferblatts landen.

Q: Warum darf ich die Zahlen zuerst reduzieren?

A: Schreibe $a = pn + r$ und $b = qn + s$. Dann ist $a + b = (p + q)n + (r + s)$ und $a \times b = (pqn + ps + qr)n + rs$. Die Teile mit $n$ sind Vielfache von $n$ und lassen keinen Rest, also entscheiden nur $r + s$ und $r \times s$ über das Ergebnis.

Q: Wo wird modulare Arithmetik außerhalb der Schule verwendet?

A: Bei Prüfziffern (Strichcodes, ISBN, die IBAN eines Bankkontos, die modulo 97 geprüft wird), in der Informatik (Hashtabellen, Zufallszahlengeneratoren) und in der Kryptografie: Das RSA-Verfahren, das Onlinebanking schützt, rechnet mit riesigen Zahlen modulo einem Produkt zweier Primzahlen.

Präsentation beenden

Modulare Arithmetik

1 / 14

Zahlentheorie / Zahleneigenschaften

Modulare Arithmetik

Lerne Uhrenarithmetik: Reste, a mod n, Kongruenz modulo n und wie du damit Wochentage, Prüfziffern und die letzte Ziffer riesiger Potenzen bestimmst.

Fortgeschritten25 Min

Verwende Pfeiltasten oder Leertaste zum Navigieren