Wikipedia · einfach zusammengefasst · Stand
Division mit Rest
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.
Inhalt6 Abschnitte
Grundidee und Definition
Die Division mit Rest ist ein Satz aus Algebra und Zahlentheorie. Für zwei ganze Zahlen a und m mit m ≠ 0 gibt es eindeutig bestimmte ganze Zahlen q und r, sodass
a = m · q + r, 0 ≤ r < |m|.
q heißt Quotient oder Ganzzahlquotient, r heißt Rest. Der Rest ist also der Teil, der übrigbleibt, wenn man vom Dividenden a ein passendes Vielfaches des Divisors m abzieht. Die Zahlen q und r können durch schriftliche Division bestimmt werden. Ein Rest r = 0 bedeutet genau, dass a durch m teilbar ist.
Die Division mit Rest gibt es nicht nur für ganze Zahlen, sondern auch für Polynome. Die allgemeinste mathematische Struktur, in der eine Division mit Rest existiert, heißt euklidischer Ring.
Natürliche Zahlen
Bei natürlichen Zahlen fragt man bei a : m, wie man den Dividenden a als Vielfaches des Divisors m und als kleinen Rest schreiben kann:
a = m · q + r.
Dabei ist q der Ganzzahlquotient und r der Rest. Die entscheidende Bedingung lautet: r ist eine der Zahlen 0, 1, ..., m − 1. Dadurch ist r eindeutig bestimmt.
Der Rest ist 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 entsteht genau dann, wenn der Dividend kein Vielfaches des Divisors ist. Ist der Divisor fest, spricht man zum Beispiel vom Neunerrest einer Zahl, also vom Rest bei Division durch 9.
Typische Beispiele sind:
- 9 : 4 ergibt 2 Rest 1, denn 9 = 4 · 2 + 1.
- 2 : 4 ergibt 0 Rest 2, denn 2 = 4 · 0 + 2.
- 4 : 4 ergibt 1 Rest 0, denn 4 = 4 · 1 + 0.
Die Schulschreibweise „9 : 4 = 2, Rest 1“ ist anschaulich, aber fachwissenschaftlich problematisch, weil sie mit dem Gleichheitszeichen missverständlich sein kann. Deshalb werden Schreibweisen wie 9 : 4 = 2 + 1 : 4 oder 9 = 4 · 2 + 1 bevorzugt.
An Grundschulen kann man Division mit Rest durch Verteilen erklären: Bei „7 geteilt durch 3 ergibt 2 Rest 1“ kann man 7 Murmeln an 3 Kinder verteilen, sodass jedes Kind 2 Murmeln bekommt und 1 Murmel übrigbleibt. Man kann auch 7 Murmeln in 3er-Päckchen aufteilen; dann entstehen 2 volle Päckchen und 1 Murmel bleibt übrig.
Für bestimmte Teiler kann man den Rest oft direkt an der Dezimaldarstellung erkennen: Bei Division durch 2 entscheidet die letzte Ziffer über Rest 0 oder 1. Bei Division durch 3 oder 9 ist der Rest derselbe wie der Rest der iterierten Quersumme. Bei Division durch 5 hängt der Rest von der letzten Ziffer ab. Bei Division durch 10, 100, 1000 usw. ist der Rest die letzte, die letzten zwei, die letzten drei usw. Ziffern.
Ganze Zahlen und Restkonventionen
Bei ganzen Zahlen a und m ≠ 0 gibt es mehrere mögliche Konventionen für das Vorzeichen des Restes. Alle Fassungen verwenden eindeutig bestimmte ganze Zahlen q und r mit
a = mq + r, |r| < |m|,
legen aber unterschiedlich fest, welches Vorzeichen r haben soll. Für a ≥ 0 und m > 0 liefern alle Fassungen denselben nichtnegativen Rest.
In der Hauptfassung ist der Rest nichtnegativ: r ≥ 0, also 0 ≤ r < |m|. Dann ist mq das größte Vielfache von m, das kleiner oder gleich a ist. Beispiel: Bei −25 geteilt durch −4 ist das größte Vielfache von −4, das kleiner oder gleich −25 ist, die Zahl −28 = (−4) · 7. Daher gilt −25 = (−4) · 7 + 3, also Quotient 7 und Rest 3. Der Ganzzahlquotient kann mit der Gaußklammer oder Floor-Funktion berechnet werden:
q = sgn(m) · ⌊a / |m|⌋,
und danach r = a − mq.
Eine zweite Fassung fordert, dass der Rest das Vorzeichen des Divisors hat: r ≥ 0 für m > 0 und r ≤ 0 für m < 0. Dann kann man den Quotienten berechnen durch
q = ⌊a / m⌋,
und wieder r = a − mq. Für −25 : −4 ergibt sich dann −25 = (−4) · 6 + (−1), also Quotient 6 und Rest −1.
Eine dritte Fassung fordert, dass der Rest das Vorzeichen des Dividenden hat: r ≥ 0 für a ≥ 0 und r ≤ 0 für a ≤ 0. Der Quotient kann berechnet werden durch
q = sgn(a)sgn(m)⌊|a| / |m|⌋ = sgn(a/m)⌊|a/m|⌋,
und der Rest wieder durch r = a − mq. Auch hier ergibt −25 : −4 den Quotienten 6 und den Rest −1.
Modulo und Kongruenz
Modulo bezeichnet die Restbildung bei der Division a geteilt durch m. Eine Modulo-Funktion ordnet einem Zahlenpaar (a, m) mit m ≠ 0 einen eindeutigen Rest r zu. Eine im Artikel betrachtete Variante ist
mod: ℤ × (ℤ \ {0}) → ℤ, (a, m) ↦ a mod m := a − ⌊a/m⌋ · m.
Die Gaußklammer ⌊x⌋ bezeichnet die größte ganze Zahl, die nicht größer als x ist. Für diese Variante gilt immer
(a + km) mod m = a mod m für alle k ∈ ℤ.
Im Allgemeinen gilt aber nicht (−a) mod m = −(a mod m); zum Beispiel ist (−2) mod 3 = 1 ≠ −2 = −(2 mod 3). Ist m positiv, so ist a mod m ≥ 0 für alle a.
Beispiele sind: 17 mod 3 = 2, weil 17 = 5 · 3 + 2; 2 mod 3 = 2; 3 mod 3 = 0; und −8 mod 6 = −8 − ⌊−8/6⌋ · 6 = −8 − ((−2) · 6) = 4.
Neben dieser mathematischen Variante wird auch die symmetrische Variante als Modulo bezeichnet. Sie verwendet den zur Null hin gerundeten Quotienten a div m. Dann gilt
(a mod m) := a − m · (a div m),
wobei a div m = sgn(a)sgn(m)⌊|a|/|m|⌋. Für diese Variante gilt (−a) mod m = −(a mod m), aber im Allgemeinen nicht (a + km) mod m = a mod m; zum Beispiel ist (1 − 3) mod 3 = (−2) mod 3 = −2 ≠ 1 = 1 mod 3. Der Rest hat hier dasselbe Vorzeichen wie a oder ist 0. Für a ≥ 0 und m > 0 stimmen beide Varianten überein.
Zwei ganze Zahlen a und b heißen kongruent modulo m, wenn sie bei Division durch m denselben Rest haben, also wenn ihre Differenz a − b durch m teilbar ist. Man schreibt a ≡ b (mod m). Es gilt
a mod m = b mod m ⇔ a ≡ b (mod m),
für die passende Modulo-Verknüpfung der nichtnegativen Restfassung beziehungsweise der Divisor-Vorzeichen-Fassung, aber nicht für die Dividenden-Vorzeichen-Fassung. Beispiel: 43 und −7 haben bei Division durch 5 denselben nichtnegativen Rest, denn 43 mod 5 = 3 = (−7) mod 5. Außerdem ist 43 − (−7) = 50 durch 5 teilbar, also 43 ≡ −7 (mod 5). Die Kongruenz modulo m ist eine Äquivalenzrelation; ihre |m| Äquivalenzklassen heißen Restklassen und bilden den Restklassenring modulo m.
Computer und weitere Zahlbereiche
In Computersystemen sind Befehle oder Operatoren für ganzzahlige Division und Restbildung in den meisten Programmiersprachen und Prozessoren vorhanden. Manche Sprachen unterscheiden mehrere Varianten. In Ada hat a rem m dasselbe Vorzeichen wie a, während a mod m dasselbe Vorzeichen wie m hat; beide Reste haben einen Absolutbetrag kleiner als der von m.
Die implementierte Variante ist nicht einheitlich: Ruby, Perl, Python, Excel und der Rechner der Googlesuche verwenden die mathematische Variante. C, Java, JavaScript und PHP verwenden die symmetrische Variante. Das ist besonders bei Portierungen wichtig. Wenn in C(++) oder Java nur die symmetrische Variante verfügbar ist, kann man die mathematische Variante berechnen durch
a mod m = ((a % m) + m) % m,
wobei % die symmetrische Modulooperation bezeichnet.
Für reelle Zahlen a und m mit m ≠ 0 kann man eine Division „a durch m mit Rest“ so definieren, dass q ganzzahlig ist und r im halboffenen Intervall [0, |m|) liegt, mit a = m · q + r. Auch hier gibt es Alternativen, etwa einen Rest mit demselben Vorzeichen wie m oder den betragskleinsten Rest zu wählen. Bei Division durch 1 entspricht die Wahl des betragskleinsten Restes dem Runden: a = q + r mit |r| ≤ 1/2, wobei q der auf ganze Zahlen gerundete Wert von a ist.
Bei Polynomen ist Division mit Rest möglich, wenn das Divisorpolynom f(X) aus R[X] einen Leitkoeffizienten hat, der eine Einheit von R ist; insbesondere ist f(X) nicht das Nullpolynom. Dann gibt es zu jedem g(X) ∈ R[X] eindeutig bestimmte Polynome q(X) und r(X) mit
g(X) = f(X) · q(X) + r(X), deg(r) < deg(f).
Der Rest wird durch Polynomdivision bestimmt. Im Polynomring ℝ[X] gilt zum Beispiel
2X² + 4X + 5 = (X + 1) · (2X + 2) + 3.
Wichtige Anwendungen
Eine zentrale Anwendung ist der euklidische Algorithmus zur Berechnung des größten gemeinsamen Teilers, kurz ggT, zweier ganzer Zahlen. Er nutzt, dass sich der ggT nicht ändert, wenn man von einer Zahl ein Vielfaches der anderen abzieht:
ggT(a, m) = ggT(a − mq, m).
Wählt man q als Ganzzahlquotienten, dann ist a − mq der Rest r. Danach teilt man abwechselnd weiter, bis eine Zahl 0 wird. Dann gilt ggT(a, 0) = |a| = ggT(0, a). Für 68 und 30 beginnt die Rechnung mit 68 = 30 · 2 + 8, also ggT(68, 30) = ggT(8, 30). Danach folgt 30 = 8 · 3 + 6, also ggT(8, 30) = ggT(8, 6), und schließlich erhält man ggT(68, 30) = 2. Die gemeinsamen Teiler von 68 und 30 sind die Teiler von 2, nämlich 1, 2, −1 und −2.
Der erweiterte euklidische Algorithmus bestimmt zusätzlich zu g = ggT(a, b) ganze Zahlen u und v mit
g = ua + vb.
Im Beispiel a = 68 und b = 30 ergibt sich g = 2 und im Artikel die Darstellung g = 4a − 9b.
In der Programmierung wird Modulo häufig verwendet. Man kann zum Beispiel prüfen, ob eine Zahl a gerade ist, indem man testet, ob a mod 2 == 0 gilt. Modulo kann auch genutzt werden, um nur bei jedem a-ten Schleifendurchlauf bestimmten Code auszuführen, Teilbarkeit zu prüfen oder auf ganze Vielfache einer Zahl zu ergänzen, etwa auf 4 Bytes. Die Funktion divMod berechnet Ganzzahlquotient und Rest zusammen.
Ein Beispiel ist eine Uhr mit einem Sekundenwert seit 0 Uhr. Ist Sekundenwert mod 3600 gleich 0, beginnt eine volle Stunde. Mit Sekundenwert mod 60 erhält man die Sekunden seit der letzten vollen Minute. Ist m eine Zweierpotenz, kann der Rest a mod m auch durch den bitweisen Und-Operator berechnet werden: a mod m = a UND (m − 1). Dadurch erhält man die niedrigwertigsten Bits, also die letzten Ziffern im Dualsystem.
Weitere Anwendungen sind Prüfziffern der Internationalen Standardbuchnummer und der CAS-Nummer, der Luhn-Algorithmus, Prüfsummen bei CRC und FEC, Kalenderberechnungen wie das Osterdatum und Zellers Kongruenz, die Prüfsumme der IBAN, kryptographische Verfahren wie Diffie-Hellman-Schlüsselaustausch und RSA-Kryptosystem, die Geometrie von Schröderdiffusoren und die Bildung binärer Fraktale.
