Zum Inhalt springen

Wie funktioniert Modulo, auch mit negativen Zahlen?

Reste nach jeder Vorzeichenregel, Modulopotenzen und Inverse, auf einem Zifferblatt veranschaulicht.

Rechenart

−31 mod 12

5

−31 = −3 × 12 + 5: Der Rest ist das, was nach dem Abziehen ganzer Vielfacher von 12 übrig bleibt.

Wichtige Werte als Tabelle
Vorzeichenregelqr
Nie negativ (Mathematik)−35
Vorzeichen von n (Python, Excel)−35
Vorzeichen von a (JavaScript, C, Java)−2−7
Quotient q
−3
Kongruenz
−31 ≡ 5 (mod 12)
Nie negativ (Mathematik)
5
Vorzeichen von n (Python, Excel)
5
Vorzeichen von a (JavaScript, C, Java)
−7

Reste nach jeder Vorzeichenregel, Modulopotenzen und Inverse, auf einem Zifferblatt veranschaulicht.

Anleitung

  1. Wähle a mod n, eine Modulopotenz aᵇ mod n oder eine modulare Inverse a⁻¹ mod n.
  2. Gib die ganzen Zahlen ein oder ziehe den Punkt auf dem Zifferblatt, um a zu ändern.
  3. Wähle bei einer negativen Zahl die passende Vorzeichenregel; die Ergebnisse von Mathematik, Python und JavaScript stehen nebeneinander.

So funktioniert es

a mod n ist der Rest r, nachdem ganze Vielfache von n abgezogen wurden: a = q × n + r. Stell dir ein Zifferblatt mit n Zahlen vor, 0 oben: Starte bei 0 und gehe a Schritte (bei negativem a rückwärts); r ist die Stelle, an der du landest. 31 Stunden vor Mitternacht zeigt eine 12-Stunden-Uhr 5, denn −31 = −3 × 12 + 5.

Bei negativen Zahlen unterscheiden sich die Regeln darin, welchen Namen sie dieser Stelle geben. Die Mathematik nutzt den euklidischen Rest, nie negativ (0 ≤ r < |n|). Python und Excel runden q ab, daher hat r das Vorzeichen von n. Das % von JavaScript, C und Java rundet q zur 0 hin, daher hat r das Vorzeichen von a: −31 % 12 ist dort −7. Die Ergebnisse unterscheiden sich um n und sind kongruent: −7 ≡ 5 (mod 12).

Modulopotenzen findet man durch wiederholtes Quadrieren: 4¹³ mod 497 = 445, ohne 4¹³ je voll auszuschreiben. Die Inverse von a ist das x mit a × x ≡ 1 (mod n), gefunden mit dem erweiterten euklidischen Algorithmus: 3 × 4 = 12 ≡ 1 (mod 11), also 3⁻¹ mod 11 = 4. Sie existiert nur, wenn a und n keinen gemeinsamen Faktor haben. Quellen: Khan Academy, modulare Arithmetik; OpenStax Contemporary Mathematics, Abschnitt 3.7.

Rechenbeispiel

Was ist −31 mod 12?

  1. Schreibe −31 = q × 12 + r. In der Mathematik ist q = −3, also r = −31 − (−3 × 12) = 5.
  2. JavaScript und C runden den Quotienten stattdessen zur 0 hin: q = −2, also ist der Rest −7.

5 in der Mathematik und in Python, −7 in JavaScript; die beiden unterscheiden sich um 12.

Häufige Fragen

Warum ergibt −7 % 3 in JavaScript −1, in Python aber 2?

JavaScript rundet den Quotienten zur 0 hin (−2), der Rest ist also −7 − (−6) = −1. Python rundet ab (−3), der Rest ist −7 − (−9) = 2. Beides ist nach der jeweiligen Regel richtig.

Wie bekomme ich im Code immer einen nicht negativen Rest?

Nutze ((a % n) + n) % n bei positivem n. Das macht aus dem abgeschnittenen Rest von JavaScript oder C den euklidischen.

Wo wird modulare Arithmetik verwendet?

Bei Uhren und Kalendern, Prüfziffern wie bei IBAN und ISBN, Hashtabellen und in der Public-Key-Kryptografie wie RSA, die auf Modulopotenzen und Inversen beruht.

Warum gibt es keine Inverse von 4 mod 6?

4 und 6 haben den gemeinsamen Faktor 2, daher ist jedes Vielfache von 4 modulo 6 gerade und kann nie 1 sein.

Was ist der Unterschied zwischen Modulo und Rest?

Bei positiven Zahlen gibt es keinen. Bei negativen Zahlen liefert „mod“ meist ein Ergebnis von 0 bis n − 1 (oder mit dem Vorzeichen von n), während ein „Rest“ wie das % in JavaScript das Vorzeichen von a übernimmt.

Feedback senden