 |
|||
| HSG |
|
Richtig gerechnet?
- 17 + 19 = 12
- 5 + 42 = 23
- 7 + 9 = 16
- 77 + 9 = 14
Uhrenaddition - www.inf-schule.de
Definition
Unsere Beobachtung bei Uhrzeiten zeigen, dass in gewisser Weise zwei Zahlen als gleich angesehen werden können, wenn sie sich nur um ein Vielfaches einer festen Zahl unterscheiden. So kann man z.B. 89 und 41 bezüglich 24 als gleich ansehen, weil 89 = 41 + 2*24 gilt. Trotzdem sind uns Uhrzeiten wie 41 Uhr ungeläufig. Hier ist es üblich, auf den Bereich 0-24 umzurechnen. In diesem Sinn sind dann 17, 41 und 89 gleich.
>>> 17%24 17 >>> 41%24 17 >>> 89%24 17 >>> -7%24 17
Erinnerung
Eine ganze Zahl b heißt durch eine ganze Zahl a teilbar, wenn es eine ganze Zahl q gibt mit \[ a = q \cdot b \] Kurz schreibt man für diesen Sachverhalt: \[ a \mid b \] und liest "a teilt b" oder "a ist ein Teiler von b"
Definition
\( a,b,m \in \mathbb{N}, \; a \equiv b (m) : \Leftrightarrow m \mid (a-b) \)
Hinweis
Zur Definition von Kongruenz und Teilbarkeit wird man z.B. bei wikipedia fündig.
Satz 0
\( a,b,m \in \mathbb{N}, \; m \mid (a-b) \Leftrightarrow a \text{ und } b \text{ haben bei der Division durch } m \text{ den gleichen Rest } r \)
Aufgabe 1: Bin ich ein Sonntagskind?
Sonntagskinder kommen in Märchen und Sagen vor:
... Hans lud den Stein auf und ging mit vergnügtem Herzen weiter; seine Augen leuchteten vor Freude, 'ich muß in einer Glückshaut geboren sein,' rief er aus 'alles, was ich wünsche, trifft mir ein, wie einem Sonntagskind.' ...
In der Gegend von Metnitz erhebt sich eine steile Felswand, die an ihrem Fuß eine grottenartige Vertiefung zeigt. Hier soll der Zugang zu einem ungeheuren Schatz im Innern des Felsens sein. Aber nur ein Sonntagskind kann in der Pfingstsonntagnacht zu den verborgenen Reichtümern gelangen; denn nur ein solches hat Macht über die unterirdischen Geister, die jene Schätze bewachen. ...
Überprüfe, ob du ein Sonntagskind bist. Wenn du keins bist, so lies den wikipedia-Artikel und entscheide dann, ob das so schlimm ist.
Rechnen mit Restklassen
Man kann zur Definition der Addition, Multiplikation und Potenzierung beliebige Repräsentaten einer Restklasse aussuchen. Wenn man Pech hat, so hängt das Resultat von der speziellen Wahl ab. Tatsächlich ist das aber nicht so. Die Festlegungen sind wohldefiniert, was natürlich bewiesen werden müsste.
Beispiele
3*5 ≡ 15 ≡ 1 (7)
3 ≡ 17 (7) und 5 ≡ 26 (7), 17*26 ≡ 442 ≡ 1 (7)
Rechengesetze in Python-Notation
- (a + b)%m = (a%m + b%m)%m
- (a * b)%m = (a%m * b%m)%m
- (a**k)%m = ((a%m)**k)%m
Dabei sind a, b und m natürliche Zahlen.
Die ersten beiden Gesetze sind leicht nachzurechnen. Dazu einfach a = qa*m+ra und b = qb*m+rb addieren bzw. multiplizieren und anschließend überlegen, welche Reste auf beiden Seiten der Gleichung bleiben können. Die Gesetze sind auch anschaulich gut zu verstehen, z.B. mit Hilfe der Seite 4 der Datei Restklassen von Herrn Dr. Feldhoff. Auch das dritte Gesetz kann mit Hilfe von ak = (qa*m+ra)k verstanden werden. Dazu überlegt man sich, welche Teilprodukte nach dem Ausmultiplizieren sicher durch m teilbar sind.
Aufgabe 0
Schreibe eine Python-Funktion aTafel(m), die zu einem Modul m eine 'Additionstafel' mit allen möglichen Additionen ausgibt. In diesem Zusammenhang lohnt sich ein Blick in die Format Specification Mini-Language.
>>> aTafel(4) + | 0 1 2 3 ---+------------ 0 | 0 1 2 3 1 | 1 2 3 0 2 | 2 3 0 1 3 | 3 0 1 2
Additives Inverses
Das additive Inverse -a zu a existiert immer und lässt sich leicht über -a = m-a berechnen.
Beispiel: a = 3, m = 7, -a = 7-3 = 4, (3+4)%7 = 0
Multiplikatives Inverses
Das multiplikative Inverse a-1 existiert nicht immer.
Beispiel 1: a = 3, m = 7, a-1 = 5, (3*5)%7 = 1
Beispiel 2: a = 2, m = 10, a-1 existiert nicht.
>>> (2*0)%10 0 >>> (2*1)%10 2 >>> (2*2)%10 4 >>> (2*3)%10 6 >>> (2*4)%10 8 >>> (2*5)%10 0 >>> (2*6)%10 2 >>> (2*7)%10 4 >>> (2*8)%10 6 >>> (2*9)%10 8
Man sieht, dass es beim Rechnen mit Resten vorkommen kann, dass ein Produkt Null ergibt, ohne dass mindestens ein Faktor Null sein muss. In obigem Beispiel gilt 2*5 =10 0. =10 soll dabei bedeuten, dass die linke und die rechte Seite der Gleichung gleich sind, wenn man die Reste nach der Division durch 10 betrachtet. In der Mathematik sagt man statt a =m b 'a und b sind kongruent modulo m' und schreibt ' a ≡ b mod m'. 2*5 ≡ 0 mod 10 ergab sich hier, weil 2 ein Teiler des Moduls 10 ist.
Gibt es zu 5 ein modulares Inverses, wenn m = 12 ist?
Weitere Folgerungen
Mit Hilfe des einfachen Programms tafeln.py kann man sich schnell Multiplikationstafeln erstellen lassen.
>>> mTafel(2) * | 0 1 ---+------ 0 | 0 0 1 | 0 1 >>> mTafel(3) * | 0 1 2 ---+--------- 0 | 0 0 0 1 | 0 1 2 2 | 0 2 1 >>> mTafel(4) * | 0 1 2 3 ---+------------ 0 | 0 0 0 0 1 | 0 1 2 3 2 | 0 2 0 2 3 | 0 3 2 1 >>> mTafel(5) * | 0 1 2 3 4 ---+--------------- 0 | 0 0 0 0 0 1 | 0 1 2 3 4 2 | 0 2 4 1 3 3 | 0 3 1 4 2 4 | 0 4 3 2 1 >>> mTafel(6) * | 0 1 2 3 4 5 ---+------------------ 0 | 0 0 0 0 0 0 1 | 0 1 2 3 4 5 2 | 0 2 4 0 2 4 3 | 0 3 0 3 0 3 4 | 0 4 2 0 4 2 5 | 0 5 4 3 2 1 >>> >>> mTafel(7) * | 0 1 2 3 4 5 6 ---+--------------------- 0 | 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 2 | 0 2 4 6 1 3 5 3 | 0 3 6 2 5 1 4 4 | 0 4 1 5 2 6 3 5 | 0 5 3 1 6 4 2 6 | 0 6 5 4 3 2 1 >>> mTafel(8) * | 0 1 2 3 4 5 6 7 ---+------------------------ 0 | 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 2 | 0 2 4 6 0 2 4 6 3 | 0 3 6 1 4 7 2 5 4 | 0 4 0 4 0 4 0 4 5 | 0 5 2 7 4 1 6 3 6 | 0 6 4 2 0 6 4 2 7 | 0 7 6 5 4 3 2 1 >>> mTafel(9) * | 0 1 2 3 4 5 6 7 8 ---+--------------------------- 0 | 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 2 | 0 2 4 6 8 1 3 5 7 3 | 0 3 6 0 3 6 0 3 6 4 | 0 4 8 3 7 2 6 1 5 5 | 0 5 1 6 2 7 3 8 4 6 | 0 6 3 0 6 3 0 6 3 7 | 0 7 5 3 1 8 6 4 2 8 | 0 8 7 6 5 4 3 2 1 >>> mTafel(10) * | 0 1 2 3 4 5 6 7 8 9 ---+------------------------------ 0 | 0 0 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 8 9 2 | 0 2 4 6 8 0 2 4 6 8 3 | 0 3 6 9 2 5 8 1 4 7 4 | 0 4 8 2 6 0 4 8 2 6 5 | 0 5 0 5 0 5 0 5 0 5 6 | 0 6 2 8 4 0 6 2 8 4 7 | 0 7 4 1 8 5 2 9 6 3 8 | 0 8 6 4 2 0 8 6 4 2 9 | 0 9 8 7 6 5 4 3 2 1 >>>
Beobachtungen an den Verknüpfungstafeln
0-Zeilen und 1-Zeilen sind nicht interessant. Die weiteren a-Zeilen lassen sich in zwei Gruppen einteilen. Solche die außer der ersten selbstverständlichen Null eine weitere Null enthalten und solche, die keine weitere Null enthalten. Die Zeilen mit weiterer Null zeigen eine interessante Periodizität, wobei die Perioden genau in die Zeilen passen. Genauer, die Periodenlänge teilt die Zeilenlänge, die natürlich m (m Modul) lang ist. Eine Zeile mit weiterer 0 enthält keine 1 und eine Zeile ohne weitere Null enthält genau eine Eins. Enthält eine Zeile eine Eins, so kommen alle Reste genau einmal vor (vollständiges Restesystem). Die Reihenfolge der Reste ist scheinbar zufällig.
Vermutung
Von welcher Art eine a-Zeile ist hat mit dem ggT(a,m) = (a,m) zu tun. Welche Vermutung drängt sich auf?
Fragen
Hat 5 bezüglich m=9 ein modulares Inverses? Wie sieht es mit 6 aus? Wann kommt in einer Zeile mehr als eine Null vor? Wie sieht es dann mit dem modularen Inversen aus?
Welcher Satz kann über die Existenz des modularen Inversen vermutet werden?
Satz 1
(a,m) > 1 ⇒ (1) m/(a,m) ist eine ganze Zahl < m; (2) m/(a,m) | m; (3) m/(a,m)⋅a = 0;
Beweis: (1) (a,m) ist ein Teiler von m, daher ist m/(a,m) eine ganze Zahl, (a,m) > 1 ⇒ 1 > 1/(a,m) ⇒ m > m/(a,m); (2) m = m/(a,m) ⋅ (a,m); (3) m/(a,m) ⋅ a = m ⋅ a/(a,m) und a/(a,m) ist ganze Zahl ⇒ m/(a,m) ⋅ a ist ein ganzzahliges Vielfaches von m ⇒ m/(a,m) ⋅ a ≡ 0 (m) ∎
Bemerkung: Mit Satz 1 ist noch nicht bewiesen, dass m/(a,m) die kleinste Zahl mit den angeführten Eigenschaften ist. Es ist ebenfalls noch offen, dass die 'a-Zeile' keine 1 enthält.
Hinführende Beispiele
\( 3 \cdot 6 \equiv 8 \cdot 6 (10) \text{ , aber } 3 \not\equiv 8 (10) \)
Die Rechnung 3⋅2⋅3 - 8⋅2⋅3 = q⋅2⋅5 zeigt aber, dass durch Kürzen durch 2 die Aussage 3⋅3 - 8⋅3 = q⋅5 zu retten ist. Die verbleibende 3 muss aber q teilen, sodass eine ganze Zahl q1 mit 3 - 8 = q1⋅5 existiert. Das bedeutet aber 3 ≡ 8(10/(10,6)).
3⋅13 ≡ 11⋅13 (8) , da 13 zu 8 teilerfremd ( (13,8) = 1 ) ist, gilt: 3 ≡ 11 (8)
Satz 2
\(a,b,c,m \in \mathbb{N}, \; a \cdot c \equiv b \cdot c (m) \Rightarrow a \equiv b(\frac{m}{(m,c)}) \)
Beweis: a⋅c ≡ b⋅c (m) ⇔ m | ac-bc ⇔ m | (a-b)c ⇔ (1) m/(m,c) | (a-b)⋅c/(m,c) , es gilt (m/(m,c),c/(m,c)) = 1 oder anders ausgedrückt: m/(m,c) und c/(m,c) haben keine gemeinsamen Primfaktoren, dann muss mit (1) auch (2) m/(m,c) | (a-b) gelten, (2) ⇔ a ≡ b (m/(m,c)) ∎
Beispiel zu Satz 2
a = 11, b = 6, c = 18, m = 15 (m,c) = ggT(15,18) = 3, m/(m,c) = 15/3 = 5 Voraussetzung: 11*18 = 6*18 mod 15 (198%15 = 3, 108%15 = 3) Behauptung: 11 = 6 mod 5 (11%5 = 1, 6%5 = 1)
Aufgabe 2
Finde je ein Beispiel zu Satz 2 mit (m,c) > 1 und (m,c) = 1.
Satz 3
(k,m) = 1 und a1, a2, ..., am ist vollständiges Restesystem bezüglich m ⇒ ka1, ka2, ..., kam ist vollständiges Restesystem bezüglich m
Beweis: Alle Reste kai sind paarweise verschieden. Angenommen, kar ≡ kas (m) und r ≠ s, dann folgt aus (k,m) = 1 und Satz 2, dass man durch k 'kürzen' darf und folglich ar ≡ as (m) gelten muss. Da die ai ein vollständiges Restesystem bilden, muss r = s gelten. Das ist ein Widerspruch. ∎
Folgerung
Eine 'a-Zeile' in einer Verknüpfungstafel modulo m enthält alle Reste, insbesondere auch eine 1, wenn (a,m) = 1 gilt.
Programm von Andrea Pfreundt: Modulo.zip
Links
- Kongruenz - wikipedia
- Teilbarkeit, Kongruenz modulo n - www.inf.fh-flensburg.de
- Rechnen in Restklassen - Dr. Hans-Joachim Feldhoff
- TeX - Handhabung
- LaTeX-Kompendium für Mathematiker