Zuletzt aktualisiert: 2026-06-05

Grundbegriff: Kongruenz und Modulo

Modulare Arithmetik ist das Teilgebiet der Zahlentheorie, das sich mit ganzen Zahlen unter einem festen Teiler, dem Modulus, befasst. Zwei ganze Zahlen $a$ und $b$ heißen kongruent modulo $n$, wenn ihre Differenz ein Vielfaches von $n$ ist:

$a \equiv b \pmod{n}$

Die drei Rechenoperationen dieses Rechners – Modulo, modulare Potenzierung und modulare Inverse – bauen alle auf diesem Begriff auf.

Die Modulo-Operation

Für eine positive ganze Zahl $n$ ist $a \bmod n$ die eindeutige ganze Zahl $r \in [0, n-1]$ mit:

$a = q \cdot n + r, \qquad q = \lfloor a / n \rfloor$

Der ganzzahlige Quotient $q$ ist der Gaußsche Klammerterm $\lfloor a/n \rfloor$, der Rest $r$ ist das Ergebnis der Modulo-Operation. Diese Definition liefert stets ein nicht-negatives Ergebnis – im Unterschied zum abgeschnittenen Rest vieler Programmiersprachen.

Rechenbeispiel: $a = 17$, $n = 5$

$q = \lfloor 17 / 5 \rfloor = 3, \qquad r = 17 - 3 \cdot 5 = 2$

Also $17 \bmod 5 = 2$. Das entspricht der Uhrzeigerscheibe: 17 Schritte auf einem Zifferblatt mit fünf Positionen landen auf Position 2.

Negative Werte: $a = -7$, $n = 5$

$q = \lfloor -7 / 5 \rfloor = -2, \qquad r = -7 - (-2) \cdot 5 = 3$

Daher ist $-7 \bmod 5 = 3$ (nicht $-2$). Der %-Operator in C und JavaScript liefert dagegen $-2$, weil er den abgeschnittenen Rest verwendet.

Euklidische Identität

Für jedes Paar $(a, n)$ mit $n \geq 1$ gelten der ganzzahlige Quotient $q$ und der Rest $r$ der Identität:

$a = q \cdot n + r, \qquad 0 \leq r < n$

Dieser Rechner zeigt beide Größen ($r$ und $q$), sodass die Identität für beliebige Eingaben direkt überprüft werden kann.

Modulare Potenzierung

$a^b \bmod n$ direkt zu berechnen – also erst $a^b$ ausrechnen und dann reduzieren – ist für große Exponenten nicht praktikabel, da $a^b$ exponentiell wächst. Das Quadrieren-und-Multiplizieren (englisch: square-and-multiply) löst dieses Problem: Nach jeder Operation wird modulo $n$ reduziert, sodass alle Zwischenwerte im Bereich $[0, n-1]$ bleiben.

Der Exponent wird binär zerlegt. Beginnend mit $\text{Ergebnis} = 1$:

• Von links nach rechts wird die laufende Basis quadriert (modulo $n$).
• Ist das aktuelle Bit 1, wird das Ergebnis mit der aktuellen Basispotenz multipliziert (modulo $n$).

Der Aufwand beträgt höchstens $2\log_2 b$ Multiplikationen statt $b - 1$.

Rechenbeispiel: $a = 17$, $b = 3$, $n = 5$

$17 \equiv 2 \pmod 5$ $17^2 \equiv 4 \pmod 5$ $17^3 = 17^2 \cdot 17 \equiv 4 \cdot 2 = 8 \equiv 3 \pmod 5$

Also $17^3 \bmod 5 = 3$. Probe: $17^3 = 4913 = 982 \cdot 5 + 3$. ✓

Modulare Inverse

Die modulare Inverse von $a$ modulo $n$ ist eine ganze Zahl $x$ mit:

$a \cdot x \equiv 1 \pmod{n}$

Sie existiert genau dann, wenn $\gcd(a, n) = 1$ gilt – das heißt, wenn $a$ und $n$ teilerfremd sind. Ist $n$ eine Primzahl, besitzt jede ganze Zahl von $1$ bis $n-1$ eine Inverse. Bei zusammengesetztem $n$ fehlt die Inverse für alle $a$, die einen gemeinsamen Teiler mit $n$ haben.

Erweiterter euklidischer Algorithmus

Die Inverse wird durch den erweiterten euklidischen Algorithmus bestimmt. Er verfolgt zusätzlich zur gewöhnlichen ggT-Berechnung ganzzahlige Linearkombinationen und findet ganze Zahlen $s$ und $t$ mit:

$a \cdot s + n \cdot t = \gcd(a, n)$

Gilt $\gcd(a, n) = 1$, so ist $s$ die gesuchte modulare Inverse.

Rechenbeispiel: $a = 3$, $n = 5$

Schritte des erweiterten euklidischen Algorithmus:

• $5 = 1 \cdot 3 + 2$
• $3 = 1 \cdot 2 + 1$

Rückwärtseinsetzen: $1 = 3 - 1 \cdot 2 = 3 - 1 \cdot (5 - 1 \cdot 3) = 2 \cdot 3 - 1 \cdot 5$

Daher ist $3 \cdot 2 \equiv 1 \pmod 5$, also $3^{-1} \equiv 2 \pmod 5$.

Probe: $3 \cdot 2 = 6 = 1 \cdot 5 + 1$. ✓

Anwendungsgebiete

Modulare Arithmetik ist ein Grundbaustein der modernen Mathematik und Informatik:

Bereich	Verwendung
Asymmetrische Kryptografie (RSA)	Nachrichten werden mit einem großen Exponenten modulo einem Primzahlprodukt potenziert; Entschlüsselung nutzt die modulare Inverse des Schlüsselexponenten
Prüfsummen	ISBN-13, IBAN und der Luhn-Algorithmus für Kreditkartennummern erkennen Tippfehler mithilfe modularer Arithmetik
Kalenderrechnung	Der Wochentag nach $d$ Tagen ergibt sich als Rest modulo 7; Ostertermine folgen zyklischen Kongruenzen
Hash-Tabellen	Ein Schlüssel wird per Modulo auf einen Tabellenindex abgebildet
Ringpuffer	Lese- und Schreibzeiger kreisen mit Index mod Kapazität durch den Puffer

Kurzübersicht

Begriff	Formel
Modulo-Definition	$a = q \cdot n + r,\quad 0 \leq r < n$
Ganzzahliger Quotient	$q = \lfloor a/n \rfloor$
Modulare Potenzierung	$a^b \bmod n$ mit Quadrieren-und-Multiplizieren
Inverse (Existenzbedingung)	$\gcd(a, n) = 1$
Erweiterter euklidischer Algorithmus	$a \cdot s + n \cdot t = \gcd(a, n)$, $s$ ist die Inverse

Häufig gestellte Fragen (FAQ)

Was ist der Unterschied zwischen mathematischem Modulo und dem Rest bei negativen Zahlen?

Das mathematische Modulo liefert stets ein nicht-negatives Ergebnis im Bereich [0, n − 1]. Zum Beispiel gilt −7 mod 5 = 3, weil −7 = (−2) × 5 + 3. Viele Programmiersprachen verwenden hingegen den abgeschnittenen Rest: In C und JavaScript ergibt −7 % 5 den Wert −2. Python 3 hingegen folgt der mathematischen Definition und liefert ebenfalls 3. Dieser Rechner nutzt die mathematische Definition.

Wie wird eine große Potenz wie 17^1000 mod 5 effizient berechnet?

Die schnelle modulare Potenzierung (auch als Quadrieren-und-Multiplizieren bekannt) reduziert die Anzahl der nötigen Multiplikationen auf O(log b). Der Exponent wird binär zerlegt: In jedem Schritt wird der Zwischenwert quadriert oder quadriert und mit der Basis multipliziert; nach jeder Operation erfolgt eine Reduktion modulo n, sodass die Zahlen klein bleiben.

Wann existiert eine modulare Inverse?

Die modulare Inverse a⁻¹ mod n existiert genau dann, wenn ggT(a, n) = 1 gilt – das heißt, wenn a und n teilerfremd sind. Ist n eine Primzahl, besitzt jede ganze Zahl von 1 bis n − 1 eine Inverse. Bei zusammengesetztem n fehlt die Inverse für alle a, die einen gemeinsamen Teiler mit n haben.

Wo wird modulare Arithmetik in der Praxis eingesetzt?

Modulare Arithmetik bildet die Grundlage der asymmetrischen Kryptografie: Das RSA-Verfahren, das unter anderem HTTPS und digitale Signaturen absichert, beruht auf modularer Potenzierung und Inversen. Weitere Anwendungsgebiete sind Prüfsummen (ISBN-13, IBAN, Luhn-Algorithmus für Kreditkartennummern), Kalenderberechnungen (Wochentag als Rest modulo 7) sowie Ringpuffer und zyklische Datenstrukturen in der Softwareentwicklung.