Wie spät ist es in fünf Stunden?
Modulare Arithmetik rechnet mit dem Rest einer Division. Sie steckt hinter Uhrzeiten, Prüfziffern auf Büchern und der Verschlüsselung im Netz.
Ein Beispiel: Es ist 22 Uhr. In 5 Stunden ist es nicht 27 Uhr, sondern 3 Uhr. Die Uhr rechnet im Kreis, und genau das tut auch der Rest.
Am Ende dieser Lektion
Notiz
Ich kann mit Resten rechnen, den größten gemeinsamen Teiler finden und Primzahlen erkennen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Modulo | der Rest einer Division mit ganzen Zahlen | 17 % 5 |
| ggT | der größte gemeinsame Teiler zweier Zahlen | |
| Primzahl | eine Zahl über 1 mit genau zwei Teilern: 1 und sie selbst | |
| Prüfziffer | eine letzte Ziffer, die Tippfehler in einer Nummer erkennt | |
| Inverses | die Zahl, mit der ein Produkt beim Rest 1 ergibt |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Modulo ist der Rest einer Division
Teilen Sie 17 durch 5, erhalten Sie 3 und bleiben 2 übrig. Dieser Rest heißt Modulo: 17 mod 5 gleich 2. In Python schreibt man 17 % 5.
Der Rest liegt immer zwischen 0 und dem Teiler minus 1. Bei einer Uhr mit 24 Stunden rechnet man modulo 24: 27 Uhr ist 3 Uhr.
Beispiel: vier Reste berechnet
| Rechnung | Teilen | Rest |
|---|---|---|
| 17 mod 5 | 3 mal 5 gleich 15, bleiben 2 | 2 |
| 27 mod 24 | 1 mal 24 gleich 24, bleiben 3 | 3 |
| 100 mod 7 | 14 mal 7 gleich 98, bleiben 2 | 2 |
| 12 mod 4 | 3 mal 4 gleich 12, bleiben 0 | 0 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Reste und die Uhr in Python
python3 -c "print(17 % 5, (22 + 5) % 24, -7 % 3)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele glauben, der Rest könne so groß sein wie der Teiler, etwa 24 mod 24 gleich 24. Der Rest ist immer kleiner als der Teiler. Geht die Division auf, ist er 0. Darum ist 24 mod 24 gleich 0, und um Mitternacht zeigt die Uhr 0 Uhr.
Der ggT lässt sich mit Resten finden
Der ggT, der größte gemeinsame Teiler, ist die größte Zahl, die beide Zahlen ohne Rest teilt. Der ggT von 12 und 18 ist 6.
Das Verfahren von Euklid findet ihn schnell. Ersetzen Sie das Paar (a, b) durch (b, a mod b). Wiederholen Sie das, bis der Rest 0 ist. Die letzte Zahl ungleich 0 ist der ggT.
Beispiel: der ggT von 84 und 36
| Schritt | a | b | a mod b |
|---|---|---|---|
| 1 | 84 | 36 | 12 |
| 2 | 36 | 12 | 0 |
| Ergebnis | ggT gleich 12 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Der ggT zweier Paare
python3 -c "import math; print(math.gcd(84, 36), math.gcd(17, 5))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Eine Primzahl hat nur zwei Teiler
Eine Primzahl ist eine Zahl über 1, die nur durch 1 und durch sich selbst teilbar ist. 2, 3, 5 und 7 sind Primzahlen. 9 ist keine, denn 3 teilt sie. Die Zahl 1 ist keine Primzahl.
Ob n eine Primzahl ist, prüfen Sie so: Teilen Sie n durch jede Zahl von 2 bis n minus 1. Bleibt nie der Rest 0, ist n prim.
Alle Primzahlen unter 30
python3 -c "print([n for n in range(2, 30) if all(n % t for t in range(2, n))])"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Eine Prüfziffer erkennt Tippfehler
Auf einem Buch steht eine Nummer mit 13 Stellen. Die letzte Stelle ist eine Prüfziffer. Sie wird aus den ersten zwölf berechnet.
Man gewichtet die Ziffern abwechselnd mit 1 und 3 und addiert. Die Prüfziffer ist 10 minus (Summe mod 10), und davon noch einmal mod 10. Ein vertauschter Zahlendreher ändert die Summe und fällt auf.
Beispiel: die Prüfziffer von 978316148410
| Ziffer | Gewicht | Produkt |
|---|---|---|
| 9 | 1 | 9 |
| 7 | 3 | 21 |
| 8 | 1 | 8 |
| 3 | 3 | 9 |
| 1 | 1 | 1 |
| 6 | 3 | 18 |
| 1 | 1 | 1 |
| 4 | 3 | 12 |
| 8 | 1 | 8 |
| 4 | 3 | 12 |
| 1 | 1 | 1 |
| 0 | 3 | 0 |
| Summe | 100, mod 10 gleich 0, Prüfziffer 0 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Summe und Prüfziffer in Python
python3 -c "d = [9, 7, 8, 3, 1, 6, 1, 4, 8, 4, 1, 0]; s = sum(x * (1 if i % 2 == 0 else 3) for i, x in enumerate(d)); print(s, (10 - s % 10) % 10)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein Inverses macht das Produkt zu 1
Beim Rechnen mit Rest gibt es kein Teilen, aber ein Inverses. Das Inverse von 3 modulo 7 ist die Zahl b mit 3 mal b mod 7 gleich 1.
Probieren Sie b von 1 bis 6. Bei b gleich 5 ist 3 mal 5 gleich 15, und 15 mod 7 ist 1. Ein Inverses gibt es nur, wenn der ggT von a und dem Modul 1 ist. Auf diesem Prinzip beruht die Verschlüsselung RSA.
Beispiel: das Inverse von 3 modulo 7
| b | 3 mal b | 3 mal b mod 7 |
|---|---|---|
| 1 | 3 | 3 |
| 2 | 6 | 6 |
| 3 | 9 | 2 |
| 4 | 12 | 5 |
| 5 | 15 | 1 |
| 6 | 18 | 4 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Das Inverse mit Python prüfen
python3 -c "print(pow(3, -1, 7), 3 * 5 % 7)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Weiterführend: warum der ggT 1 sein muss
Suchen Sie das Inverse von 4 modulo 8, indem Sie 4 mal b mod 8 für b von 1 bis 7 ausrechnen. Es kommt nie 1 heraus.
Der ggT von 4 und 8 ist 4, nicht 1. Jedes Produkt 4 mal b ist durch 4 teilbar, der Rest durch 8 also auch. Warum kann dann nie 1 herauskommen?