Division mit Rest

Wenn zwei natürliche Zahlen, der Dividend ${\displaystyle a}$ und der Divisor ${\displaystyle b}$ (ungleich 0), mit Rest dividiert werden sollen, wenn also

${\displaystyle a:b}$

berechnet werden soll, so wird gefragt, wie man die Zahl ${\displaystyle a}$ als Vielfaches von ${\displaystyle b}$ und einem „kleinen Rest“ darstellen kann:

${\displaystyle a=b\cdot c+r}$

Hier ist ${\displaystyle c}$ der sogenannte Ganzzahlquotient und ${\displaystyle r}$ der Rest. Entscheidende Nebenbedingung ist, dass ${\displaystyle r}$ eine der Zahlen ${\displaystyle 0,1,\dotsc ,b-1}$ ist. Hierdurch wird ${\displaystyle r}$ eindeutig bestimmt.

Der Rest ist also die Differenz zwischen dem Dividenden und dem größten Vielfachen des Divisors, das höchstens so groß ist wie der Dividend. Ein Rest ungleich 0 ergibt sich folglich genau dann, wenn der Dividend kein Vielfaches des Divisors ist. Man sagt auch: Der Dividend ist nicht durch den Divisor teilbar, weshalb ein Rest übrigbleibt.

Liegt der Divisor fest, so spricht man beispielsweise auch vom Neunerrest einer Zahl, also dem Rest, der sich bei Division dieser Zahl durch neun ergibt.

Ist ${\displaystyle b}$ eine negative ganze Zahl, dann gibt es keine natürlichen Zahlen zwischen 0 und ${\displaystyle b-1}$, die für den Rest ${\displaystyle r}$ in Frage kämen. Unter den vielen Möglichkeiten sind die folgenden drei die interessantesten:

1. Stattdessen kann man fordern, dass der Rest ${\displaystyle r}$ zwischen 0 und ${\displaystyle |b|-1}$ (dem Betrag von ${\displaystyle b}$ minus 1) liegt.
2. Alternativ kann man aber auch verlangen, dass der Rest ${\displaystyle r}$ zwischen ${\displaystyle b+1}$ und 0 liegt, also dasselbe Vorzeichen hat wie ${\displaystyle b.}$
3. Eine dritte Möglichkeit ist, den betragskleinsten Rest ${\displaystyle r}$ zu wählen. Diese Variante liefert für ${\displaystyle a=b\cdot c+r}$ die beste Näherung ${\displaystyle b\cdot c}$ für ${\displaystyle a.}$

 7 : 3 = 2 Rest 1
−7 : 3 = −2 Rest −1

 7 : −3 = −2 Rest 1
−7 : −3 = 2 Rest −1

 7 : 3 = 1 Rest 4
 7 : 3 = 2 Rest 1
 7 : 3 = 3 Rest −2

−7 : 3 = −1 Rest −4
−7 : 3 = −2 Rest −1
−7 : 3 = −3 Rest 2

 7 : 3 = 2 Rest 1
−7 : 3 = −3 Rest 2
 7 : −3 = −3 Rest −2
−7 : −3 = 2 Rest −1

Modulo berechnet den Rest ${\displaystyle b}$ der Division ${\displaystyle n}$ geteilt durch ${\displaystyle m}$. Man kann eine Funktion definieren, die jedem Zahlenpaar ${\displaystyle (n,m)}$ einen eindeutigen Teilerrest ${\displaystyle b}$ zuordnet. Diese nennt man Modulo (von lat. modulus, Kasus Ablativ, also: ‚(gemessen) mit dem (kleinen) Maß (des …)‘[1]) und kürzt sie meistens mit mod ab.

In Programmiersprachen, die B-Abkömmlinge sind, wie C oder Java, wird die Funktion durch % (Prozentzeichen) dargestellt und als Operator behandelt.[2] Frühe Programmiersprachen kannten den Operator mod noch nicht, nur den Datentyp des ganzzahligen Werts integer (abgekürzt INT); darum wurde der Divisionsrest nach der Formel ${\displaystyle {\bigg (}{\frac {n}{m}}-{\texttt {INT}}\left({\frac {n}{m}}\right){\bigg )}\cdot m}$ errechnet und wegen der damaligen Rechenungenauigkeit beim Dividieren dann auf den ganzzahligen Wert gerundet.

Wir betrachten die Funktion

${\displaystyle \operatorname {mod} \colon \mathbb {Z} \times (\mathbb {Z} \setminus \{0\})\to \mathbb {Z} ,\quad (a,m)\mapsto a{\bmod {m}}:=a-\left\lfloor {\frac {a}{m}}\right\rfloor \cdot m.}$

Die Gaußklammer ${\displaystyle \lfloor \cdot \rfloor }$ bezeichnet die größte ganze Zahl, die nicht größer als die Zahl in der Gaußklammer ist, also, falls positiv, der ganze Anteil ohne die Nachkommastellen. Hier gilt stets

${\displaystyle (a+km){\bmod {m}}=a{\bmod {m}}}$ für alle ${\displaystyle k\in \mathbb {Z} ,}$

aber im Allgemeinen ist

${\displaystyle (-a){\bmod {m}}\neq -(a{\bmod {m}}),}$ z. B. ${\displaystyle (-2){\bmod {3}}=1\neq -2=-(2{\bmod {3}}).}$

Ist ${\displaystyle m}$ positiv, so ist ${\displaystyle a{\bmod {m}}\geq 0}$ für alle ${\displaystyle a.}$

Neben dieser „mathematischen Variante“ wird oft auch eine ähnliche Funktion als Modulo bezeichnet, die für negative Argumente unterschiedliche Ergebnisse liefert und „symmetrische Variante“ genannt wird:

${\displaystyle (a{\bmod {m}}):=a-m\cdot (a\,\operatorname {div} \,m)}$

Dabei bezeichnet ${\displaystyle a\,\operatorname {div} \,m}$ den zur Null hin gerundeten Quotienten ${\displaystyle a\,/\,m}$, gegeben durch ${\displaystyle a\,\operatorname {div} \,m=\operatorname {sgn}(a)\;\operatorname {sgn}(m)\left\lfloor {\frac {|a|}{|m|}}\right\rfloor }$, wobei ${\displaystyle \operatorname {sgn}(x)}$ die Vorzeichenfunktion bezeichnet. Für diese Variante gilt

${\displaystyle (-a){\bmod {m}}=-(a{\bmod {m}}),}$

aber im Allgemeinen

${\displaystyle (a+km){\bmod {m}}\neq a{\bmod {m}},}$ z. B. ${\displaystyle (1-3){\bmod {3}}=(-2){\bmod {3}}=-2\neq 1=1{\bmod {3}}.}$

${\displaystyle a{\bmod {m}}}$ hat stets dasselbe Vorzeichen wie ${\displaystyle a}$, oder es gilt ${\displaystyle a{\bmod {m}}=0}$.

Gilt ${\displaystyle a\geq 0}$ und ${\displaystyle m>0}$, so ergeben beide Varianten dasselbe Ergebnis. In Programmiersprachen ist die implementierte Variante nicht einheitlich. So verwenden Ruby, Perl, Python, Excel und der Rechner der Googlesuche die mathematische Variante, wohingegen C, Java, JavaScript und PHP die symmetrische einsetzen, was besonders wichtig bei Portierungen ist.

Steht in einer Sprache wie C(++) oder Java nur die symmetrische Variante zur Verfügung, kann man Ergebnisse nach der mathematischen Variante erhalten mit:

${\displaystyle a{\bmod {b}}}$ = ((a % b) + b) % b,

wobei % die symmetrische Modulooperation bezeichnet und ${\displaystyle \operatorname {mod} }$ die mathematische.

Ist die Zahl m eine Primzahl, so kann man die aus den reellen Zahlen gewohnten Grundrechenarten mit anschließender Modulo-Berechnung anwenden und erhält einen sogenannten endlichen Körper.

Sind ${\displaystyle a}$ und ${\displaystyle b}$ reelle Zahlen, ${\displaystyle a}$ ungleich 0, dann kann man eine Division mit Rest folgendermaßen definieren: Der ganzzahlige Quotient ${\displaystyle c}$ und Rest ${\displaystyle r}$ im halboffenen Intervall ${\displaystyle [0,|b|)}$ sind diejenigen (eindeutig bestimmten) Zahlen, die die Gleichung ${\displaystyle a=b\cdot c+r}$ erfüllen.

Auch hier gibt es die Alternativen, dem Rest dasselbe Vorzeichen wie ${\displaystyle b}$ zu geben oder den betragskleinsten Rest zu wählen. Letztere Alternative entspricht der Rundung: Die Division mit Rest von ${\displaystyle a}$ durch 1 liefert eine ganze Zahl ${\displaystyle c}$ und eine reelle Zahl ${\displaystyle r}$ mit Betrag kleiner oder gleich 1/2, die die Gleichung ${\displaystyle a=c+r}$ erfüllen. Die Zahl ${\displaystyle c}$ ist der auf ganze Zahlen gerundete Wert von ${\displaystyle a}$.

Es ist zu beachten, dass hierbei der Quotient nicht aus derselben Menge (der reellen Zahlen) genommen wird wie Divisor und Dividend.

Bei der Division mit Rest für Polynome muss das als Divisor auftretende Polynom ${\displaystyle f(X)}$ aus dem Polynomring ${\displaystyle R[X]}$ (über ${\displaystyle R}$, einem kommutativen Ring mit ${\displaystyle 1}$) eine Voraussetzung erfüllen: Der Leitkoeffizient von ${\displaystyle f(X)}$ muss eine Einheit von ${\displaystyle R}$ sein (insbes. ist ${\displaystyle f(X)}$ nicht das Nullpolynom). Unter dieser Bedingung gibt es zu jedem ${\displaystyle g(X)\in R[X]}$ eindeutig bestimmte Polynome ${\displaystyle q(X),r(X)\in R[X]}$ mit

${\displaystyle g(X)=q(X)\cdot f(X)+r(X)}$

${\displaystyle \operatorname {deg} (r)<\operatorname {deg} (f)}$

Dabei wird dem Nullpolynom ein kleinerer Grad als jedem anderen Polynom gegeben, beispielsweise ${\displaystyle -\infty }$.

Beispiel

${\displaystyle 2X^{2}+4X+5=(2X+2)(X+1)+3\in \mathbb {R} [X]}$

Die Polynome ${\displaystyle q(X)}$ und ${\displaystyle r(X)}$ lassen sich durch Polynomdivision bestimmen.

• Hashfunktion und die dort genannten Verfahren
• Kleiner fermatscher Satz
• Satz von Euler
• Liste von Operatoren für den Rest einer Division

• Kristina Reiss, Gerald Schmieder: Basiswissen Zahlentheorie. Eine Einführung in Zahlen und Zahlenbereiche. Springer-Verlag, Berlin u. a. 2005, ISBN 3-540-21248-5.
• Peter Hartmann: Mathematik für Informatiker. Ein praxisbezogenes Lehrbuch. 4. überarbeitete Auflage. Vieweg, Wiesbaden 2006, ISBN 3-8348-0096-1, S. 62, (online).
• Albrecht Beutelspacher, Marc-Alexander Zschiegner: Diskrete Mathematik für Einsteiger. Mit Anwendungen in Technik und Informatik. Vieweg, Wiesbaden 2007, ISBN 978-3-8348-0094-7, S. 65, (online).
• Universität Ulm: "Elementare Zahlentheorie", (online).

• Modulo online berechnen
• Java ist auch eine Insel: Der Restwert-Operator %
• Ganzzahlige Division und der Rest
• Division mit Rest – der heimliche Hauptsatz der Algebra (PDF; 86 kB)
• Video: Division mit Rest (Teil 1). Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19767.
• Video: Division mit Rest (Teil 2). Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19768.

1. Siehe auch den Eintrag modulo im Wörterbuch Wiktionary.
2. Ken Thompson: Users' Reference to B. Hrsg.: Bell Telephone Laboratories. 7. Januar 1972, S. 10 (englisch, bell-labs.com [PDF]).