Modulo-Rechner

-47 ÷ 5 = -9 Rest -2 (abgeschnitten); -2 + 5 = 3, also ist -47 mod 5 = 3 und -47 ≡ 3 (mod 5)

a

Der Dividend, die Zahl, die reduziert wird. Er darf negativ sein, und genau das ist der Fall, den es zu prüfen lohnt: a mod n muss nicht negativ herauskommen, auch wenn a es ist, also muss -47 bei 3 landen und nicht bei -2. Ganze Zahlen von -1.000.000.000 bis 1.000.000.000 werden angenommen, und auch 0 ist ein völlig brauchbarer Dividend, dessen Rest immer 0 ist

n

Der Modul, die Zahl, durch die geteilt wird. Auch er darf negativ sein, und der Rest ändert sich dadurch nicht: 47 mod -5 und 47 mod 5 sind beide 2, denn die Aussage »n teilt a - r« und die Aussage »-n teilt a - r« sagen dasselbe. Null ist der eine Wert, der abgelehnt wird, und die Seite gibt n genauso aus, wie Sie es eingegeben haben, statt es durch seinen Betrag zu ersetzen

r

Der Rest, und das ist die Antwort. Er ist die kleinste nicht negative Zahl, die man von a abziehen kann und dabei ein Vielfaches von n übrig lässt. Zwei Bedingungen legen ihn vollständig fest: r ist mindestens 0, und r ist strikt kleiner als der Betrag von n. -47 mod 5 ergibt 3, weil 3 der kleinste nicht negative Wert ist, für den -47 - 3 = -50 ein Vielfaches von 5 ist

((a mod n) + |n|) mod |n|

Das zweischrittige Rezept, dem die Seite folgt, und der Grund für den zweiten Schritt. Der erste Schritt ist das, was die meisten Sprachen berechnen, und er kann ein negatives Ergebnis zurückgeben; der zweite Schritt addiert den Betrag des Moduls und reduziert erneut, was das Ergebnis in das nicht negative Intervall schiebt, ohne zu ändern, von welchem Vielfachen von n aus gemessen wird. Dass dabei der Betrag von n verwendet wird und nicht n selbst, lässt einen negativen Modul unverändert durch

a ≡ r (mod n)

Die Kongruenz, und das ist die erste Zeile der Ergebnisanzeige. Sie besagt, dass n die Differenz a - r ohne Rest teilt, und sie ist dieselbe Aussage wie der Rest allein, nur mit Modul und Dividend daneben genannt. Das Dreifachstrich-Zeichen und das Schlüsselwort mod sind Notation und keine Wörter, deshalb werden sie in jeder Sprache dieser Website identisch ausgegeben, und es werden keine Tausendertrennzeichen in die Zahlen gesetzt

-47 ≡ 3 (mod 5)

Die Standardeingabe, vollständig ausgeschrieben. Sie ist der Fall, der diese Seite von einem Rest-Rechner trennt: dieselben zwei Zahlen ergeben -9 mit Rest -2 unter der abgeschnittenen Konvention, die ein gewöhnlicher Taschenrechner benutzt, und hier eben -47 ≡ 3 (mod 5). Setzt man 47 statt -47 ein, kommt 2 statt 3 heraus, ein einziges Minuszeichen verschiebt die Antwort also um einen ganzen Schritt im Zyklus

Diese Seite ist die richtige, sobald die Antwort umlaufen soll statt anzuhalten. Die Uhr ist das älteste Beispiel: 10 Uhr plus 5 Stunden ist 3 Uhr, also 15 mod 12, und dass der Rest nie negativ herauskommt, hält ein Zifferblatt überhaupt lesbar. Kalenderrechnung hat dieselbe Gestalt — der 100. Tag eines Jahres oder der Wochentag eines Datums ist ein Rest modulo 7. In der Programmierung prüft man mit einem Modulo, ob eine Zahl eine andere teilt (a mod n ist genau dann 0, wenn n ohne Rest hineingeht), man faltet damit einen Index in einen Ringpuffer oder eine Hash-Tabelle zurück in den gültigen Bereich, man hält damit einen laufenden Zähler in festen Grenzen und wählt damit der Reihe nach einen Eintrag aus einer Liste aus. Die Kryptografie baut darauf auf: RSA und Diffie-Hellman sind modulares Rechnen mit sehr großen Zahlen, und der eigentliche Grund, den Rest als nicht negativ zu definieren, ist, dass eine vorzeichenbehaftete Antwort eine mehrdeutige Grundlage zum Weiterrechnen wäre. Prüfziffern, von der Kontonummer bis zur ISBN, sind Reste modulo 9, 10 oder 11. Geht es dagegen darum, wie oft die Division hineingeht und was nach der Konvention Ihres Taschenrechners übrig bleibt, ist der Divisionsrest-Rechner die bessere Seite, weil er beide Konventionen nebeneinander legt; geht es um das, was zwei Zahlen gemeinsam haben, beantwortet das der ggT-Rechner direkt. Ist die Frage schließlich, ob eine Zahl ohne Rest teilbar ist, gibt es dafür die Teilbarkeit als eigene Fragestellung — sie ist derselbe Rest, nur auf die eine Frage verkürzt.

1. Die Vorzeichenfalle: -47 mod 5

   1. Wie gewohnt teilen und den Bruchteil wegwerfen: -47 ÷ 5 = -9,4, der abschneidende Quotient ist also -9
   2. -9 × 5 = -45, und -47 - (-45) = -2, der abgeschnittene Rest ist also -2
   3. Der Rest muss mindestens 0 sein, also den Betrag des Moduls addieren: -2 + 5 = 3
   4. Prüfen, ob das Ergebnis im Intervall liegt: 0 ≤ 3 < 5, es ist also keine weitere Korrektur nötig
   5. Die Kongruenz lesen: -47 ≡ 3 (mod 5), das heißt, 5 teilt -47 - 3 = -50 ohne Rest

   Die Standardeingabe, und der Fall, der erklärt, warum es diese Seite überhaupt gibt. Ein einfacher Taschenrechner und die meisten Programmiersprachen melden für diese Division -9 mit Rest -2; diese Antwort ist nicht falsch, sie beantwortet nur eine anders formulierte Frage. Der Rest ist hier 3, weil 3 der kleinste nicht negative Wert ist, der ein Vielfaches von 5 übrig lässt. Beachten Sie, dass 47 mod 5 gleich 2 ist und nicht -3 und nicht 3 — verschiebt man den Dividenden um einen ganzen Schritt im Zyklus, verschiebt sich der Rest um eins, und die beiden Reste unterscheiden sich um genau 1 und nicht um 5.

2. Ein negativer Modul: 47 mod -5

   1. 47 ÷ 5 = 9,4, also geht die 5 neunmal hinein und 9 × 5 = 45
   2. 47 - 45 = 2, und das liegt bereits im Intervall 0 ≤ 2 < 5
   3. Der Modul ist negativ, aber die Teilbarkeit kümmert sich nicht um das Vorzeichen: -5 teilt 45 ohne Rest, also teilt es auch 47 - 2 ohne Rest
   4. Die Kongruenz wird mit dem Modul geschrieben, wie er eingegeben wurde: 47 ≡ 2 (mod -5)

   Der Fall, der zeigt, dass der Rest auf das Vorzeichen des Moduls nicht reagiert. Ersetzt man -5 durch 5, ändert sich an der Antwort nichts, denn -5 teilt eine Zahl genau dann ohne Rest, wenn 5 es tut. Die Seite behält das Minuszeichen in der ausgegebenen Kongruenz, statt es stillschweigend wegzulassen; eine -5 als 5 umzuschreiben sähe so aus, als wäre die Eingabe verworfen worden. Vergleichen Sie die zwei Zeilen der Referenztabelle mit dem Divisor -5 mit den Zeilen mit der 5: Nur das Vorzeichen des Dividenden verschiebt jemals den Rest.

3. Der gewöhnliche Fall: 1.234 mod 12

   1. 12 × 100 = 1.200, und 1.234 - 1.200 = 34, also weiter: 12 × 2 = 24 lässt 34 - 24 = 10 übrig
   2. 12 × 3 = 36 würde über die 34 hinausgehen, der Quotient ist also 102 und der Rest 10
   3. 10 ist mindestens 0 und kleiner als 12, ist also bereits der Rest
   4. Als Kongruenz gelesen: 1234 ≡ 10 (mod 12)

   Der schlichte Fall mit zwei positiven Zahlen, bei dem der Rest und ein gewöhnlicher Divisionsrest übereinstimmen — und genau das ist der Grund, ihn hier zu zeigen. Sind beide Zahlen positiv, gibt es nichts auszugleichen, und die Seite tut dieselbe Arbeit wie jedes Divisionsrest-Werkzeug. Interessant sind die Zeilen mit einem Minuszeichen darin. Dieses Zahlenpaar hat noch eine zweite Lesart, die es wert ist, bemerkt zu werden: 1.234 mod 12 ist die Frage, auf welche Stunde eine Dauer fällt, wenn das Zifferblatt zwölf Stunden hat, und 10 ist eine völlig vernünftige Stunde, während -2 es nicht gewesen wäre.

Der Modul darf nicht null sein. Durch null zu teilen hat keine Antwort, es gibt also keinen Rest zu berichten und schon gar keinen kleinsten nicht negativen; die Seite lehnt die Eingabe ab, statt einen Platzhalter auszugeben, der wie ein Ergebnis aussieht. Beide Zahlen müssen ganz sein. Ein gebrochener Modul hat in manchen Teilgebieten der Mathematik seine eigene Definition, aber es ist nicht die, die diese Seite umsetzt; 47,5 wird deshalb abgelehnt und nicht stillschweigend auf 48 gerundet und dann beantwortet, als wäre das die Frage gewesen. Der Betrag jeder Zahl ist auf eine Milliarde begrenzt; das hält jeden Zwischenschritt in dem Bereich, in dem eine Gleitkommazahl doppelter Genauigkeit ganze Zahlen noch exakt darstellt. Darüber hinaus würde die Arithmetik zu runden beginnen, und die Antwort sähe völlig gewöhnlich aus, während sie falsch wäre. Die Seite berichtet einen Rest und eine Kongruenz und sonst nichts: Sie gibt keinen Quotienten aus, listet nicht die übrigen zu Ihrem Dividenden kongruenten Zahlen auf und rechnet nicht mit mehr als einem Zahlenpaar gleichzeitig. Ein negativer Modul wird angenommen und so ausgegeben, wie er eingegeben wurde, was bedeutet, dass zwei Kongruenzen, die dasselbe aussagen, auf der Seite verschieden aussehen können — 47 ≡ 2 (mod -5) und 47 ≡ 2 (mod 5) sind dieselbe Aussage. Die Referenztabelle unten zeigt schließlich vier feste Zahlenpaare und folgt nicht Ihren Eingaben; die Ergebnisanzeige ist der Teil, der Ihre Eingaben beantwortet.

Warum ist -47 mod 5 gleich 3 und nicht -2?

Weil der Rest als die kleinste nicht negative Zahl definiert ist, die man vom Dividenden abziehen kann und dabei ein Vielfaches des Moduls übrig lässt. Sowohl -2 als auch 3 erfüllen dies in dem Sinn, dass -47 - (-2) = -45 und -47 - 3 = -50 Vielfache von 5 sind; die Arithmetik allein entscheidet also nicht zwischen ihnen. Die Definition tut es: Der Rest lebt im Intervall von 0 bis ausschließlich zum Modul, und -2 liegt außerhalb. Alles Weitere folgt daraus. Was eine Programmiersprache liefert, hängt davon ab, welche Konvention sie gewählt hat, und JavaScript, C, Java und Go haben die andere gewählt — bei ihnen folgt das Vorzeichen dem Dividenden. Python hat diese hier gewählt. Keine der Sprachen ist kaputt; sie beantworten unterschiedlich formulierte Fragen.

Darf der Modul negativ sein?

Ja, und der Rest wird von seinem Vorzeichen nicht berührt. Ein negativer Modul funktioniert, weil die Teilbarkeit Vorzeichen ignoriert: -5 teilt eine Zahl genau dann ohne Rest, wenn 5 es tut, die Menge der Vielfachen von -5 ist also dieselbe wie die der Vielfachen von 5, und die kleinste nicht negative Zahl in dieser Menge ist in beiden Fällen dieselbe. Die Seite gibt den Modul genau so aus, wie er eingegeben wurde, statt -5 durch 5 zu ersetzen, denn die Eingabe umzuschreiben sähe so aus, als wäre das Vorzeichen verworfen worden. 47 mod -5 ist also 2 und 47 mod 5 ebenfalls, und die beiden ausgegebenen Kongruenzen unterscheiden sich nur darin, dass die eine ein Minuszeichen zeigt.

Was passiert, wenn ich 0 als Modul eingebe?

Die Seite lehnt die Eingabe ab. Mod 0 hat keinen Wert zu berichten: Null teilt nur die Null, es gibt also kein ganzzahliges Vielfaches von 0, an dem man den Dividenden messen könnte, und keinen Rest zu bilden. Eine 0 oder den Dividenden selbst auszugeben würde wie eine Antwort aussehen und wäre für jede Eingabe falsch. Die Eingabe abzulehnen ist das ehrliche Ergebnis. Aus demselben Grund ist die Division durch null überall sonst in der Arithmetik undefiniert.

Ist das dasselbe wie der Divisionsrest-Rechner auf dieser Website?

Nein, und die beiden geben auf dieselbe Aufgabe unterschiedliche Antworten, was der deutlichste Weg ist, den Unterschied zu sehen. Die Rest-Seite legt zwei Konventionen nebeneinander und lässt Sie wählen, weil die schriftliche Division tatsächlich in zwei Varianten im Umlauf ist und im Unterricht die eine oder die andere gelehrt werden kann. Diese Seite bietet keine Wahl an, weil der Modulo nur eine Lesart hat: Die Antwort wird nie negativ. Für -47 geteilt durch 5 zeigt die Rest-Seite unter ihrer Standardkonvention -9 mit Rest -2, während diese Seite die Kongruenz -47 ≡ 3 (mod 5) zeigt. Benutzen Sie jene Seite, um zu sehen, wie sich die beiden Konventionen bei einem konkreten Zahlenpaar unterscheiden; benutzen Sie diese, wenn Sie den mathematischen Rest selbst haben wollen.

Wo wird ein solcher Rest tatsächlich gebraucht?

Überall dort, wo ein Zähler umlaufen soll, statt immer weiter zu wachsen. Das Zifferblatt einer Uhr ist der Alltagsfall: zwölf Stunden auf dem Zifferblatt heißen, dass die Stunde nach 10 Uhr plus 5 Stunden 15 mod 12 ist, also 3. Wochentage funktionieren genauso modulo 7. In der Programmierung prüft ein Modulo die Teilbarkeit, weil a mod n genau dann 0 ist, wenn n ohne Rest hineingeht; er faltet einen Index in einem Ringpuffer oder einer Hash-Tabelle zurück in den gültigen Bereich, wo ein über das Ende hinausgelaufener Index wieder am Anfang landen muss; und er hält einen laufenden Zähler in festen Grenzen. Die Public-Key-Kryptografie ist modulares Rechnen mit sehr großen Zahlen, weshalb die nicht negative Konvention so wichtig ist — eine Arithmetik, die vorzeichenbehaftete Ergebnisse liefert, wäre eine mehrdeutige Grundlage.

Warum wird nur die Kongruenz gezeigt und nicht der Quotient?

Weil der Quotient nicht zu dem gehört, was ein Rest aussagt. Eine Kongruenz nennt den Dividenden, den Rest und den Modul, und ihre Behauptung ist, dass der Modul die Differenz der ersten beiden teilt. Diese Aussage ist ohne Quotienten vollständig, denn der Quotient ist die Zahl, die man erhält, wenn man fragt, wie oft der Modul hineinpasst, und diese Frage gehört zur schriftlichen Division. Wenn Sie den Quotienten daneben brauchen, geben ihn der Divisionsrest-Rechner und der Rechner für die schriftliche Division beide aus. Der Rest allein steht außerdem in der zweiten Zeile der Ergebnisanzeige, sodass niemand, der nur die Zahl will, sie aus dem Satz herauslesen muss.

• Modulo — from Wolfram MathWorld (English original; die Definition von a mod n als kleinster nicht negativer Rest und die Rechenregeln, die daraus folgen) — Wolfram MathWorld (United States)
• Congruence — from Wolfram MathWorld (English original; die Schreibweise a ≡ r (mod n) und was es bedeutet, dass eine Zahl die Differenz zweier anderer ohne Rest teilt) — Wolfram MathWorld (United States)
• Remainder — from Wolfram MathWorld (English original; der Divisionsrest und die verschiedenen Konventionen, die bei negativen Zahlen auseinandergehen) — Wolfram MathWorld (United States)
• Ganze Zahlen — Mathebibel: die deutschsprachige Darstellung der negativen Zahlen, ihrer Vorzeichenregeln und der Rechnung mit ihnen; genau der Bereich, in dem ein negativer Dividend den Unterschied zwischen Rest und mathematischem Rest ausmacht — Mathebibel (Deutschland)