Was bedeutet das Zeichen $\equiv$?

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.

Warum darf ich die Zahlen zuerst reduzieren?

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.

Wo wird modulare Arithmetik außerhalb der Schule verwendet?

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.

Lehrermaterialien

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 MinLektion

In Classroom teilen

Arbeitsblatt zum Drucken

Definition

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.

Probier es gleich aus

Was ist

23 \bmod 5

Lösungsbeispiele

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

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

Häufige Fehler

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

Warum es falsch ist: 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.

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

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

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

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

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

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

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

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

Warum es falsch ist: 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.

Richtig: 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$ .

Interaktive Visualisierung

9 Uhr plus 100 Stunden: zähle die Runden

12 Plätze auf dem Ziffernblatt: mod 12

Start

Addieren

Starte bei 9 und gehe 100 Stunden vorwärts.

Wochentage rechnen modulo 7: erst tippen, dann zusehen

7 Plätze auf dem Ziffernblatt: mod 7

Wo landet der Zeiger? Tippe auf den Platz auf dem Ziffernblatt.

2 + 100 ≡ ? (mod 7)

Starte bei Mi und gehe 100 Tage vorwärts.

Kongruent modulo 12: dieselbe Stelle auf dem Zifferblatt

12 Plätze auf dem Ziffernblatt: mod 12

Erste Zahl

Zweite Zahl

38 = 3 × 12 + 2

14 = 1 × 12 + 2

38 − 14 = 24 = 2 × 12

38 ≡ 14 (mod 12)

38 und 14 landen auf demselben Platz, weil ihre Differenz 24 ein Vielfaches von 12 ist.

Zahlen auf dem Platz 2: … -10, 2, 14, 26, 38 …

Endziffern der Potenzen von 3 (modulo 10) wiederholen sich

10 Plätze auf dem Ziffernblatt: mod 10

Basis

Exponent

Multipliziere immer wieder mit 3 und behalte jedes Mal nur den Rest.

Interaktiver Sandkasten

Ausdrucksrechner

Probiere diese:

Verlauf

Noch keine Berechnungen

Übungsaufgaben

18 Aufgaben

Aufgabe 1 von 18

Einfach

Was ist

23 \bmod 5

Warum es wichtig ist

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).

Anwendungen im echten Leben

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.

Beispiel:

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).

1Probiere es selbst

Heute ist Mittwoch. Dein Austausch beginnt in genau 100 Tagen. Nummeriere die Tage Montag $= 0$ , Dienstag $= 1$ und so weiter bis Sonntag $= 6$ .

An welchem Wochentag beginnt der Austausch?

Schritt 1: Wähle die richtige Antwort

Wähle den Tag:

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.

Beispiel:

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$ .

2Probiere es selbst

Ein Laden erstellt einen Produktcode mit den 12 Ziffern $400123456789$ . Die Ziffern an den Stellen 1, 3, 5, ... zählen einfach, die Ziffern an den Stellen 2, 4, 6, ... dreifach. Die Prüfziffer macht die Summe zu einem Vielfachen von 10.

Wie lautet die Prüfziffer?

Schritt 1: Schreibe den mathematischen Ausdruck

Prüfziffer:

Schichtarbeit und die 24-Stunden-Uhr

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

Beispiel:

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.

3Probiere es selbst

Ein Maschinentest in einer Fabrik beginnt um 19:00 Uhr und läuft 75 Stunden ohne Pause.

Zu welcher Stunde (0 bis 23) endet der Test?

Schritt 1: Schreibe den mathematischen Ausdruck

Endstunde:

Wichtige Erkenntnisse

1 $a \bmod n$ ist der Rest von $a : n$ und immer eine der Zahlen $0, 1, \ldots, n - 1$
2 $a \equiv b \pmod{n}$ bedeutet, dass $a$ und $b$ denselben Rest lassen, und das heißt dasselbe wie: $n$ teilt $a - b$
3Eine Uhr rechnet modulo 12, die 24-Stunden-Uhr modulo 24, die Wochentage modulo 7 und gerade/ungerade modulo 2
4In Summen, Differenzen und Produkten darfst du jede Zahl zuerst reduzieren und das Ergebnis danach noch einmal
5Bei einer negativen Zahl addierst du $n$ , bis sie in $0, \ldots, n - 1$ landet: $-3 \bmod 12 = 9$
6Potenzen wiederholen sich modulo $n$ in Zyklen: Bestimme die Zykluslänge und reduziere den Exponenten modulo dieser Länge, nicht modulo $n$

Häufig gestellte Fragen

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.

Glossar

Modul: Die feste Zahl $n$ , durch die du teilst; die Reste sind $0, 1, \ldots, n - 1$ (12 bei der Uhr, 7 bei den Wochentagen)
Rest: Was beim Teilen übrig bleibt: In $a = q \times n + r$ mit $0 \leq r \leq n - 1$ ist es $r$
a mod n: Der Rest von $a$ bei Division durch $n$ , zum Beispiel $17 \bmod 5 = 2$ und $-3 \bmod 12 = 9$
Kongruent modulo n: Zwei Zahlen mit demselben Rest modulo $n$ , geschrieben $a \equiv b \pmod{n}$ ; gleichbedeutend: $n$ teilt $a - b$
Zykluslänge: Nach wie vielen Schritten sich die Reste von Potenzen wiederholen, zum Beispiel 4 für die Endziffern der Potenzen von 3
Prüfziffer: Eine zusätzliche Ziffer am Ende eines Codes (Strichcode, ISBN), so gewählt, dass eine gewichtete Summe durch 10 oder 11 teilbar ist

Formelkarte

Division mit Rest

a = q \times n + r, \quad 0 \leq r \leq n - 1

$r$ ist $a \bmod n$, $q$ ist der Quotient

Kongruenz

a \equiv b \pmod{n} \iff n \mid (a - b)

Derselbe Rest, oder: Die Differenz ist ein Vielfaches von $n$

Erst reduzieren

(a + b) \bmod n = \big((a \bmod n) + (b \bmod n)\big) \bmod n

Dasselbe gilt für Subtraktion und Multiplikation

Negative Zahlen

x \bmod n = (x + k \times n) \bmod n

Addiere ein Vielfaches von $n$, bis die Zahl in $0, \ldots, n - 1$ landet: $-3 + 12 = 9$

Heutige ChallengeEine Aufgabe, drei Versuche

Mehr zu diesem Thema

Gerade und ungerade Zahlen

Grundlegend15 Min

Quadratzahlen und perfekte Quadrate

Mittelstufe25 Min