Station - Modulare Gleichheit
Verallgemeinerte Uhrzeiten
Wir betrachten die Reise mit der Transsibirischen Eisenbahn. Bei Beginn der Reise in Moskau ist es 17 Uhr.
Nach 149 Stunden wird das Ziel Wladiwostok erreicht. Es ist jetzt (17+149) Uhr bzw. 166 Uhr. Das entspricht - auch im fernen Sibirien - 22 Uhr.
Man kann diese Uhrzeit leicht rechnerisch ermitteln, indem man den Rest bei der Division durch 24 ermittelt:
166 % 24 = 22
Uhrzeiten werden eigentlich nur mit den Zahlen 0, 1, ..., 23 angegeben. Im Alltag lässt man auch manchmal die Zahl 24 zu: 24 Uhr ist dasselbe wie 0 Uhr. Die 24 ist - zumindest bei Uhrzeitangaben - also gleich zu behandeln wie die 0.
Was könnte man unter 25 Uhr oder 31 Uhr oder 55 Uhr verstehen, wenn man entsprechend weiter verfahren würde? Die 25 würde man wie die 1 behandeln, die 31 wie die 7 und die 55 ebenfalls wie die 7.
31 Uhr und 55 Uhr (als verallgemeinerte Uhrzeiten) würden für dieselben Uhrzeiten stehen, weil der zyklisch sich drehende und immer wieder bei 0 beginnende Uhrzeiger dieselbe Stelle anzeigen würde. Rechnerisch zeigt sich das, indem beide Zahlen 31 und 55 denselben Rest bei der Division durch 24 hinterlassen.
Gleichheit modulo einer vorgegebenen Zahl
Vorgegeben sei eine natürliche Zahl n. Zwei natürliche Zahlen a und b heißen gleich modulo n bzw. kongruent modulo n genau dann, wenn sie beide den gleichen Rest bei der Division durch n erzeugen.
Beispiel: 31 und 55 sind gleich modulo 24, denn es gilt:
[31]%24 = 7 = [55]%24
Aufgabe 1
Welche der folgenden Zahlen sind gleich bezüglich der Operation modulo 13?
8, 14, 27, 31, 40, 47, 50, 52, 60, 65, 81
Aufgabe 2
(a) Markiere auf einem Zahlenstrahl sämtliche Zahlen, die bei der Division durch n = 6 den Rest 4 ergeben.
(b) Begründe (am Beispiel / allgemein) den folgenden Zusammenhang: Zwei natürliche Zahlen a und b sind gleich modulo einer vorgegebenen natürlichen Zahl n genau dann, wenn die Differenz der beiden Zahlen a und b ein Vielfaches von n ist.
Eine interessante Beobachtung
Beim Zählen modulo einer vorgegebenen Zahl wiederholt sich das Zählmuster immer wieder. Die folgende Übersicht zeigt die Zahlen, die beim üblichen Zählen entstehen, sowie die Zahlen, die beim Zählen modulo 3 bzw. 5 bzw. 15 entstehen:
n: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ... [n]%3: 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 ... [n]%5: 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 ... [n]%15: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 ...
Aufgabe 3
(a) Wie erkennt man in der Übersicht, dass zwei Zahlen a und b modulo 3 (bzw. modulo 5) gleich sind? Gib Beispiele für solche Zahlen an.
(b) Wie erkennt man in der Übersicht, dass zwei Zahlen a und b sowohl modulo 3 als auch modulo 5 gleich sind? Gib Beispiele für solche Zahlen an.
(c) Was fällt auf, wenn man Gleicheit modulo 3 und 5 sowie Gleichheit modulo 15 betrachtet?
Satz (über modulare Gleichheit bzgl. Primzahlen)
p und q seien zwei vorgegebene verschiedene Primzahlen. Wenn zwei natürliche Zahlen a und b sowohl gleich modulo p als auch gleich modulo q sind, dann sind sie auch gleich modulo p*q.
Anders formuliert:
Aus [a]%p = [b]%p und [a]%q = [b]%q folgt [a]%(p*q) = [b]%(p*q).
Die Begründung ist recht einfach. Gegeben seien zwei natürliche Zahlen a und b, die sowohl gleich modulo p als auch gleich modulo q sind. Wir gehen im Folgenden davon aus, dass a ≥ b gilt. Im Fall b ≥ a argumentiert man völlig analog.
Nach Aufgabe 2 können wir schließen, dass die Differenz a-b sowohl ein Vielfaches von p als auch ein Vielfaches von q ist. Also ist a-b = m*p und a-b = n*q mit zwei natürlichen Zahlen m und n.
Es folgt, dass m*p = n*q gelten muss.
Da p und q zwei verschiedene Primzahlen sind, muss p ein Teiler von n und q ein Teiler von m sein.
Es muss daher zwei natürliche Zahlen i und j geben mit n = i*p und m = j*q.
Setzt man in die Gleichung m*p = n*q ein, erhält man a-b = j*p*q und a-b = i*p*q.
Hieraus folgt jetzt (wieder mit Aufgabe 2), dass a und b gleich modulo p*q ist.
Aufgabe 4
Überprüfe mit Aufzählungen wie oben die Aussage des Satzes für die Primzahlen p = 2 und q = 7.
n: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ... [n]%2: [n]%7: [n]%14:
Aufgabe 5
Überprüfe die Aussage des Satzes mit Hilfe des folgenden Python-Programms. Variiere auch die vorgegebenen Primzahlen.
# vorgegebene Primzahlen
p = 3
q = 5
# Test auf modulare Gleichheit
for i in range(30):
for j in range(30):
if i%p == j%p and i%q == j%q:
print('i:', i, 'j:', j)
print('i%p = j%p:', i%p)
print('i%q = j%q:', j%q)
print('i%(p*q):', i%(p*q))
print('j%(p*q):', j%(p*q))
print()
