Das Rechnen mit Restklassen

Inhalt

Das Rechnen mit Restklassen

Wenn man mit Restklassen rechnet, so bedeutet dies, dass man nur mit dem „Rest“ rechnet, der nach einer ganzzahligen Teilung durch eine bestimmte Zahl übrigbleibt. Diese Zahl, durch die geteilt wird, nennt man den „Modul“ oder die „Modulzahl“. Wenn wir beispielsweise mit dem Teiler oder der Modulzahl 5 rechnen, sagen wir auch, „wir rechnen modulo 5“.

Wie das Rechnen mit Restklassen -- auch Modulo-Arithmetik oder Kongruenzrechnung genannt -- funktioniert, kann man sich gut klarmachen, wenn man sich das Zifferblattes einer Uhr vorstellt:

Um beispielsweise 3 + 2 zu rechnen, beginnen wir bei der Ziffer 2 und drehen den Zeiger um 3 Striche weiter (oder wir starten bei der 3 und drehen 2 Striche weiter, was natürlich auf dasselbe hinausläuft) Das Ergebnis ist 5.

Zählt man auf diese Weise 7 + 8 zusammen, erhält man 3. Denn 3 ist der Rest, wenn man 15 (also 7 + 8) durch 12 teilt. Um 5 mit 7 zu multiplizieren, beginnt man bei 0 und dreht 7 mal jeweils um 5 Striche weiter (oder auch bei 0 beginnend 5 mal um 7 Striche). In beiden Fällen bleibt der Zeiger bei 11 stehen. Denn 11 ist der Rest, wenn 35 (also 7 * 5) durch 12 geteilt wird.

Beim Rechnen mit Restklassen addieren und teilen wir Zahlen also nach den normalen Regeln der Alltagsarithmetik, verwenden dabei jedoch immer nur den Rest nach der Teilung. Um anzuzeigen, dass wir nach den Regeln der Modulo-Arithmetik und nicht nach denen der üblichen Arithmetik rechnen, schreibt man den Modul (Sie wissen schon -- den Teiler) dazu. Man sagt dann zum Beispiel „4 modulo 5“, schreibt aber kurz „4 mod5“.

Bei Modulo-5 zum Beispiel hat man dann eine Uhr, auf deren Zifferblatt es nur die 0, 1, 2, 3 und 4 gibt. Also:

4 mod5 + 3 mod5 = 7 mod5 = 2 mod5

Anders ausgedrückt, ist in der Modulo-5 Arithmetik das Ergebnis aus 4 plus 3 gleich 2. Wir können also auch schreiben:

9 mod5 + 7 mod5 = 16 mod5 = 1 mod5

Wir sehen auch, dass es egal ist, in welcher Reihenfolge wir vorgehen, weil wir nämlich auch schreiben können:

9 mod5 + 7 mod5 = 4 mod5 + 2 mod5 = 6 mod5 = 1 mod5

Denn 4 ist dasselbe wie 9, und 2 dasselbe wie 7, da wir uns ja nur für den jeweiligen Rest nach der Teilung durch 5 interessieren. Daran wird deutlich, dass wir bei dieser Art der Arithmetik jederzeit 5 oder ein Vielfaches von 5, wie 10, 15 und so weiter nehmen können,und das Ergebnis stets dasselbe ist.

Das funktioniert auch beim Multiplizieren (Malnehmen).

Ein Beispiel:

4 mod5 * 2 mod5 = 8 mod5 = 3 mod5

Ebenso können wir schreiben:

9 mod5 * 7 mod5 = 63 mod5 = 3 mod5

da wir einfach 60, also 5 * 12, abziehen können.

Man könnte aber auch schreiben:

9 mod5 * 7 mod5 = 4 mod5 * 2 mod5 = 8 mod5 = 3 mod5

denn 4 entspricht 9, und 2 entspricht 7, wenn wir nur den Rest nach Teilung durch 5 betrachten.

Widerum stellen wir fest, dass es egal ist, wenn wir das Vielfache von 5 einfach weglassen.

Da dadurch alles einfacher wird, machen wir das, bevor wir Zahlen addieren oder multiplizieren. Das bedeutet, dass wir uns lediglich um die Zahlen 0, 1, 2, 3 und 4 kümmern müssen, wenn wir mit der Modulo-5 Arithmetik rechnen. Denn wir können ja alles, was durch 5 teilbar ist, weglassen. Dazu noch drei Beispiele:

5 mod11 * 3 mod11 = 15 mod11 = 4 mod11

2 mod7 * 4 mod7 = 1 mod7

13 mod17 * 11 mod17 = 7 mod17

Das letzte Beispiel wird klar, wenn man bedenkt, dass in normaler Arithmetik gerechnet 13 * 11 = 143 und 143 = 8 * 17 + 7 ist.

Das Rechnen mit Restklassen

Inhalt