Modulo und Restklassen

Wenn wir “normal” dividieren, erhalten wir eine Zahl. Beispielsweise \(\frac{8}{5} = 1.6\). Allerdings können wir mit Rest teilen, wodurch wir zusätzlich den Rest erhalten. Interessanterweise können wir mit Resten so rechnen, wie wir das von ganzen Zahlen gewohnt sind. Ausserdem taucht mit Rest rechnen – auch modulo rechnen genannt – in vielen Bereichen auf, beispielsweise Kryptographie, Algorithmik, Mathe, u.v.m. Deshalb schauen wir uns genauer an, wie modulo rechnen funktioniert.

Rechnen modulo n

Wie in der Einleitung können wir für Zahlen den Rest bestimmen. Meistens geht das ohne Probleme. Damit wir mit ihnen rechnen können, müssen wir zürst ueberlegen, wann zwei Zahlen den gleichen Rest haben. Dafür nehmen wir uns ein konkretes Beispiel, und zwar Uhrzeiten. An einer Uhr kann man Minuten ablesen. Diese gehen von \(0\) bis \(59\). Somit rechnen wir bei Minuten modulo \(60\).

Bei welchen Anzahlen von Minuten steht der Zeiger an der gleichen Stelle? Beispielsweise bei \(0\) und \(60\) Minuten, oder \(5\) und \(65\) Minuten. Wir sehen also, dass Zahlen, die sich um \(60\) unterscheiden den gleichen Rest haben. Das ist eine gute Beobachtung, allerdings noch nicht alles. Nicht nur haben \(0\) und \(60\) den gleichen Rest, \(0\) und \(120\) haben auch den gleichen Rest. Dementsprechend haben nicht nur Zahlen die sich um \(60\) unterscheiden den gleichen Rest, sondern Zahlen, die sich um ein Vielfaches von \(60\) unterscheiden.

Das liefert uns direkt eine Definition. Und zwar haben zwei Zahlen \(a\) und \(b\) den gleichen Rest modulo \(n\), wenn \(n\) die Differenz von \(a\) und \(b\) teilt. Sobald die Differenz durch \(n\) teilbar ist, wissen wir, dass die Differenz ein Vielfaches von \(n\) ist. Es folgt die formale Definition.

\[ a \equiv b \mod n :\iff n | (a - b) \]

Mit dieser Definition assoziieren wir alle Zahlen miteinander, die den selben Rest haben. Unsere vorherigen Beispiele für Minuten mit demselben Rest können wir jetzt prägnanter schreiben. Dass \(60\) und \(0\) Minuten den selben Rest haben, drücken wir durch \(60 \equiv 0 \mod 60\) aus. Damit Du dich an die Denkweise und das Rechnen gewöhnen kannst, sind hier einige Beispiele. Welche sind richtig, welche sind falsch?

1. \(10 \equiv 12 \mod 3\)
2. \(7 \equiv 25 \mod 9\)
3. \(3 \equiv -7 \mod 5\)
4. \(2^n \equiv 2^{n+2} \mod 4\)

Restklassen

Zu Beginn sagte ich, dass wir “mit Resten rechnen können”. Tatsächlich ist es egal, ob wir zuerst addieren und dann den Rest berechnen, oder ob wir die Reste zweier Zahlen direkt addieren. Addiere ich \(7\) und \(64\) Minuten, so erhalte ich \(71\), was Rest \(11\) hat. Berechne ich zuerst die Reste, so hat \(64\) Rest \(4\). Addieren wir \(7\) und \(4\) erhalten wir wieder \(11\). Intuitiv sehen wir, dass man mit Resten rechnen kann. Allerdings haben wir noch nicht bewiesen, dass man das tun kann. Deshalb übersetzen wir unsere Intuition jetzt in eine mathematische Definition.

Zuerst wollen wir alle Zahlen mit demselben Rest “gleich behandeln”. Dafür fassen wir alle Zahlen mit demselben Rest in einer Restklasse zusammen. Somit enthält die Restklasse von \(3\), geschrieben als \([3]\), alle Zahlen mit Rest \(3\). Also \([3] := \{x \in \mathbb{Z} : 3 \equiv x \mod n\}\). Als nächstes beweisen, dass man mit Restklassen rechnen kann. Konkret soll die folgende Gleichung gelten.

\[ [a] + [b] = [a+b] \]

Auf der linken Seite addieren wir Reste miteinander, auf der rechten Seite berechnen wir den Rest der Summe. Wenn diese Gleichung immer stimmt, dann haben wir gezeigt, dass wir mit Resten rechnen können. Wie stellen wir das an? Hier müssen wir die Wohldefiniertheit zeigen. Das bedeutet, dass ich mit unterschiedlichen Zahlen aus den Restklassen rechnen kann, und dennoch das gleiche Ergebnis kriege. Wir müssen also zeigen, dass wenn \([a] = [a’]\) und \([b] = [b’]\), dann ist auch \([a+b] = [a’+b’]\). Den Beweis gehen wir nun durch.

Wir nehmen zwei Dinge an: \([a] = [a’]\) und \([b] = [b’]\). Zu zeigen ist, dass \([a+b] = [a’+b’]\). Unsere beiden Annahmen können wir anders schreiben, indem wir die Definition von Restklassen nutzen. Damit erhalten wir \([a] = [a’] \iff a’ = a + kn\) und \([b] = [b’] \iff b’ = b + ln\). Was wir zeigen müssen ist \(a’ + b’ = (a+b) * kn\), da das identisch ist zu \([a+b] = [a’+b’]\). Fangen wir an, umzuformen. Zuerst setzen wir die Definition ein.

\[ a’ + b’ = (a + kn) + (b + ln) \]

Dann vertauschen wir \(b\) und \(kn\), und klammern \(kn + ln\) aus.

\[ (a + kn) + (b + ln) = (a + b) + (k + l)n \]

Damit sind wir fertig. Auf der rechten Seite haben wir \((a+b)\) und ein Vielfaches von \(n\). Damit hat \((a’ + b’)\) den gleichen Rest, wie \((a+b)\). Als letztes bleibt zu sagen, dass man mit Restklassen auch subtrahieren, multiplizieren und dividieren kann. Das dividieren ist aber ein Sonderfall, für den man den euklidischen Algorithmus braucht.

Inverse & Euklidischer Algorithmus

Gegeben eine Zahl \(x\), ist ein Inverses das \(x^{-1}\), welches die Gleichung \(xx^{-1} = 1\) loest. Anders ausgedrueckt suchen wir eine Zahl, die mit \(x\) multipliziert \(1\) ergibt. Wenn wir mit Bruechen Rechnen, dann ist das sehr einfach, \(x^{-1} = \frac{1}{x}\) ist die Loesung. Rechnen wir allerdings modulo \(n\), so haben wir keine Brueche. Dementsprechend muessen wir fuer ein \(x\) berechnen, was das Inverse ist.

Fuer ein konkretes Beispiel sei \(x=3\) und \(n=7\). Wir wollen \(3\cdot y \equiv 1 \mod 7\) loesen. Hier koennen wir nicht einfach \(y=\frac{1}{3}\) setzen, da garnicht klar ist, was das sein soll. Stattdessen suchen wir eine Zahl zwischen \(0\) und \(6\), sodass die Gleichung erfuellt ist. Ausprobieren liefert uns hier, dass \(y = 5\) die Loesung ist. Zwei Fragen sind aber ungeklaert: 1. Existiert so ein Inverses immer? 2. Wie berechnet man es?

Zur Erinnerung, wir wollen wissen, ob \(a \cdot x \equiv 1 \mod n\) fuer ein gegebenes \(a\) eine Loesung besitzt. Die Frage ist also, ob wir \(1\) darstellen koennen als \(a \cdot x\). Tatsaechlich geht das nur, wenn \(a\) und \(n\) teilerfremd sind, sprich \(ggT(a, n) = 1\). Die Antwort liegt im erweiterten euklidischen Algorithmus.

Zuvor haben wir den euklidischen Algorithmus benutzt, um zu pruefen, ob zwei Zahlen teilerfremd sind. Im Grunde haben wir mit ihm den ggT berechnet. Dann haben wir gesehen, dass wir nicht nur den ggT berechnen koennen, sondern auch eine Darstellung des ggT durch Rueckeinsetzen erhalten. Im folgenden sind \(r, t \in \mathbb{Z}\).

\[ ggT(a, n) = ra + tn \]

Wenn nun \(ggT(a, n) = 1\), dann erhalten wir \(1 = ra + tn\). Was passiert, wenn wir jetzt modulo \(n\) rechnen? Ueber \(r\) und \(t\) koennen wir nichts aussagen, da ihre Werte von \(a\) und \(n\) abhaengen. \(a\) ist kleiner als \(n\), bringt uns auch nichts. Aber was ist \(n \mod n\)? Null. Daher ist \(tn \equiv t \cdot 0 \mod n\) und damit kongruent zu Null. Wenn wir \(\mod n\) rechnen streicht sich das \(tn\) raus. Wir erhalten:

\[ 1 = ra + tn \equiv ra \mod n \]

Damit haben wir ein Inverses gefunden. Warum? Wir haben \(1 \equiv ra \mod n\), und wir kennen \(r\). Damit ist \(r\) per Definition das Inverse von \(a\) mod \(n\). Wenn \(ggT(a, n) = 1\), dann liefert uns der euklidische Algorithmus ein Inverses.

Sobald \(ggT(a, n) \neq 1\) berechnet der euklidische Algorithmus kein Inverses mehr. Stattdessen erhalten wir ein \(k\), sodass \(ak \equiv ggT(a, n) \mod n\). Stellt sich die Frage, ob es dennoch ein Inverses gibt? Tatsaechlich nein. Der \(ggT(a, n)\) ist naemlich genau die kleinste Zahl mit einer Darstellung \(ak + nl\). Somit kann es kein Inverses geben.