Die mathematische Operation modulo bestimmt den Rest bei der Division einer ganzen Zahl n durch eine andere ganze Zahl k. Das Ergebnis von n modulo k liegt also im Bereich zwischen 0 und k-1.
Beispiel 1:
0 modulo 3 = 0 | 1 modulo 3 = 1 | 2 modulo 3 = 2 |
3 modulo 3 = 0 | 4 modulo 3 = 1 | 5 modulo 3 = 2 |
6 modulo 3 = 0 | ... |
Mathematisch ausgedrückt:
a modulo n = r mit n ≠ 0 und 0 < |r| < |n|.
Dabei gilt für den Rest "r" folgende Gleichung:
r = a - ⌊a / n⌋ * n
Dabei ist |x| der Betrag einer Zahl x; und ⌊x⌋ ist die nächstniedrigere ganze Zahl von x, wenn x nicht ganzzahlig ist.
Für negative Werte von a oder n kann man mit der obigen Gleichung den Rest r ebenfalls definieren.
In den meisten Programmiersprachen ist die Modulo-Operation auf die natürlichen Zahlen beschränkt. Z.B. ist in ANSI C der Modulo-Operator für negative Operanden nicht definiert. Man kann es selbst mit den Funktionen floor, ceil und abs definieren, sofern man math.h includiert.
Beispiel 2:
Mit der Definition der Restklassen (Kongruenzklassen) fasst man alle Zahlen
zusammen die denselben Rest ergeben.
7 ≅ 4 modulo 3, denn beide ergeben beim Teilen durch 3 den Rest 1.
Man sagt auch a=7 ist kongruent zu b=4 modulo 3
Zwei Zahlen a und b sind kongruent, wenn die Differenz (a-b) vom Modulus ohne Rest geteilt wird. So wird auch (25-(-1))=26 durch 26 geteilt.
Beispiel 3:
In der folgenden Tabelle werden nun die Zahlen a, die in dieselbe Restklasse modulo 26 gehören, untereinander geschrieben:
-26 |
-25 |
... |
-2 |
-1 |
0 |
1 |
... |
24 |
25 |
26 |
27 |
... |
50 |
51 |
Hier sieht man auch: Lässt man beim Berechnen von a modulo n für a nicht nur N
(alle natürlichen Zahlen plus 0) zu, sondern auch negative ganze Zahlen, dann
gilt: (-1) % 26 = 25.
-1 und 25 gehören also zur gleichen Restklasse, ebenso wie a=51 kongruent ist zu b=25, jeweils modulo 26. Alle drei Zahlen stehen in derselben Spalte.