imported>Elrond: /* Weitere Anwendungen */ + CAS-Nummer

2026-04-28T10:46:14Z

Weitere Anwendungen: + CAS-Nummer

Neue Seite

Von der '''Division mit Rest''' handelt ein [[Satz (Mathematik)|mathematischer Satz]] aus der [[Algebra]] und der [[Zahlentheorie]]. Er besagt, dass es zu zwei [[Ganze Zahl|ganzen Zahlen]] <math>a</math> und <math>m \ne 0</math> eindeutig bestimmte ganze Zahlen <math>q</math> und <math>r</math> gibt, für die
:<math>a = m \cdot q + r\,,\quad 0 \le r < |m|</math>
gilt. Die Zahlen <math>q</math> und <math>r</math> lassen sich durch die [[schriftliche Division]] ermitteln.

Die Division mit Rest ist auch für [[Polynom]]e definiert. Die allgemeinste [[mathematische Struktur]], in der es eine Division mit Rest gibt, ist der [[Euklidischer Ring|euklidische Ring]].

== Natürliche Zahlen ==
Wenn zwei [[natürliche Zahlen]], der Dividend <math>a</math> und der Divisor <math>m</math> (ungleich 0), mit Rest dividiert werden sollen, wenn also
: <math>a : m</math>
berechnet werden soll, so wird gefragt, wie man die Zahl <math>a</math> als Vielfaches von <math>m</math> und einem „kleinen Rest“ darstellen kann:
: <math>a = m \cdot q + r</math>
Hier ist <math>q</math> der sogenannte ''Ganzzahlquotient'' und <math>r</math> der ''Rest.''
Entscheidende [[Nebenbedingung]] ist, dass <math>r</math> eine der Zahlen <math>0, 1, \dotsc, m-1</math> ist. Hierdurch wird <math>r</math> 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 [[Teilbarkeit|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.

=== Beispiele ===
* 9 : 4 = 2, Rest 1, da 9 = 4 × 2 + 1 („vier passt zweimal in neun und es bleibt eins übrig“ – der Rest ist also eins)
* 2 : 4 = 0, Rest 2, da 2 = 4 × 0 + 2
* 4 : 4 = 1, Rest 0, da 4 = 4 × 1 + 0

Die hier verwendete Schreibweise wird so in Grundschulen und teilweise auch in weiterführenden Schulen verwendet, ist fachwissenschaftlich aber problematisch und nicht ganz korrekt, da sie die [[Transitive Relation|Transitivität]] der [[Äquivalenzrelation]] „=“ verletzt. Man erhält bei dieser Schreibweise z. B. für die unterschiedlichen Divisionen 9 : 4 und 5 : 2 scheinbar das gleiche Ergebnis, nämlich (2, Rest 1), woraus gemäß «Sind zwei Zahlen einer dritten gleich, so sind sie untereinander gleich» irrigerweise 2,25 = 9/4 = (2, Rest 1) = 5/2 = 2,5 folgen würde. Oft werden daher die Schreibweisen 9 : 4 = 2 + 1 : 4 oder auch 9 = 4 × 2 + 1 vorgezogen.

An Grundschulen lässt sich die Division mit Rest durch das Teilen einer Menge in gleich große Teile erklären. Dabei hat man prinzipiell zwei Möglichkeiten: entweder wird die Anzahl der Teile vorgegeben oder deren Größe. Beispielsweise kann „7 geteilt durch 3 ergibt 2 Rest 1“ so konkretisiert werden:
{| style="margin:-0.7em 0 1em -0.2em"
|-
| 7 Murmeln an 3 Kinder verteilen:
| <math> \begin{array}{|c|c|c|}\hline \bullet&\bullet&\bullet\\ \bullet&\bullet&\bullet\\\hline \end{array} \;\bullet </math>
|-
| 7 Murmeln in 3er-Päckchen aufteilen: 
| <math> \begin{array}{|ccc|}\hline \bullet&\bullet&\bullet\\\hline \bullet&\bullet&\bullet\\\hline \end{array} \;\bullet </math>
|}

=== Bestimmung des Restes für spezielle Teiler ===
Häufig kann man den Rest an der Dezimaldarstellung ablesen:
* Bei Division durch 2: Der Rest ist 1, wenn die letzte Ziffer ungerade ist, bzw. 0, wenn die letzte Ziffer gerade ist.
* Bei Division durch 3: Der Rest ist gleich dem Rest, den die [[Quersumme#Einstellige (oder iterierte) Quersumme|iterierte Quersumme]] bei Division durch 3 lässt.
* Bei Division durch 5: Der Rest ist gleich dem Rest, den die letzte Ziffer bei Division durch 5 lässt.
* Bei Division durch 9: Der Rest ist gleich dem Rest, den die iterierte Quersumme bei Division durch 9 lässt.
* Bei Division durch 10 (oder 100, 1000, …): Der Rest ist die letzte Ziffer (oder die beiden, drei … letzten Ziffern). Analoge Regeln gelten auch in anderen [[Stellenwertsystem]]en.
Ähnliche, wenn auch etwas kompliziertere Regeln existieren für etliche weitere Teiler.

== Ganze Zahlen ==
Bei der Division mit Rest von einer ganzen Zahl <math>a</math> durch eine ganze Zahl <math>m \neq 0</math> gibt es außer der anfangs angegebenen Hauptfassung insbesondere zwei Modifikationen. Alle drei Fassungen besagen, dass jeweils eindeutig bestimmte ganze Zahlen <math>q</math> und <math>r</math> existieren mit
:<math>
a = mq + r, \quad |r| < |m|
</math>
und vorgegebenem Vorzeichen von <math>r.</math> Im Fall <math>a \ge 0</math> und <math>m > 0</math> ergeben sich aber derselbe Ganzzahlquotient <math>q</math> und derselbe Rest <math>r,</math> und beide sind ebenfalls [[nichtnegativ]].

Für den Rest <math>r</math> schreibt man meist <math>a \bmod m</math> mit dem jeweiligen ''[[Modulo]]'', kurz <math>\mathrm{mod},</math> das als eine [[Zweistellige Verknüpfung|Verknüpfung]] ganzer Zahlen aufgefasst werden kann. Es gilt <math>r = 0</math> genau dann, wenn <math>a</math> durch <math>m</math> [[teilbar]] ist.

=== (I) Rest ist nichtnegativ ===
Die zusätzliche Forderung <math>r \ge 0</math> führt auf die ganz oben angegebene Hauptfassung. In der Darstellung <math>a = mq + r</math> ist dabei der Summand <math>mq</math> das größte Vielfache von <math>m,</math> das kleiner oder gleich <math>a</math> ist.

Bei <math>-25</math> geteilt durch <math>-4</math> beispielsweise findet man als größtes Vielfaches von <math>-4,</math> das kleiner oder gleich <math>-25</math> ist, die Zahl <math>-28 = (-4)\cdot 7\,</math> (um <math>3</math> kleiner), also
:<math>
-25 = (-4)\cdot 7 + 3,
</math>
d. h. <math>(-25):(-4)</math> ergibt <math>7</math> Rest <math>3.</math> Insbesondere ist hier <math>(-25) \bmod ({-4}) = 3.</math>

==== Berechnung des Ganzzahlquotienten ====
Die Bedingung <math>0 \le r < |m|</math> an den Rest <math>r = a - mq</math> lässt sich umschreiben zur Bedingung <math>0 \le a - mq < |m|</math> an <math>q.</math> Division durch <math>|m| = \sgn(m)\,m\,</math> (<math>\sgn</math> ist die [[Signumfunktion]]) führt auf die äquivalente Ungleichungskette
:<math>
0 \le \frac{a}{|m|} - \frac{q}{\sgn(m)} < 1
</math>
und weiter auf
:<math>
\frac{a}{|m|} - 1 < \frac{q}{\sgn(m)} \le \frac{a}{|m|}\,,
</math>
d. h. die (ganze) Zahl <math>\tfrac{q}{\sgn(m)}</math> ist die größte ganze Zahl, die kleiner oder gleich <math>\tfrac{a}{|m|}</math> ist. Der Ganzzahlquotient kann also bestimmt werden durch
:<math>
q = \sgn(m) \left\lfloor\frac{a}{|m|}\right\rfloor
</math>
mit der [[Abrundungsfunktion]] <math>\lfloor\cdot\rfloor</math> (Gaußklammer, Floor-Funktion). Der Rest ergibt sich dann durch <math>r = a - mq.</math>

So erhält man für <math>(-25):(-4)</math> im letzten Beispiel erneut den Ganzzahlquotienten
:<math>
q = \sgn(-4)\cdot \left\lfloor\frac{-25}{|{-4}|}\right\rfloor = -1\cdot \left\lfloor\frac{-25}{4}\right\rfloor</math> <math>= -\lfloor-6{,}25\rfloor = -(-7) = 7
</math>
und den Rest <math>r = -25 - (-4)\cdot 7 = -25 + 28 = 3.</math>

=== (II) Rest hat Vorzeichen des Divisors ===
Gemeint ist hier die Forderung
:<math>
r \ge 0\;\text{ für } m > 0,\qquad r \le 0\;\text{ für } m < 0.
</math>
Der Ganzzahlquotient kann dabei durch
:<math>
q = \left\lfloor\frac{a}{m\vphantom|}\right\rfloor
</math>
berechnet werden, der Rest dann wieder durch <math>r = a - mq.</math>

Die vorherige Division <math>(-25):(-4)</math> ergibt nun gemäß der Darstellung
:<math>
-25 = (-4)\cdot 6 + (-1)
</math>
jedoch <math>6</math> Rest <math>-1.</math> Das erhält man auch bei der Rechnung
:<math>
q = \left\lfloor\frac{-25}{-4}\right\rfloor = \left\lfloor\frac{25}{4}\right\rfloor = \lfloor6{,}25\rfloor = 6
</math>
und <math>r = -25 - (-4)\cdot 6 = -25 + 24 = -1.</math> Hier ist also <math>(-25) \bmod ({-4}) = -1.</math>

=== (III) Rest hat Vorzeichen des Dividenden ===
Gemeint ist hier die Forderung
:<math>
r \ge 0\;\text{ für } a \ge 0,\qquad r \le 0\;\text{ für } a \le 0.
</math>
Der Ganzzahlquotient kann dabei durch
:<math>
q = \sgn(a)\sgn(m) \left\lfloor\frac{|a|}{|m|}\right\rfloor
</math>
berechnet werden, der Rest dann wieder durch <math>r = a - mq.</math>

Hier ergibt <math>(-25):(-4)</math> gemäß derselben Darstellung wie in (II) ebenfalls <math>6</math> Rest <math>-1.</math> Aber die Berechnung des Ganzzahlquotienten würde nun so verlaufen:
:<math>
q = \sgn(-25)\cdot\sgn(-4)\cdot \left\lfloor\frac{|{-25}|}{|{-4}|}\right\rfloor</math> <math>= -1\cdot(-1)\cdot \left\lfloor\frac{25}{4}\right\rfloor = \lfloor6{,}25\rfloor = 6.
</math>

== Modulo ==
Modulo berechnet den Rest <math>r</math> der Division <math>a</math> geteilt durch <math>m</math>. Man kann eine Funktion definieren, die jedem Zahlenpaar <math>(a, m)</math> einen eindeutigen Teilerrest <math>r</math> zuordnet. Diese nennt man ''Modulo'' (von lat. modulus, Kasus [[Ablativ]], also: ‚(gemessen) mit dem (kleinen) Maß (des …)‘<ref>Siehe auch den Eintrag [[wikt:modulo|modulo]] im Wörterbuch Wiktionary.</ref>) und kürzt sie meistens mit ''mod'' ab.

Wir betrachten [[#(II) Rest hat Vorzeichen des Divisors|gemäß (II)]] die Funktion
: <math>\operatorname{mod}\colon\Z \times (\Z\setminus\{0\}) \to \Z, \quad (a,m) \mapsto a \bmod m:= a - \left \lfloor \frac{a}{m} \right \rfloor \cdot m.</math>

: Die [[Abrundungsfunktion und Aufrundungsfunktion|Gaußklammer]] <math>\lfloor \cdot \rfloor</math> 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
::<math>(a + km) \bmod m = a \bmod m</math> für alle <math>k\in\Z,</math>
: aber im Allgemeinen ist
:: <math>(-a) \bmod m \ne-(a \bmod m),</math> z. B. <math>(-2) \bmod 3=1\ne-2=-(2 \bmod 3).</math>
: Ist <math>m</math> positiv, so ist <math>a \bmod m\geq0</math> für alle <math>a.</math>

=== Beispiele ===
* <math> 17 \bmod 3 = 2,</math> da <math>17 = 5 \cdot 3 + 2</math> („3 passt fünfmal in 17 und es bleiben 2 übrig“ – der Rest ist also 2)
* <math> 2 \bmod 3 = 2,</math> da <math> 2 = 0 \cdot 3 + 2</math>
* <math> 3 \bmod 3 = 0,</math> da <math> 3 = 1 \cdot 3 + 0</math>
* <math>-8 \bmod 6 = -8 - \left\lfloor \tfrac{-8}{6} \right\rfloor \cdot 6 = -8 - ((-2) \cdot 6 ) = -8 + 12 = 4</math>

Neben dieser „mathematischen Variante“ wird oft auch die Restfunktion [[#(III) Rest hat Vorzeichen des Dividenden|in (III)]] als Modulo bezeichnet, die für negative Argumente unterschiedliche Ergebnisse liefert und „symmetrische Variante“ genannt wird:

:: <math>(a \bmod m) := a - m\cdot (a\,\operatorname{div}\,m)</math>
: Dabei bezeichnet <math>a\,\operatorname{div}\,m</math> den zur Null hin gerundeten Quotienten <math>a\,/\,m</math>, gegeben durch <math>a\,\operatorname{div}\,m = \sgn(a)\;\sgn(m) \left \lfloor \tfrac{|a|}{|m|} \right \rfloor</math>, wobei <math>\sgn(x)</math> die [[Vorzeichenfunktion]] bezeichnet. Für diese Variante gilt
:: <math>(-a) \bmod m = -(a \bmod m),</math>
: aber im Allgemeinen
:: <math>(a + km) \bmod m\ne a \bmod m,</math> z. B. <math>(1 - 3) \bmod 3=(-2) \bmod 3=-2\ne 1=1 \bmod 3.</math>
: <math>a \bmod m</math> hat stets dasselbe Vorzeichen wie <math>a</math>, oder es gilt <math>a \bmod m = 0</math>.

Gilt <math>a\geq 0</math> und <math>m>0</math>, so ergeben beide Varianten dasselbe Ergebnis.

=== Implementierung in Computersystemen ===
DIV- und MOD-Befehle bzw. Operatoren (für ganzzahlige Division und Restbildung) sind in den meisten [[Programmiersprache]]n und [[Prozessor]]en implementiert.

Einige Programmiersprachen und [[Computeralgebrasystem]]e tragen der Vielfalt von Konventionen Rechnung, indem sie zwei Modulo- oder Rest-Operatoren zur Verfügung stellen. In der Programmiersprache [[Ada (Programmiersprache)|Ada]] hat:
* (<math>a</math> '''rem''' <math>m</math>) dasselbe Vorzeichen wie <math>a</math> und einen Absolutbetrag kleiner als der von <math>m,</math>
* (<math>a</math> '''mod''' <math>m</math>) dasselbe Vorzeichen wie <math>m</math> und einen Absolutbetrag kleiner als der von <math>m,</math>
man erhält also den Rest <math>r</math> gemäß (III) bzw. (II).

{{Siehe auch|Liste von Operatoren für den Rest einer Division}}

In Programmiersprachen ist die implementierte Variante [[Liste von Operatoren für den Rest einer Division|nicht einheitlich]]. So verwenden [[Ruby (Programmiersprache)|Ruby]], [[Perl (Programmiersprache)|Perl]], [[Python (Programmiersprache)|Python]], Excel und der [[Google Suche#Zusatzfunktionen|Rechner der Googlesuche]] die mathematische Variante, wohingegen [[C (Programmiersprache)|C]], [[Java (Programmiersprache)|Java]], [[JavaScript]] und [[PHP]] die symmetrische einsetzen, was besonders wichtig bei [[Portierung (Software)|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:
:<math>a \bmod m</math> = <code>((a % m) + m) % m</code>,
wobei <code>%</code> die symmetrische Modulooperation bezeichnet und <math>\operatorname{mod}</math> die mathematische.

In Programmiersprachen, die [[B (Programmiersprache)|B]]-Abkömmlinge sind, wie [[C (Programmiersprache)|C]] oder [[Java (Programmiersprache)|Java]], wird die Funktion durch <code>%</code> ([[Prozentzeichen]]) dargestellt und als [[Operator (Mathematik)|Operator]] behandelt.<ref>{{Literatur |Autor=[[Ken Thompson]] |Titel=Users' Reference to B |Hrsg=[[Bell Telephone Laboratories]] |Datum=1972-01-07 |Sprache=en |Seiten=10 |Online=https://www.bell-labs.com/usr/dmr/www/kbman.pdf#page=12 |Format=PDF}}</ref> Frühe Programmiersprachen kannten den Operator ''mod'' noch nicht, nur den [[Datentyp]] des ganzzahligen Werts ''[[Integer (Datentyp)|integer]]'' (abgekürzt <code>INT</code>); darum wurde der Divisionsrest nach der Formel <math>\bigg(\frac{a}{m} - \texttt{INT}\left(\frac{a}{m}\right)\bigg) \cdot m</math> errechnet und wegen der damaligen Rechenungenauigkeit beim Dividieren dann auf den ganzzahligen Wert gerundet.

== Kongruenz modulo einer ganzen Zahl ==
{{Hauptartikel|Kongruenz (Zahlentheorie)}}
Zwei ganze Zahlen <math>a</math> und <math>b</math> haben bei Division durch eine ganze Zahl <math>m \neq 0</math> [[#(I) Rest ist nichtnegativ|gemäß (I)]] genau dann denselben nichtnegativen Rest, wenn sie sich nur um ein [[Vielfaches]] von <math>m</math> unterscheiden, d. h. wenn ihre Differenz <math>a - b</math> durch <math>m</math> [[teilbar]] ist. In diesem Fall heißt <math>a</math> [[Kongruenz (Zahlentheorie)|kongruent]] zu <math>b</math> modulo <math>m,</math> in Zeichen <math>a \equiv_m b</math> oder auch bevorzugt <math>\,\textstyle a \equiv b \pmod{\!m};\,</math> dabei wird <math>m</math> Modul genannt. Gebräuchlich ist zwar auch die Schreibweise <math>\,\textstyle a \equiv b \!\mod{\!m}\,</math> ohne die Klammern, bei der aber <math>\mathrm{mod}</math> mit der [[Modulo]]-''Verknüpfung'' verwechselt werden kann. Damit gilt die Äquivalenz
:<math>
a \bmod m = b \bmod m \quad</math> <math>\Longleftrightarrow\quad a \equiv b \pmod m,
</math>
wobei nur die beiden <math>\mathrm{mod}</math> bei der linken Gleichung für die Modulo-Verknüpfung stehen, und zwar für die zu (I) gehörige. Das gilt ebenso [[#(II) Rest hat Vorzeichen des Divisors|mit (II)]], jedoch nicht mit [[#(III) Rest hat Vorzeichen des Dividenden|Fassung (III)]] der Division mit Rest.

Beispielsweise haben die beiden Zahlen <math>43</math> und <math>-7</math> bei Division durch <math>5</math> gemäß (I) denselben nichtnegativen Rest:
:<math>
43 \bmod 5 = 3 = (-7) \bmod 5.
</math>
Andererseits ist ihre Differenz <math>43 - (-7) = 50</math> durch <math>5</math> teilbar, und somit sind sie auch zueinander kongruent modulo <math>5\colon</math>
:<math>
43 \equiv -7 \pmod 5.
</math>

Die Kongruenz modulo <math>m</math> ist eine [[Äquivalenzrelation]] in der Menge der ganzen Zahlen. Die zugehörigen <math>|m|</math> verschiedenen [[Äquivalenzklasse]]n heißen auch [[Restklasse]]n und bilden zusammen den [[Restklassenring]] modulo <math>m.</math>

== Verallgemeinerung: Reelle Zahlen ==
Sind <math>a</math> und <math>m</math> reelle Zahlen, <math>m</math> ungleich 0, dann kann man eine Division "<math>a</math> durch <math>m</math> mit Rest" folgendermaßen definieren: Der ''ganzzahlige'' Quotient <math>q</math> und der Rest <math>r</math> im halboffenen [[Intervall (Mathematik)|Intervall]] <math>[0, |m|)</math> sind diejenigen (eindeutig bestimmten) Zahlen, die die Gleichung <math>a = m \cdot q + r</math> erfüllen.

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

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

== Polynome ==
Bei der Division mit Rest für [[Polynom]]e muss das als Divisor auftretende Polynom <math>f(X)</math> aus dem [[Polynomring]] <math>R[X]</math> (über <math>R</math>, einem [[Ring (Algebra)#Ring|kommutativen Ring]] [[Ring (Algebra)#Ring mit Eins|mit <math>1</math>]]) eine Voraussetzung erfüllen: Der [[Leitkoeffizient]] von <math>f(X)</math> muss eine [[Einheit (Mathematik)#Spezialfall: Einheiten in unitären Ringen|Einheit]] von <math>R</math> sein (insbes. ist <math>f(X)</math> nicht das [[Nullpolynom]]). Unter dieser Bedingung gibt es zu jedem <math>g(X) \in R[X]</math> eindeutig bestimmte Polynome <math>q(X), r(X) \in R[X]</math> mit
: <math>g(X) = f(X) \cdot q(X) + r(X), \qquad</math> <math>\operatorname{deg}(r) < \operatorname{deg}(f).</math>

Dabei wird dem Nullpolynom ein kleinerer [[Polynom|Grad]] als jedem anderen Polynom gegeben, beispielsweise <math>-\infty</math>. Die Polynome <math>q(X)</math> und <math>r(X)</math> lassen sich durch [[Polynomdivision]] bestimmen.

Im Polynomring <math>\R[X]</math> ist beispielsweise
:<math>
2X^2 + 4X + 5 = (X + 1)\cdot(2X + 2) + 3.
</math>

== Anwendungen ==
=== Euklidischer Algorithmus ===
Mit dem [[Euklidischer Algorithmus|euklidischen Algorithmus]] kann der [[Größter gemeinsamer Teiler|größte gemeinsame Teiler]] zweier ganzer Zahlen berechnet werden. Dabei wird wiederholt verwendet, dass sich der ggT nicht ändert, wenn ein Vielfaches der einen Zahl zur anderen addiert wird, also
:<math>
\mathrm{ggT}(a,m) = \mathrm{ggT}(a - mq,\, m)
</math>
für beliebige ganze Zahlen <math>a,</math> <math>m</math> und <math>q.</math> Sogar ''jeder'' gemeinsame Teiler von <math>a</math> und <math>m</math> ist auch einer von <math>a - mq</math> und <math>m</math> und ebenso umgekehrt.<ref>''Beweis.'' „<math>\Rightarrow</math>“ Ist <math>t</math> ein gemeinsamer Teiler von <math>a</math> und <math>m,</math> so gibt es <math>\alpha, \mu \in \Z</math> mit <math>a = t\alpha</math> und <math>m = t\mu.</math> Es folgt <math>a - mq = t\alpha - t\mu q</math> <math>= t(\alpha - \mu q),</math> und somit ist <math>t</math> auch ein gemeinsamer Teiler von <math>a - mq</math> und <math>m.</math><br /> „<math>\Leftarrow</math>“ Umgekehrt ist jeder gemeinsame Teiler von <math>a - mq</math> und <math>m</math> aufgrund der schon bewiesenen Richtung auch einer von <math>(a - mq) - (-m)q = a</math> und <math>m.</math> <math>\,\square</math><br /> Außerdem beachte man, dass die Teiler von <math>0</math> die gesamten ganzen Zahlen sind, aber <math>\mathrm{ggT}(0,0)</math> als <math>0</math> definiert ist.</ref>

Hier kann man aber im Fall <math>m \neq 0</math> für <math>q</math> den Ganzzahlquotienten nehmen, der sich bei der Division etwa [[#(I) Rest ist nichtnegativ|gemäß (I)]] von <math>a</math> durch <math>m</math> ergibt, sodass <math>a - mq = r</math> der nichtnegative Rest wird. Anschließend verfährt man umgekehrt, also entsprechend zur Division von <math>m</math> durch <math>r</math> usw. – immer abwechselnd. So wird schließlich eine der beiden Zahlen zu <math>0,</math> sodass dann wegen
:<math>
\mathrm{ggT}(a,0) = |a| = \mathrm{ggT}(0,a)
</math>
der ggT der beiden Ausgangszahlen ermittelt ist. Außerdem ergibt sich, dass deren gemeinsame Teiler genau die Teiler des ggT sind.

==== Beispiel ====
Die Berechnung des größten gemeinsamen Teilers von <math>68</math> und <math>30</math> beginnt entsprechend zur Division <math>68:30,</math> also <math>68 = 30\cdot 2 + 8,</math> mit
:<math>
\mathrm{ggT}(68,30) = \mathrm{ggT}(68 - 30\cdot 2,\, 30) </math> <math> = \mathrm{ggT}(8,30),
</math>
im zweiten Schritt entsprechend zu <math>30 = 8\cdot 3 + 6</math> dann
:<math>
\mathrm{ggT}(8,30) = \mathrm{ggT}(8,\,30-8\cdot3) </math> <math> = \mathrm{ggT}(8,6)
</math>
und so fort. Das lässt sich aber kompakter schreiben:
:<math>
\mathrm{ggT}\underset{\color{Green}\scriptstyle\;\;^\uparrow\!\!-\!-\!(-2)}{(68,30)}
= \mathrm{ggT}\underset{\color{Green}\scriptstyle\!(-3)\!-\!\!-\!^\uparrow\;\;}{(8,30)}
= \mathrm{ggT}\underset{\color{Green}\scriptstyle\;^\uparrow\!\!-\!\!-\!(-1)\!\!}{(8,\,6)}\!\ </math> <math>
= \mathrm{ggT}\underset{\color{Green}\scriptstyle\!\!(-3)\!-\!\!-\!^\uparrow\;}{(2,\,6)}
= \mathrm{ggT}(2,0) = 2\!\ ;
</math>
dabei soll etwa <math>\color{Green}\scriptstyle\,^\uparrow\!\!-\!-\!(-2)</math> beim ersten Schritt bedeuten, dass das <math>(-2)</math>-Fache von <math>30</math> zu <math>68</math> addiert wird. Die gemeinsamen Teiler der beiden Ausgangszahlen <math>68</math> und <math>30</math> sind auch tatsächlich die Teiler von <math>\mathrm{ggT}(68,30) = 2,</math> nämlich <math>1,</math> <math>2,</math> <math>-1</math> und <math>-2.</math>

==== Erweiterter euklidischer Algorithmus ====
[[Datei:Roland Uhl - Euklidischer Algorithmus.svg|hochkant=1.8|rahmenlos|rechts|rand|Erweiterter euklidischer Algorithmus für 𝑔 = ggT(68,30)]]
Im letzten Beispiel wurde von <math>a = 68</math> und <math>b = 30</math> der größte gemeinsame Teiler <math>g = 2</math> berechnet. Wendet man aber die grün angedeuteten Vielfachen-Additionen analog auf Gleichungen an, beginnend mit <math>a = 1a + 0b</math> und <math>b = 0a + 1b,</math> so ergibt sich <math>g = 4a - 9b</math> nach den nebenstehenden Rechnungen (rechts daneben noch ein entsprechendes Zahlenschema mit den analogen Zeilenoperationen).

Allgemein können mit dem [[Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] für zwei ganze Zahlen <math>a</math> und <math>b</math> neben <math>g = \mathrm{ggT}(a,b)</math> noch zwei ganze Zahlen <math>u</math> und <math>v</math> mit <math>g = ua + vb</math> bestimmt werden.

=== Programmierung ===
Die Division mit Rest (Modulo) wird in der Programmierung relativ häufig verwendet. Der entsprechende Operator heißt in unterschiedlichen Programmiersprachen oft <code>mod</code> oder <code>%</code>. Man kann etwa prüfen, ob eine gegebene Zahl <math>a</math> gerade ist, indem man folgende Abfrage durchführt: <code>if a mod 2 == 0</code>. Modulo kann man auch nutzen, wenn man in einer [[Schleife (Programmierung)|Schleife]] lediglich bei jedem <math>a</math>-ten Schleifendurchlauf einen speziellen Programmcode ausführen will. Auch bei vielen Berechnungen und Algorithmen ist der Operator sinnvoll einsetzbar. Allgemein kann man mit <code>mod</code> prüfen, ob eine Zahl durch eine andere genau teilbar ist: Nur dann liefert der Modulo-Operator den Wert 0. Des Weiteren muss man in der Programmierung oft auf ganze Vielfache einer Zahl ergänzen (z. B. 4 Bytes) und kann durch den Modulo errechnen, wie viele „[[Pad-Byte]]s“ noch fehlen. Durch die Funktion [[divmod|<code>divMod</code>]] werden Ganzzahlquotient und Rest zusammen berechnet.
;Beispiel: Man programmiert eine Uhr und hat die Zeit als Sekundenwert seit 0 Uhr gegeben. Dann kann man den Sekundenwert mod 3600 berechnen. Ist dieser gleich 0, so weiß man, dass eine volle Stunde angefangen hat. Diese Information kann man nutzen, um z. B. ein akustisches Signal (Gong zur vollen Stunde) auszulösen. Mit der Berechnung Sekundenwert mod 60 erhält man die Sekunden seit der letzten vollen Minute, die oftmals von Digitaluhren als letzte zwei Stellen angezeigt werden.

Wenn der Divisor <math>m</math> eine [[Zweierpotenz]] ist, kann der Divisionsrest <math>a \operatorname{mod} m</math> auch mit dem [[Bitweiser Operator#UND|bitweisen Und-Operator]] (''UND'') berechnet werden. Denn dann ist <math>a \, \operatorname{mod} \, m = a \, \operatorname{UND} \, (m-1)</math>. Mit dieser Operation erhält man die niedrigwertigsten Bits oder letzten Ziffern im [[Dualsystem]].

=== Weitere Anwendungen ===
* Berechnung der [[Prüfziffer]] der [[Internationale Standardbuchnummer#Formeln zur Berechnung der Prüfziffer|Internationalen Standardbuchnummer]] oder der [[CAS-Nummer]] (ein internationaler Bezeichnungsstandard für chemische Stoffe)
* Prüfsummen-Formel [[Luhn-Algorithmus]] zur Bestätigung von Identifikationsnummern wie Kreditkartennummern und kanadische Sozialversicherungsnummern
* Prüfsummenberechnung bei [[Zyklische Redundanzprüfung|CRC]] und [[Vorwärtsfehlerkorrektur|FEC]] auf Ganzzahl- oder [[Binäres Zahlensystem|Binärbasis]]
* Kalenderberechnung (die relativ komplizierte Berechnung des [[Osterdatum]]s), siehe auch [[Zellers Kongruenz]].
* Berechnung der Prüfsumme der [[Internationale Bankkontonummer|Internationalen Bankkontonummer]] (IBAN)
* In der [[Kryptographie]], beim [[Diffie-Hellman-Schlüsselaustausch]] oder beim [[RSA-Kryptosystem]]
* Berechnung der Geometrie von [[Diffusor (Akustik)|Schröderdiffusoren]]
* Bildung binärer [[Fraktal|Fraktale]]

== Siehe auch ==
* [[Hashfunktion]] und die dort genannten Verfahren
* [[Kleiner fermatscher Satz]]
* [[Satz von Euler]]
* [[Liste von Operatoren für den Rest einer Division]]

== Literatur ==
* [[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 ([http://books.google.de/books?id=GcJOBaGN4q8C 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 ([https://books.google.de/books?id=xhsAC5ufSNUC online]).

== Weblinks ==
* [http://userpage.fu-berlin.de/~ram/pub/pub_jf47ht81Ht/formal_modulo_de Ganzzahlige Division und der Rest]
* [https://www.uibk.ac.at/mathematik/personal/pauer/vortragpauerwien2004.pdf Division mit Rest – der heimliche Hauptsatz der Algebra] (PDF; 86 kB)
* {{TIBAV |19767 |Linktext=Division mit Rest (Teil 1) |Herausgeber=PHHD |Jahr=2012 |DOI=10.5446/19767}}
* {{TIBAV |19768 |Linktext=Division mit Rest (Teil 2) |Herausgeber=PHHD |Jahr=2012 |DOI=10.5446/19768}}
* [[Helmut Maier (Mathematiker)|Helmut Maier]], Hans-Peter Reck: [https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.zawa/lehre/11elzahl/Skript.pdf Vorabskript zur Vorlesung ''Elementare Zahlentheorie''.] Institut für Zahlentheorie und Wahrscheinlichkeitstheorie, Universität Ulm, Sommersemester 2011

== Einzelnachweise und Anmerkungen ==
<references />

[[Kategorie:Division (Mathematik)]]
[[Kategorie:Zahlentheorie]]

Division mit Rest - Versionsgeschichte

imported>Elrond: /* Weitere Anwendungen */ + CAS-Nummer