Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

Beitrag_6_handball

Wie rechne ich mit Restklassen?

Max erzählt Rike, dass er am Sonntag mit seinen Sportfreunden den Sieg gefeiert hat. Sie hätten viel gelacht, ein paar Bier getrunken und plötzlich wusste er nicht mehr, was 1 und 1 ist.

Beitrag_6_Dialog

Rike Mein Papa hat mir mal erzählt, er hat auch 1 und 1 addiert. Die 1 steht in der Informatik für ein Ja. Früher haben sie das elektrisch und sogar mechanisch umgesetzt. Das kleinste nichttriviale System hat 2 Zustände: 0 und 1. Und die beiden Zustände können miteinander agieren, z.B., wenn wir hier zwei Flaschen haben, nehmen wir mal an, beide sind voll, ja, und wenn der Inhalt von beiden in eine soll, dann könnte das System das verweigern, also

\(1+1 = 0\)

Was wäre dann

\(1 + 0\;?\)

Max Ein Bier und kein Bier? Ein Bier!

\(1+0 = 1\)

Rike Und kein Bier und kein Bier?

Max Kein Bier!

\(0 + 0 = 0\)

Rike Ok, dann haben wir jetzt die Additionstabelle:

+01
001
110

Außerdem können wir multiplizieren, was meinst Du, einmal ein Bier?

Max

\(1 \cdot 1 = 1\)

Rike Ja, stimmt, und

\(0 \cdot 1 = \;?\)

Max

\(0 \cdot 1 = 0\)

Rike Und

\(0 \cdot 0 =\; ?\)

Max Ist doch klar,

\(0 \cdot 0 = 0\)

Rike Jetzt haben wir auch die vollständige Multiplikationstabelle:

·01
000
101

Mathematisch kann man sich für 0 gerade Zahlen und für 1 ungerade Zahlen vorstellen.

Max Ok, zwei gerade Zahlen addiert ergeben eine gerade, zwei ungerade addiert ergeben eine gerade:

\(1+1= 0\)

Naja, sieht ja etwas komisch aus!

Rike 0 und 1 stehen als Symbole für alle natürlichen oder ganzen Zahlen, du musst sie nur durch 2 teilen und nicht das Ergebnis nehmen, sondern den Rest. Man schreibt

\(1\;001 = 2 \cdot 500 + 1 \equiv 1\;mod\;2\)

oder

\(2\; 000\; 000 = 2 \cdot 1\; 000\; 000 + 0 \equiv 0\;mod\;2\)

Max Ok, cool, das könnten wir eigentlich immer machen.

Rike Man braucht das in der Zahlentheorie und der Kryptografie. Das nennt sich Rechnen mit Restklassen. Aber nicht nur zur Basis 2. Am besten eignen sich große Primzahlen, 9 419 kennst du ja schon.

Max Hm, jetzt hab ich das grad mit 0 und 1 kapiert, ich weiß nicht, aber vielleicht ist es doch ok für mich, hm, denn

\(2 \cdot 9\; 419 \equiv 2 \cdot 0 \equiv 0 \;mod\; 9\; 419.\)

Rike Ich fasse es nicht, du hasts verstanden!

* * *

Übungsaufgaben

Erstelle die vollständige Additions- und Multiplikationstabellen zur Basis \(q = 7\) und \(q = 8\).

Lösungen

Additionstabelle für \(q=7\):

+0123456
00123456
11234560
22345601
33456012
44560123
55601234
66012345

Multiplikationstabelle für \(q=7\):

·0123456
00000000
10123456
20246135
30362514
40415263
50531642
60654321

Additionstabelle für \(q=8\):

+01234567
001234567
112345670
223456701
334567012
445670123
556701234
667012345
770123456

Multiplikationstabelle für \(q=8\):

·01234567
000000000
101234567
202460246
303614725
404040404
505274163
606420642
707654321