Division mit Rest

Redirected from Modulo

Von der Division mit Rest handelt ein mathematischer Satz aus der Algebra und der Zahlentheorie. Er besagt, dass es zu zwei ganzen Zahlen ${\displaystyle a}$ und ${\displaystyle m\neq 0}$ eindeutig bestimmte ganze Zahlen ${\displaystyle q}$ (Quotient) und ${\displaystyle r}$ (Rest) gibt, für die

${\displaystyle a=m\cdot q+r\,,\quad 0\leq r<|m|}$

gilt. Die Zahlen ${\displaystyle q}$ und ${\displaystyle r}$ lassen sich durch die schriftliche Division ermitteln.

Die Division mit Rest ist auch für Polynome definiert. Die allgemeinste mathematische Struktur, in der es eine Division mit Rest gibt, ist der euklidische Ring.

Natürliche Zahlen#edit

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

${\displaystyle a:m}$

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

${\displaystyle a=m\cdot q+r}$

Hier ist ${\displaystyle q}$ der sogenannte Ganzzahlquotient und ${\displaystyle r}$ der Rest. Entscheidende Nebenbedingung ist, dass ${\displaystyle r}$ eine der Zahlen ${\displaystyle 0,1,\dotsc ,m-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.

Beispiele#edit

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 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:

Bestimmung des Restes für spezielle Teiler#edit

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 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 Stellenwertsystemen.

Ähnliche, wenn auch etwas kompliziertere Regeln existieren für etliche weitere Teiler.

Ganze Zahlen#edit

Bei der Division mit Rest von einer ganzen Zahl ${\displaystyle a}$ durch eine ganze Zahl ${\displaystyle m\neq 0}$ gibt es außer der anfangs angegebenen Hauptfassung insbesondere zwei Modifikationen. Alle drei Fassungen besagen, dass jeweils eindeutig bestimmte ganze Zahlen ${\displaystyle q}$ und ${\displaystyle r}$ existieren mit

${\displaystyle a=mq+r,\quad |r|<|m|}$

und vorgegebenem Vorzeichen von ${\displaystyle r.}$ Im Fall ${\displaystyle a\geq 0}$ und ${\displaystyle m>0}$ ergeben sich aber derselbe Ganzzahlquotient ${\displaystyle q}$ und derselbe Rest ${\displaystyle r,}$ und beide sind ebenfalls nichtnegativ.

Für den Rest ${\displaystyle r}$ schreibt man meist ${\displaystyle a{\bmod {m$ mit dem jeweiligen Modulo, kurz ${\displaystyle \mathrm {mod} ,}$ das als eine Verknüpfung ganzer Zahlen aufgefasst werden kann. Es gilt ${\displaystyle r=0}$ genau dann, wenn ${\displaystyle a}$ durch ${\displaystyle m}$ teilbar ist.

(I) Rest ist nichtnegativ#edit

Die zusätzliche Forderung ${\displaystyle r\geq 0}$ führt auf die ganz oben angegebene Hauptfassung. In der Darstellung ${\displaystyle a=mq+r}$ ist dabei der Summand ${\displaystyle mq}$ das größte Vielfache von ${\displaystyle m,}$ das kleiner oder gleich ${\displaystyle a}$ ist.

Bei ${\displaystyle -25}$ geteilt durch ${\displaystyle -4}$ beispielsweise findet man als größtes Vielfaches von ${\displaystyle -4,}$ das kleiner oder gleich ${\displaystyle -25}$ ist, die Zahl ${\displaystyle -28=(-4)\cdot 7\,}$ (um ${\displaystyle 3}$ kleiner), also

${\displaystyle -25=(-4)\cdot 7+3,}$

d. h. ${\displaystyle (-25):(-4)}$ ergibt ${\displaystyle 7}$ Rest ${\displaystyle 3.}$ Insbesondere ist hier ${\displaystyle (-25){\bmod {({-4})=3.}$

Berechnung des Ganzzahlquotienten#edit

Die Bedingung ${\displaystyle 0\leq r<|m|}$ an den Rest ${\displaystyle r=a-mq}$ lässt sich umschreiben zur Bedingung ${\displaystyle 0\leq a-mq<|m|}$ an ${\displaystyle q.}$ Division durch ${\displaystyle |m|=\operatorname {sgn} (m)\,m\,}$ ( ${\displaystyle \operatorname {sgn} }$ ist die Signumfunktion) führt auf die äquivalente Ungleichungskette

${\displaystyle 0\leq {\frac {a}{|m|-{\frac {q}{\operatorname {sgn} (m)<1}$

und weiter auf

${\displaystyle {\frac {a}{|m|-1<{\frac {q}{\operatorname {sgn} (m)\leq {\frac {a}{|m|\,,}$

d. h. die (ganze) Zahl ${\displaystyle {\tfrac {q}{\operatorname {sgn} (m)$ ist die größte ganze Zahl, die kleiner oder gleich ${\displaystyle {\tfrac {a}{|m|$ ist. Der Ganzzahlquotient kann also bestimmt werden durch

${\displaystyle q=\operatorname {sgn} (m)\left\lfloor {\frac {a}{|m|\right\rfloor }$

mit der Abrundungsfunktion ${\displaystyle \lfloor \cdot \rfloor }$ (Gaußklammer, Floor-Funktion). Der Rest ergibt sich dann durch ${\displaystyle r=a-mq.}$

So erhält man für ${\displaystyle (-25):(-4)}$ im letzten Beispiel erneut den Ganzzahlquotienten

${\displaystyle q=\operatorname {sgn} (-4)\cdot \left\lfloor {\frac {-25}{|{-4}|\right\rfloor =-1\cdot \left\lfloor {\frac {-25}{4\right\rfloor }$ ${\displaystyle =-\lfloor -6{,}25\rfloor =-(-7)=7}$

und den Rest ${\displaystyle r=-25-(-4)\cdot 7=-25+28=3.}$

(II) Rest hat Vorzeichen des Divisors#edit

Gemeint ist hier die Forderung

${\displaystyle r\geq 0\;{\text{ für m>0,\qquad r\leq 0\;{\text{ für m<0.}$

Der Ganzzahlquotient kann dabei durch

${\displaystyle q=\left\lfloor {\frac {a}{m{\vphantom {|\right\rfloor }$

berechnet werden, der Rest dann wieder durch ${\displaystyle r=a-mq.}$

Die vorherige Division ${\displaystyle (-25):(-4)}$ ergibt nun gemäß der Darstellung

${\displaystyle -25=(-4)\cdot 6+(-1)}$

jedoch ${\displaystyle 6}$ Rest ${\displaystyle -1.}$ Das erhält man auch bei der Rechnung

${\displaystyle q=\left\lfloor {\frac {-25}{-4\right\rfloor =\left\lfloor {\frac {25}{4\right\rfloor =\lfloor 6{,}25\rfloor =6}$

und ${\displaystyle r=-25-(-4)\cdot 6=-25+24=-1.}$ Hier ist also ${\displaystyle (-25){\bmod {({-4})=-1.}$

(III) Rest hat Vorzeichen des Dividenden#edit

Gemeint ist hier die Forderung

${\displaystyle r\geq 0\;{\text{ für a\geq 0,\qquad r\leq 0\;{\text{ für a\leq 0.}$

Der Ganzzahlquotient kann dabei durch

${\displaystyle q=\operatorname {sgn} (a)\operatorname {sgn} (m)\left\lfloor {\frac {|a|}{|m|\right\rfloor }$ ${\displaystyle =\operatorname {sgn} \left({\frac {a}{m\right)\,{\bigg \lfloor }\left|{\frac {a}{m\right|{\bigg \rfloor$

berechnet werden, der Rest dann wieder durch ${\displaystyle r=a-mq.}$

Hier ergibt ${\displaystyle (-25):(-4)}$ gemäß derselben Darstellung wie in (II) ebenfalls ${\displaystyle 6}$ Rest ${\displaystyle -1.}$ Aber die Berechnung des Ganzzahlquotienten würde nun etwa so verlaufen:

${\displaystyle q=\operatorname {sgn} (-25)\cdot \operatorname {sgn} (-4)\cdot \left\lfloor {\frac {|{-25}|}{|{-4}|\right\rfloor }$ ${\displaystyle =(-1)\cdot (-1)\cdot \left\lfloor {\frac {25}{4\right\rfloor =\lfloor 6{,}25\rfloor =6.}$

Modulo#edit

Modulo berechnet den Rest ${\displaystyle r}$ der Division ${\displaystyle a}$ geteilt durch ${\displaystyle m}$ . Man kann eine Funktion definieren, die jedem Zahlenpaar ${\displaystyle (a,m)}$ einen eindeutigen Teilerrest ${\displaystyle r}$ 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.

Wir betrachten gemäß (II) 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.}$

Beispiele#edit

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

Neben dieser „mathematischen Variante“ wird oft auch die Restfunktion in (III) 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 {\tfrac {|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.

Implementierung in Computersystemen#edit

DIV- und MOD-Befehle bzw. Operatoren (für ganzzahlige Division und Restbildung) sind in den meisten Programmiersprachen und Prozessoren implementiert.

Einige Programmiersprachen und Computeralgebrasysteme tragen der Vielfalt von Konventionen Rechnung, indem sie zwei Modulo- oder Rest-Operatoren zur Verfügung stellen. In der Programmiersprache Ada hat:

( ${\displaystyle a}$ rem ${\displaystyle m}$ ) dasselbe Vorzeichen wie ${\displaystyle a}$ und einen Absolutbetrag kleiner als der von ${\displaystyle m,}$
( ${\displaystyle a}$ mod ${\displaystyle m}$ ) dasselbe Vorzeichen wie ${\displaystyle m}$ und einen Absolutbetrag kleiner als der von ${\displaystyle m,}$

man erhält also den Rest ${\displaystyle r}$ gemäß (III) bzw. (II).

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 {m$ = ((a % m) + m) % m,

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

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 {a}{m-{\texttt {INT\left({\frac {a}{m\right){\bigg )}\cdot m}$ errechnet und wegen der damaligen Rechenungenauigkeit beim Dividieren dann auf den ganzzahligen Wert gerundet.

Kongruenz modulo einer ganzen Zahl#edit

Zwei ganze Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ haben bei Division durch eine ganze Zahl ${\displaystyle m\neq 0}$ gemäß (I) genau dann denselben nichtnegativen Rest, wenn sie sich nur um ein Vielfaches von ${\displaystyle m}$ unterscheiden, d. h. wenn ihre Differenz ${\displaystyle a-b}$ durch ${\displaystyle m}$ teilbar ist. In diesem Fall heißt ${\displaystyle a}$ kongruent zu ${\displaystyle b}$ modulo ${\displaystyle m,}$ in Zeichen ${\displaystyle a\equiv _{m}b}$ oder auch bevorzugt ${\displaystyle \,\textstyle a\equiv b{\pmod {\!m;\,}$ dabei wird ${\displaystyle m}$ Modul genannt. Gebräuchlich ist zwar auch die Schreibweise ${\displaystyle \,\textstyle a\equiv b\!\mod {\!m}\,}$ ohne die Klammern, bei der aber ${\displaystyle \mathrm {mod} }$ mit der Modulo-Verknüpfung verwechselt werden kann. Damit gilt die Äquivalenz

${\displaystyle a{\bmod {m=b{\bmod {m\quad }$ ${\displaystyle \Longleftrightarrow \quad a\equiv b{\pmod {m,}$

wobei nur die beiden ${\displaystyle \mathrm {mod} }$ bei der linken Gleichung für die Modulo-Verknüpfung stehen, und zwar für die zu (I) gehörige. Das gilt ebenso mit (II), jedoch nicht mit Fassung (III) der Division mit Rest.

Beispielsweise haben die beiden Zahlen ${\displaystyle 43}$ und ${\displaystyle -7}$ bei Division durch ${\displaystyle 5}$ gemäß (I) denselben nichtnegativen Rest:

${\displaystyle 43{\bmod {5=3=(-7){\bmod {5.}$

Andererseits ist ihre Differenz ${\displaystyle 43-(-7)=50}$ durch ${\displaystyle 5}$ teilbar, und somit sind sie auch zueinander kongruent modulo ${\displaystyle 5\colon }$

${\displaystyle 43\equiv -7{\pmod {5.}$

Die Kongruenz modulo ${\displaystyle m}$ ist eine Äquivalenzrelation in der Menge der ganzen Zahlen. Die zugehörigen ${\displaystyle |m|}$ verschiedenen Äquivalenzklassen heißen auch Restklassen und bilden zusammen den Restklassenring modulo ${\displaystyle m.}$

Verallgemeinerung: Reelle Zahlen#edit

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

Auch hier gibt es die Alternativen, dem Rest dasselbe Vorzeichen wie ${\displaystyle m}$ 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 q}$ und eine reelle Zahl ${\displaystyle r}$ mit Betrag kleiner oder gleich 1/2, die die Gleichung ${\displaystyle a=q+r}$ erfüllen. Die Zahl ${\displaystyle q}$ 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.

Polynome#edit

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)=f(X)\cdot q(X)+r(X),\qquad }$ ${\displaystyle \operatorname {deg} (r)<\operatorname {deg} (f).}$

Dabei wird dem Nullpolynom ein kleinerer Grad als jedem anderen Polynom gegeben, beispielsweise ${\displaystyle -\infty }$ . Die Polynome ${\displaystyle q(X)}$ und ${\displaystyle r(X)}$ lassen sich durch Polynomdivision bestimmen.

Im Polynomring ${\displaystyle \mathbb {R} [X]}$ ist beispielsweise

${\displaystyle 2X^{2}+4X+5=(X+1)\cdot (2X+2)+3.}$

Anwendungen#edit

Euklidischer Algorithmus#edit

Mit dem euklidischen Algorithmus kann der 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

${\displaystyle \mathrm {ggT} (a,m)=\mathrm {ggT} (a-mq,\,m)}$

für beliebige ganze Zahlen ${\displaystyle a,}$ ${\displaystyle m}$ und ${\displaystyle q.}$ Sogar jeder gemeinsame Teiler von ${\displaystyle a}$ und ${\displaystyle m}$ ist auch einer von ${\displaystyle a-mq}$ und ${\displaystyle m}$ und ebenso umgekehrt.^[3]

Hier kann man aber im Fall ${\displaystyle m\neq 0}$ für ${\displaystyle q}$ den Ganzzahlquotienten nehmen, der sich bei der Division etwa gemäß (I) von ${\displaystyle a}$ durch ${\displaystyle m}$ ergibt, sodass ${\displaystyle a-mq=r}$ der nichtnegative Rest wird. Anschließend verfährt man umgekehrt, also entsprechend zur Division von ${\displaystyle m}$ durch ${\displaystyle r}$ usw. – immer abwechselnd. So wird schließlich eine der beiden Zahlen zu ${\displaystyle 0,}$ sodass dann wegen

${\displaystyle \mathrm {ggT} (a,0)=|a|=\mathrm {ggT} (0,a)}$

der ggT der beiden Ausgangszahlen ermittelt ist. Außerdem ergibt sich, dass deren gemeinsame Teiler genau die Teiler des ggT sind.

Beispiel#edit

Die Berechnung des größten gemeinsamen Teilers von ${\displaystyle 68}$ und ${\displaystyle 30}$ beginnt entsprechend zur Division ${\displaystyle 68:30,}$ also ${\displaystyle 68=30\cdot 2+8,}$ mit

${\displaystyle \mathrm {ggT} (68,30)=\mathrm {ggT} (68-30\cdot 2,\,30)}$ ${\displaystyle =\mathrm {ggT} (8,30),}$

im zweiten Schritt entsprechend zu ${\displaystyle 30=8\cdot 3+6}$ dann

${\displaystyle \mathrm {ggT} (8,30)=\mathrm {ggT} (8,\,30-8\cdot 3)}$ ${\displaystyle =\mathrm {ggT} (8,6)}$

und so fort. Das lässt sich aber kompakter schreiben:

${\displaystyle \mathrm {ggT} {\underset {\color {Green}\scriptstyle \;\;^{\uparrow }\!\!-\!-\!(-2)}{(68,30)=\mathrm {ggT} {\underset {\color {Green}\scriptstyle \!(-3)\!-\!\!-\!^{\uparrow }\;\;}&#$ ${\displaystyle =\mathrm {ggT} {\underset {\color {Green}\scriptstyle \!\!(-3)\!-\!\!-\!^{\uparrow }\;}{(2,\,6)=\mathrm {ggT} (2,0)=2\!\ ;}$

dabei soll etwa ${\displaystyle \scriptstyle \color {Green}\,^{\uparrow }\!\!-\!-\!(-2)}$ beim ersten Schritt bedeuten, dass das ${\displaystyle (-2)}$ -Fache von ${\displaystyle 30}$ zu ${\displaystyle 68}$ addiert wird. Die gemeinsamen Teiler der beiden Ausgangszahlen ${\displaystyle 68}$ und ${\displaystyle 30}$ sind auch tatsächlich die Teiler von ${\displaystyle \mathrm {ggT} (68,30)=2,}$ nämlich ${\displaystyle 1,}$ ${\displaystyle 2,}$ ${\displaystyle -1}$ und ${\displaystyle -2.}$

Erweiterter euklidischer Algorithmus#edit

Im letzten Beispiel wurde von ${\displaystyle a=68}$ und ${\displaystyle b=30}$ der größte gemeinsame Teiler ${\displaystyle g=2}$ berechnet. Wendet man aber die grün angedeuteten Vielfachen-Additionen analog auf Gleichungen an, beginnend mit ${\displaystyle a=1a+0b}$ und ${\displaystyle b=0a+1b,}$ so ergibt sich ${\displaystyle g=4a-9b}$ nach den nebenstehenden Rechnungen (rechts daneben noch ein entsprechendes Zahlenschema mit den analogen Zeilenoperationen).

Allgemein können mit dem erweiterten euklidischen Algorithmus für zwei ganze Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ neben ${\displaystyle g=\mathrm {ggT} (a,b)}$ noch zwei ganze Zahlen ${\displaystyle u}$ und ${\displaystyle v}$ mit ${\displaystyle g=ua+vb}$ bestimmt werden.

Programmierung#edit

Die Division mit Rest (Modulo) wird in der Programmierung relativ häufig verwendet. Der entsprechende Operator heißt in unterschiedlichen Programmiersprachen oft mod oder %. Man kann etwa prüfen, ob eine gegebene Zahl ${\displaystyle a}$ gerade ist, indem man folgende Abfrage durchführt: if a mod 2 == 0. Modulo kann man auch nutzen, wenn man in einer Schleife lediglich bei jedem ${\displaystyle a}$ -ten Schleifendurchlauf einen speziellen Programmcode ausführen will. Auch bei vielen Berechnungen und Algorithmen ist der Operator sinnvoll einsetzbar. Allgemein kann man mit mod 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-Bytes“ noch fehlen. Durch die Funktion divMod 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 ${\displaystyle m}$ eine Zweierpotenz ist, kann der Divisionsrest ${\displaystyle a\operatorname {mod} m}$ auch mit dem bitweisen Und-Operator (UND) berechnet werden. Denn dann ist ${\displaystyle a\,\operatorname {mod} \,m=a\,\operatorname {UND} \,(m-1)}$ . Mit dieser Operation erhält man die niedrigwertigsten Bits oder letzten Ziffern im Dualsystem.

Weitere Anwendungen#edit

Berechnung der Prüfziffer der 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 CRC und FEC auf Ganzzahl- oder Binärbasis
Kalenderberechnung (die relativ komplizierte Berechnung des Osterdatums), siehe auch Zellers Kongruenz.
Berechnung der Prüfsumme der Internationalen Bankkontonummer (IBAN)
In der Kryptographie, beim Diffie-Hellman-Schlüsselaustausch oder beim RSA-Kryptosystem
Berechnung der Geometrie von Schröderdiffusoren
Bildung binärer Fraktale

Siehe auch#edit

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

Literatur#edit

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).

Weblinks#edit

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.
Helmut Maier, Hans-Peter Reck: Vorabskript zur Vorlesung Elementare Zahlentheorie. Institut für Zahlentheorie und Wahrscheinlichkeitstheorie, Universität Ulm, Sommersemester 2011

Einzelnachweise und Anmerkungen#edit

Siehe auch den Eintrag modulo im Wörterbuch Wiktionary.
Ken Thompson: Users' Reference to B. Hrsg.: Bell Telephone Laboratories. 7. Januar 1972, S. 10 (englisch, bell-labs.com [PDF]).
Beweis. „ ${\displaystyle \Rightarrow }$ “ Ist ${\displaystyle t}$ ein gemeinsamer Teiler von ${\displaystyle a}$ und ${\displaystyle m,}$ so gibt es ${\displaystyle \alpha ,\mu \in \mathbb {Z} }$ mit ${\displaystyle a=t\alpha }$ und ${\displaystyle m=t\mu .}$ Es folgt ${\displaystyle a-mq=t\alpha -t\mu q}$ ${\displaystyle =t(\alpha -\mu q),}$ und somit ist ${\displaystyle t}$ auch ein gemeinsamer Teiler von ${\displaystyle a-mq}$ und ${\displaystyle m.}$
„ ${\displaystyle \Leftarrow }$ “ Umgekehrt ist jeder gemeinsame Teiler von ${\displaystyle a-mq}$ und ${\displaystyle m}$ aufgrund der schon bewiesenen Richtung auch einer von ${\displaystyle (a-mq)-(-m)q=a}$ und ${\displaystyle m.}$ ${\displaystyle \,\square }$
Außerdem beachte man, dass die Teiler von ${\displaystyle 0}$ die gesamten ganzen Zahlen sind, aber ${\displaystyle \mathrm {ggT} (0,0)}$ als ${\displaystyle 0}$ definiert ist.

References#

^ Siehe auch den Eintrag modulo im Wörterbuch Wiktionary.
^ Ken Thompson: Users' Reference to B. Hrsg.: Bell Telephone Laboratories. 7. Januar 1972, S. 10 (englisch, bell-labs.com [PDF]).
^ Beweis. „ ${\displaystyle \Rightarrow }$ “ Ist ${\displaystyle t}$ ein gemeinsamer Teiler von ${\displaystyle a}$ und ${\displaystyle m,}$ so gibt es ${\displaystyle \alpha ,\mu \in \mathbb {Z} }$ mit ${\displaystyle a=t\alpha }$ und ${\displaystyle m=t\mu .}$ Es folgt ${\displaystyle a-mq=t\alpha -t\mu q}$ ${\displaystyle =t(\alpha -\mu q),}$ und somit ist ${\displaystyle t}$ auch ein gemeinsamer Teiler von ${\displaystyle a-mq}$ und ${\displaystyle m.}$
„ ${\displaystyle \Leftarrow }$ “ Umgekehrt ist jeder gemeinsame Teiler von ${\displaystyle a-mq}$ und ${\displaystyle m}$ aufgrund der schon bewiesenen Richtung auch einer von ${\displaystyle (a-mq)-(-m)q=a}$ und ${\displaystyle m.}$ ${\displaystyle \,\square }$
Außerdem beachte man, dass die Teiler von ${\displaystyle 0}$ die gesamten ganzen Zahlen sind, aber ${\displaystyle \mathrm {ggT} (0,0)}$ als ${\displaystyle 0}$ definiert ist.

Categories Division (Mathematik)Zahlentheorie

This article is mirrored from “Division mit Rest” on Deutsch Wikipedia, revision 271650349, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 271650349 · just now