Division mit Rest

aus Wikipedia, der freien Enzyklopädie

Die Division mit Rest oder der Divisionsalgorithmus ist ein mathematischer Satz aus der Algebra und der Zahlentheorie. Er besagt, dass es zu zwei Zahlen und eindeutig bestimmte Zahlen und gibt, für die

gilt. Die Zahlen und 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

Wenn zwei natürliche Zahlen, der Dividend und der Divisor (ungleich 0), mit Rest dividiert werden sollen, wenn also

berechnet werden soll, so wird gefragt, wie man die Zahl als Vielfaches von und einem „kleinen Rest“ darstellen kann:

Hier ist der sogenannte Ganzzahlquotient und der Rest. Entscheidende Nebenbedingung ist, dass eine Zahl in ist. Hierdurch wird 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

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

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

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

  1. Stattdessen kann man fordern, dass der Rest zwischen 0 und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |b| - 1} (dem Betrag von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} minus 1) liegt.
  2. Alternativ kann man aber auch verlangen, dass der Rest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b+1} und 0 liegt, also dasselbe Vorzeichen hat wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b .}
  3. Eine dritte Möglichkeit ist, den betragskleinsten Rest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} zu wählen. Diese Variante liefert für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a = b \cdot c + r} die beste Näherung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b \cdot c} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a .}

Beispiel

Dividiert man negative Zahlen, ergibt sich folgendes Bild: 

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

Übertragen auf negative Teiler, folgt: 

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

(Hierbei wird für die Wahl von Quotient und Rest zunächst so getan, als gäbe es keine Vorzeichen, sie werden sozusagen nach der „eigentlichen Berechnung wieder hinzugefügt“). Als Ganzzahlquotient wird hier immer ein Wert bestimmt, dessen Betrag nicht größer als der Betrag des (rationalen) Quotienten ist. Der Rest und sein Vorzeichen folgen aus der Wahl des Quotienten.

Wie groß der Rest bei einer Division nun ausfällt, ist eigentlich Geschmackssache. Denn es steht jedem frei, nur einen Teil einer gegebenen Größe zu teilen, den verbleibenden Rest erklärt er einfach zum „Rest“. Lassen wir hierbei auch zu, dass „Schulden“ gemacht werden dürfen, sind beispielsweise alle folgenden Ergebnisse zulässig: 

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

oder 

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

Zur Normierung wird in der Mathematik die Konvention verwendet, die Vorzeichen der Reste aus denen der Teiler zu beziehen, wie in den folgenden Beispielen dargestellt: 

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

Hierbei kann die Zugehörigkeit einer Zahl zu einer Restklasse direkt am Rest abgelesen werden.

Implementierung in Computersystemen

DIV- und MOD-Befehle bzw. Operatoren (für ganzzahlige Division und Restbildung) sind in den meisten Programmiersprachen (und sogar in CPUs) genau diesem Alltagsansatz entsprechend implementiert.

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

  • (A rem B) dasselbe Vorzeichen wie A und einen Absolutwert kleiner als der Absolutwert von B
  • (A mod B) dasselbe Vorzeichen wie B und einen Absolutwert kleiner als der Absolutwert von B

Modulo

Modulo berechnet den Rest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} der Division Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} geteilt durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} . Man kann eine Funktion definieren, die jedem Zahlenpaar Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n, m)} einen eindeutigen Teilerrest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} zuordnet. Diese nennt man Modulo (von lat. modulus, Kasus Ablativ, also: ‚(gemessen) mit dem (kleinen) Maß (des …)‘; siehe auch wikt:modulo) 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.[1] 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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.}
Die Gaußklammer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a + km) \bmod m = a \bmod m} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k\in\Z,}
aber im Allgemeinen ist
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (-a) \bmod m \ne-(a \bmod m),} z. B. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (-2) \bmod 3=1\ne-2=-(2 \bmod 3).}
Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} positiv, so ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \bmod m\geq0} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a \bmod m) := a - m\cdot (a\,\operatorname{div}\,m)}
Dabei bezeichnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\,\operatorname{div}\,m} den zur Null hin gerundeten Quotienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\,/\,m} , gegeben durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\,\operatorname{div}\,m = \sgn(a)\;\sgn(m) \left \lfloor \frac{|a|}{|m|} \right \rfloor} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sgn(x)} die Vorzeichenfunktion bezeichnet. Für diese Variante gilt
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (-a) \bmod m = -(a \bmod m),}
aber im Allgemeinen
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a + km) \bmod m\ne a \bmod m,} z. B. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (1 - 3) \bmod 3=(-2) \bmod 3=-2\ne 1=1 \bmod 3.}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \bmod m} hat stets dasselbe Vorzeichen wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} , oder es gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \bmod m = 0} .

Gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\geq 0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \bmod b} = ((a % b) + b) % b,

wobei % die symmetrische Modulooperation bezeichnet und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{mod}} die mathematische.

Beispiele

  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 17 \bmod 3 = 2,} da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 17 = 5 \cdot 3 + 2} („3 passt fünfmal in 17 und es bleiben 2 übrig“ – der Rest ist also 2)
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 \bmod 3 = 2,} da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 = 0 \cdot 3 + 2}
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3 \bmod 3 = 0,} da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 3 = 1 \cdot 3 + 0}
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -8 \bmod 6 = -8 - \left\lfloor \frac{-8}{6} \right\rfloor \cdot 6 = -8 - ((-2) \cdot 6 ) = -8 + 12 = 4}

Aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \bmod m = b \bmod m} folgt nicht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a = b} , sondern nur, dass sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} um ein ganzzahliges Vielfaches von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} unterscheiden, also: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a = b + (k \cdot m)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \in \Z} . Eine derartige Gleichung kann auch einfacher mit Hilfe der in der Zahlentheorie verbreiteten Kongruenzrelation geschrieben werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\equiv b\mod m} oder auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \equiv_{m} b}

Üblich ist auch die Schreibweise

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a = b \pmod m,}

sowohl mit als auch ohne die Klammer, und zwar nicht nur, wo dies ohne die Klammer bei Betrachtung als Restoperator stimmen würde, etwa Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 = 11 \pmod {10},} sondern auch sonst:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 11 = 1 \pmod {10}} oder gar
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 11 = 21 \pmod {10}}

Hintergrund ist hier, dass man dann die durch den Repräsentanten 1 eindeutig bestimmte Äquivalenzklasse der zu 1 modulo m kongruenten Zahlen als ein Element des Restklassenrings Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z_m} versteht; in diesem Sinne sind die beiden Ausdrücke als verschiedene Repräsentanten derselben Äquivalenzklasse tatsächlich gleich. In der Praxis ergibt sich kein Unterschied zur Verwendung des Kongruenzsymbols.

Grundrechenarten modulo einer natürlichen Zahl

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.

Beispiele

  • Modulo 3: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left((2 \bmod 3) + (2 \bmod 3)\right) \bmod 3 = 4 \bmod 3= 1 \bmod 3}
  • Modulo 5: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left((3 \bmod 5) \cdot (3 \bmod 5)\right) \bmod 5 = 9 \bmod 5 = 4 \bmod 5}

Verallgemeinerung: Reelle Zahlen

Sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} reelle Zahlen, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ungleich 0, dann kann man eine Division mit Rest folgendermaßen definieren: Der ganzzahlige Quotient Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} und Rest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} im halboffenen Intervall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [0, |b|)} sind diejenigen (eindeutig bestimmten) Zahlen, die die Gleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a = b \cdot c + r} erfüllen.

Auch hier gibt es die Alternativen, dem Rest dasselbe Vorzeichen wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} zu geben oder den betragskleinsten Rest zu wählen. Letztere Alternative entspricht der Rundung: Die Division mit Rest von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} durch 1 liefert eine ganze Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} und eine reelle Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} mit Betrag kleiner oder gleich 1/2, die die Gleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a = c + r} erfüllen. Die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} ist der auf ganze Zahlen gerundete Wert von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} .

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 Polynome muss das als Divisor auftretende Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(X)} aus dem Polynomring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R[X]} (über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} , einem kommutativen Ring mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} ) eine Voraussetzung erfüllen: Der Leitkoeffizient von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(X)} muss eine Einheit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} sein (insbes. ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(X)} nicht das Nullpolynom). Unter dieser Bedingung gibt es zu jedem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(X) \in R[X]} eindeutig bestimmte Polynome Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(X), r(X) \in R[X]} mit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(X) = q(X) \cdot f(X) + r(X)}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{deg}(r) < \operatorname{deg}(f)}

Dabei wird dem Nullpolynom ein kleinerer Grad als jedem anderen Polynom gegeben, beispielsweise Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -\infty} .

Beispiel
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2X^2 + 4X + 5 =(2X + 2)(X + 1) + 3 \in \R[X]}

Die Polynome Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q(X)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r(X)} lassen sich durch Polynomdivision bestimmen.

Anwendung

Programmierung

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} gerade ist, indem man folgende Abfrage durchführt: if ((x mod 2) == 0). Modulo kann man auch nutzen, wenn man in einer Schleife lediglich bei jedem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} -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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} eine Zweierpotenz ist, kann der Divisionsrest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \operatorname{mod} b} auch mit dem bitweisen Und-Operator (UND) berechnet werden. Denn dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \, \operatorname{mod} \, b = a \, \operatorname{UND} \, (b-1)} . Mit dieser Operation erhält man die niedrigwertigsten Bits oder letzten Ziffern im Dualsystem.

Weitere Anwendungen

Siehe auch

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

Weblinks

Einzelnachweise

  1. ↑ Ken Thompson: Users' Reference to B. Hrsg.: Bell Telephone Laboratories. 7. Januar 1972, S. 10 (englisch, bell-labs.com [PDF]).
Abgerufen von „https://de.wikiup.org/index.php?title=Division_mit_Rest&oldid=223540111“