Hauptinhalt

Was ist modulare Arithmetik?

Eine Einführung in die modulare Arithmetik

Wenn wir zwei ganze Zahlen dividieren, erhalten wir eine Gleichung, die wie folgt aussieht:

$\frac{A}{B} = Q remainder R$ ‍

A

ist der Dividend

B

ist der Divisor

Q

ist der Quotient

R

ist der Rest

Wenn wir

A

durch

B

dividieren sind wir manchmal nur am Rest interessiert (und nicht am Ergebnis, dem Quotienten).
Für diese Fälle existiert ein Operator, den man den modulo Operator nennt (abgekürzt als mod).

Mit dem gleichen

A

B

Q

und

R

wie oben haben wir:

A mod B = R

Wir würden sagen, dass

A

modulo

B

gleich

R

ist. Wobei man

B

als den Modulus bezeichnet.

Zum Beispiel:

$\begin{array}{rcl} \frac{13}{5} & = & 2 Rest 3 \\ 13 mod 5 & = & 3 \end{array}$ ‍

Modulo mit Uhren visualisieren

Beobachte, was passiert, wenn wir Zahlen um eins erhöhen und sie dann durch 3 dividieren.

$\begin{array}{rcl} \frac{0}{3} & = & 0 Rest 0 \\ \frac{1}{3} & = & 0 Rest 1 \\ \frac{2}{3} & = & 0 Rest 2 \\ \frac{3}{3} & = & 1 Rest 0 \\ \frac{4}{3} & = & 1 Rest 1 \\ \frac{5}{3} & = & 1 Rest 2 \\ \frac{6}{3} & = & 2 Rest 0 \end{array}$ ‍

Die Reste beginnen bei 0 und werden jedes Mal um 1 erhöht, bis die Anzahl eins weniger ist als die Zahl, durch die geteilt durch. Danach wird die Sequenz wiederholt.

Wenn wir das wissen, können wir den modulo-Operator mit einem Kreis visualisieren.

Wir schreiben 0 an den oberen Rand eines Kreises und weiter im Uhrzeigersinn die Zahlen 1,2,... bis um 1 kleiner als der Modulus.

Beispielsweise wäre eine Uhr, bei der die 12 durch eine 0 ersetzt ist der Kreis für ein Modul von 12.

Um das Resultat von

A mod B

zu ermitteln, führen wir folgende Schritte durch:

Baue eine Uhr für die Größe $B$ ‍
Beginne bei 0 und bewege dich in $A$ ‍ Schritten rund um die Uhr
Wo immer wir landen, ist unsere Lösung.

(Wenn die Zahl positiv ist, gehe im Uhrzeigersinn, wenn sie negativ ist, gehe gegen den Uhrzeigersinn.)

Beispiele

$8 mod 4 = ?$ ‍

Mit einem Modul von 4 machen wir eine Uhr mit den Zahlen 0, 1, 2, 3.
Wir beginnen bei 0 und gehen nacheinander im Uhrzeigersinn durch 8 Zahlen 1, 2, 3, 0, 1, 2, 3, 0

Wir landen bei 0 daher ist

8 mod 4 = 0

$7 mod 2 = ?$ ‍

Mit einem Modul von 2 machen wir eine Uhr mit Zahlen 0,1.
Wir beginnen bei 0 und gehen im Uhrzeigersinn durch 7 Zahlen 1,0,1,0,1,0,1.

Wir landen bei 1 daher ist

7 mod 2 = 1

$- 5 mod 3 = ?$ ‍

Mit einem Modul von 3 machen wir eine Uhr mit den Zahlen 0, 1, 2.
Wir beginnen bei 0 und gehen durch 5 Zahlen entgegen dem Uhrzeigersinn (5 ist negativ) 2, 1, 0, 2, 1.

Wir landen bei 1 daher ist

- 5 mod 3 = 1

Schlussfolgerung

Wenn wir

A mod B

haben und

A

um ein vielfaches von $B$ ‍ vergrößern, kommen wir zur gleichen Stelle, d.h.

$A mod B = (A + K \cdot B) mod B$ ‍ gilt für jede ganze Zahl $K$ ‍.

Zum Beispiel:

$\begin{array}{r} 3 mod 10 = 3 \\ 13 mod 10 = 3 \\ 23 mod 10 = 3 \\ 33 mod 10 = 3 \end{array}$ ‍

Hinweise für den Leser

mod in Programmiersprachen und Taschenrechnern

Viele Programmiersprachen und Taschenrechner, haben einen mod-Operator, dafür wird meistens ein %-Symbol verwendet. Wenn du das Ergebnis einer negativen Zahl berechnest, geben dir einige Programmiersprachen ein negatives Ergebnis.
z.B.

-5 % 3 = -2.

Kongruenz Modul

Du siehst vielleicht einen Ausdruck wie:

$A \equiv B (mod C)$ ‍

Dies bedeutet, dass

A

mit

B

mod

C

kongruent ist. Dies ist ähnlich wie die hier verwendeten Ausdrücke, aber nicht ganz gleich.

Im nächsten Artikel werden wir erklären, was das bedeutet und wie sich das auf die oben genannten Ausdrücke bezieht.

Willst du an der Diskussion teilnehmen?

Anmelden

Sortiere nach:

Noch keine Beiträge.

Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.

Informatik

Kurs: Informatik > Lerneinheit 2