Modular arithmetic is a system of arithmetic for integers, where numbers wrap around when reaching a certain value, called the modulus.
Laut Wikipedia ist die mod. Ar. einer der Eckpfeiler der Zahlentheorie und greift nahezu alle Aspekte dieses Gebietes auf. Im Praktischen wird sie in der Kryptografie, IT generell als auch in der Chemie und visuellen und musikalischen Kunst aufgegriffen.
Die Basics
Die Modulare Arithmetik entstammt der Zahlentheorie, und genau deshalb können wir uns so einiges erlauben. Fangen wir damit an, dass in dieser Theorie nur mit Ganzzahlen ℤ = {...-3,-2,-1,0,1,2,3...} gearbeitet wird, und die Ergebnisse sogar nur natürliche Zahlen ℕ = {0,1,2,3,4,...} sein dürfen.
In der mod. Ar. gibt es zwar, so wie in jeder Zahlentheorie, Zeichen die einem bekannt vorkommen werden, jedoch haben diese eine ganz andere Art von Schritten, um zu Ergebnis zu kommen.
Die Modulararithmetik arbeitet mit dem Modulus, bzw. dem mod einer Zahl. Der mod ist der Rest nach einer Division. Wir schreiben (der Einfachheit zu liebe) beispielsweise 31 mod 7 = 3. 3 ist hier der Rest der Division 31:7 (= 4 und 3 Rest).
Klingt doch ganz einfach. Aber was passiert bei negativen Zahlen? Wieso ist -2 mod 5 = 3 und wie nutzt man Multi- und Division?
Bevor wir weiter in die Rechenregeln schauen müssen wir noch eines klarstellen: Die Restklassen, oder auch Äquivalenzklassen.
Äquivalenz-/Restklassen
Auch wenn man öfters Restklassen hören mag, ist der Alternativbegriff "Äquivalenzklassen" imo intuitiv logischer, denn in der mod. Ar. gibt es Klassen an Zahlen, die immer wieder denselben Werten entsprechen.
Unter mod 5 haben wir beispielsweise folgende fünf Restklassen:
ℤ₀ = {...,-15,-10,-5,0,5,10,15,...}
ℤ₁ = {...,-14, -9,-4,1,6,11,16,...}
ℤ₂ = {...,-13, -8,-3,2,7,12,17,...}
ℤ₃ = {...,-12, -7,-2,3,8,13,18,...}
ℤ₄ = {...,-11, -6,-1,4,9,14,19,...}
Bevor wir mit der Beschreibung beginnen noch ein Hinweis - wenn anstelle des normalen "=" ein "≡" verwendet wird, impliziert das, dass es sich dabei um eine Modulo Operation handelt.
Damit gilt beispielsweise, dass 18/3 ≡ 6 ≡ 1 bei mod 5 ist, wie auch 13/3 ≡ 1 mod 5 ist, da sich beide Werte in derselben Restlkasse ℤ₃ stammen. Wichtig zu sehen ist, dass die verschiedenen Werte einer Restklasse immer + bzw. - des Modulus (hier mod 5) gerechnet werden, also zb. 3,8,13,18 bei ℤ₃.
Man kann die Restklassen auch gut als Zahlenstrahl darstellen:
ℤ = -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | +1 | +2 | +3 | +4 | +5 | +6
mod5 (ℕ) = 3 | 4 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | 0 | 1
<-------|------------------------|------------------------|------->
Hier ist nun in jedem mod5-Abteil je ein Element jeder Restklasse (0 bis 4) enthalten, welches sich pro Abteil wiederholt. Damit erklären sich die identischen Werte und somit die zuvor dargestellten Restklassen. Restklassen werden übrigens Restklassen genannt, weil ihr Rest identisch ist.
Rechnen im System
Nachdem wir die Basics jetzt haben, gibt es noch ein paar Beispielrechnungen. Wichtig: hier ist zu bemerken, dass man entweder jedes Element für sich reduzieren (bzw. durch ein kleineres aus derselben Restklasse ersetzen, wir wissen ja, dass diese gleichwertig sind!) oder gleich das Modulo durchführen kann.
13+12 mod 5 ≡ 8+7 ≡ 3+2 ≡ 0
oder auch
13+12 mod 5 = 25 ≡ 0
13-12 mod 5 ≡ 8-7 ≡ 3-2 ≡ 1
oder auch
13-12 mod 5 = 1 ≡ 1
13*12 mod 5 ≡ 8*7 ≡ 3*2 ≡ 1
oder auch
13*12 mod 5 = 156 ≡ 1
Damit hätten wir vorerst mal alles für diese kurze Einführung geschafft! Die Division ist ein wenig komplizierter, aber auch mehr als machbar.
Kommentare
Kommentar veröffentlichen