Division mit Rest

Teilt man zwei ganze Zahlen a/b (mit b ungleich 0) erhält man eine ganze Zahl und einen ganzzahligen Rest (das Modulo). Ist der ganzzahlige Anteil des Quotienten q und der Rest r, so gilt stets q·b + r = a und 0≤r<b. Ist 0<a<b, so ist der Rest gleich b.

Beispiel:

Bei einer Division durch 3 kann der Rest die Werte 0, 1 oder 2 annehmen. Sehr anschaulich wird das, wenn man die Zahlen durch Striche ersetzt:

Division 7 durch 3:
7 : IIIIIII
3 : III
Jetzt kann man immer je 3 Striche zu einem Block gruppieren.
7 : III III I
Der letzte Block der entsteht bildet den Rest, dieser kann aus einem oder zwei Strichen bestehen. Sind nur Dreierblöcke vorhanden so ist der Rest gleich Null.

Diese Division funktioniert auch mit negativen Zahlen:

 7 :  3 =  2 Rest 1
-7 :  3 = -3 Rest 2
 7 : -3 = -2 Rest 1
-7 : -3 =  3 Rest 2

Man beachte, dass DIV- und MOD-Befehle (für ganzzahlige Division und Restbildung) in den meisten Programmiersprachen mit negativen Zahlen anders umgehen:

 7 :  3 =  2 Rest  1
-7 :  3 = -2 Rest -1
 7 : -3 = -2 Rest  1
-7 : -3 =  2 Rest -1

Division mit Rest ist jedoch nicht auf ganze Zahlen beschränkt, sondern auch für andere Ringe definiert. Ein Beispiel ist die Polynomdivision:

 (2 x^2 + 4 x + 5) : (x + 1) = 2 x + 2
  2 x^2 + 2 x
  -----------
          2 x + 5
          2 x + 2
          -------
                3

2x + 2 ist hierbei das Ergebnis und 3 der Rest. Hier ist der Rest stets ein Polynom von kleinerem Grad als der Divisor.

Ein Ring, in dem Division mit Rest möglich ist, heißt euklidischer Ring.