Modulo-Rechner – Rest berechnen (a mod n), Kongruenz prüfen, Potenz modulo n

Wählen Sie, was Sie berechnen möchten, und geben Sie ganze Zahlen ein. „Rest“ funktioniert auch mit negativen Zahlen und zeigt den Unterschied zwischen dem mathematischen Rest (ab 0) und dem %-Operator beim Programmieren.

Berechnung

Ganze Zahl a

Ganze Zahl b (Vergleich)

Exponent k (hoch k)

Modul n (Divisor)

Geben Sie nur ganze Zahlen ein (keine Dezimalzahlen oder Brüche). a, b und n dürfen bis zu 30 Stellen haben, der Exponent k ist mindestens 0 mit bis zu 9 Stellen, und der Modul n ist mindestens 1.

Ergebnis und Figur

Wählen Sie links, was Sie berechnen möchten, geben Sie ganze Zahlen ein und klicken Sie auf „Berechnen“. Das Ergebnis erscheint dann hier (bei einem Modul n von 2 bis 24 zeigt ein Zifferblatt, wo der Rest landet).

Inhaltsverzeichnis

[ Schließen X ]

Das können Sie auf dieser Seite
Wofür braucht man diese Berechnung?
Anleitung
Formeln und Abbildungen
Symbole und Begriffe
- Symbole
- Begriffe
Das sollten Sie vorher wissen
So berechnen Sie es in Excel
So berechnen Sie es in Google Tabellen
So berechnen Sie es in Python
So schreiben Sie die Formel in LaTeX und anderen Formelsprachen (zum Kopieren)
So lassen Sie ChatGPT rechnen
Die Vorteile von DataChef
Verwandte Funktionen
Alle Rechner von NumberChef

Das können Sie auf dieser Seite

Den Rest berechnen, der beim Teilen einer ganzen Zahl $a$ durch $n$ bleibt. Auch negative Zahlen sind möglich (zum Beispiel $-7$ geteilt durch $3$): Die Seite zeigt den mathematischen Rest ($0 \le r < n$) neben dem Ergebnis des %-Operators in C, Java, JavaScript und ähnlichen Sprachen (das negativ sein kann)
Prüfen, ob die Kongruenz $a \equiv b \pmod{n}$ gilt – mit Begründung: Ist die Differenz $a - b$ ein Vielfaches von $n$?
Den exakten Rest riesiger Potenzen wie $7^{100}$ geteilt durch $13$ berechnen, mit dem Rechenweg des schnellen Potenzierens (auch Zahlen, die jeden Taschenrechner sprengen)
Den Rest auf einem Zifferblatt (dem Kreis modulo $n$) sehen und ein Gefühl dafür bekommen, wie Reste immer wieder dieselben Positionen durchlaufen (das Zifferblatt erscheint bei einem Modul $n$ von 2 bis 24)
Dazu eine leicht verständliche Erklärung der Formeln sowie Formeln zum Kopieren für Excel, Google Tabellen und Python

Der Modul $n$ ist eine ganze Zahl ab 1. Geben Sie $a$, $b$ und $n$ mit höchstens 30 Stellen ein und den Exponenten $k$ als ganze Zahl ab 0 mit höchstens 9 Stellen.

Wofür braucht man diese Berechnung?

Uhr und Kalender (welcher Wochentag ist in N Tagen?)

Dass 14 Uhr auf dem Zifferblatt bei der 2 steht, ist genau die Restrechnung 14 mod 12 = 2. Wochentage funktionieren genauso, nur mit einer „Uhr“, die nach 7 Tagen einmal herum ist. Ist heute zum Beispiel Montag, dann ist wegen 100 mod 7 = 2 der Tag in 100 Tagen „2 Tage nach Montag“, also ein Mittwoch.
Ob Taschenkalender oder Kalender-App: Datum und Wochentag werden mit dieser Restrechnung einander zugeordnet.

Prüfziffern entlarven falsche Nummern (Strichcode, ISBN, IBAN)

Die letzte Ziffer eines Strichcodes auf Waren (EAN) oder der ISBN eines Buches ist eine Prüfziffer, die aus den übrigen Ziffern mit einer Restrechnung gebildet wird. Beim EAN-Code werden die Ziffern abwechselnd mit 1 und 3 multipliziert und addiert; aus dem Rest dieser Summe beim Teilen durch 10 ergibt sich die letzte Ziffer.
Ist eine Ziffer vertippt, passt der Rest nicht mehr – Kasse und Onlineshop erkennen den Fehler sofort. Auch die zwei Prüfziffern direkt nach dem „DE“ Ihrer IBAN beruhen auf dieser Idee: Sie werden aus dem Rest beim Teilen durch 97 berechnet, sodass Banküberweisungen mit vertippter Kontonummer gar nicht erst losgehen.

Verschlüsselung, die das Internet schützt (RSA)

RSA, das bekannteste Public-Key-Verfahren zum sicheren Übertragen etwa von Kartennummern, rechnet direkt mit „dem Rest einer riesigen Potenz“. Eine Potenz modulo n lässt sich schnell berechnen, aber aus dem Ergebnis auf die Ausgangszahl zurückzurechnen, ist extrem schwer. Auf dieser Einbahnstraßen-Eigenschaft beruht die Sicherheit.
Das schnelle Potenzieren, dessen Rechenweg die Berechnung „Potenz modulo n“ auf dieser Seite zeigt, führt Verschlüsselungssoftware jeden Tag aus.

Programmier-Alltag (gerade oder ungerade, Reihenfolge im Kreis)

Beim Programmieren ist der %-Operator ständig im Einsatz: i % 2 unterscheidet gerade von ungeraden Zahlen, und i % n erzeugt eine Reihenfolge, die nach n Elementen von vorn beginnt (der nächste Spieler in einem rundenbasierten Spiel, nach der letzten Folie zurück zur ersten usw.).
Sind negative Zahlen im Spiel, liefert % je nach Sprache unterschiedliche Ergebnisse. Wer den Unterschied zwischen dem mathematischen Rest und % in C und Java kennt, findet solche Fehler schneller.

Gerecht verteilen und den Rest zählen (verteilen, verpacken)

Verteilt man 63 Bleistifte gleichmäßig an 12 Personen, bekommt jede 5, und 3 bleiben übrig (63 = 12 × 5 + 3). Ware in Kartons packen (wie viele volle Kartons zu n Stück und wie viele bleiben übrig), Gruppen für eine Feier einteilen: Jede Situation „gleichmäßig verteilen und schauen, was übrig bleibt“ ist diese Rechnung.
Die Grundgleichung der Division mit Rest a = n × q + r fasst all diese Alltagssituationen in einer Formel zusammen.

Formeln und Abbildungen

Die Grundgleichung der Division mit Rest (was ein Rest ist)

Zifferblatt (mod 12)

Mathematische Schreibweise (die übliche Formel)

$a$ $=$ $n$ $\times$ $q$ $+$ $r$

In Worten (Symbole durch Wörter ersetzt)

④ $a$: Dividend $=$ ① $n$: Divisor (Modul) $\times$ ② $q$: Quotient $+$ ③ $r$: Rest

Die Formel in Worten

① Man nimmt den $n$: Divisor (Modul)

② mal den $q$: Quotienten

③ plus den $r$: Rest (so gewählt, dass $0 \le r < n$)

④ und erhält wieder den $a$: Dividend . In dieser Form lässt sich $a$ auf genau eine Weise schreiben, und $r$ ist „der Rest von $a$ geteilt durch $n$“ ($a \bmod n$)

Einfaches Beispiel

38 geteilt durch 12 (dieselbe Rechnung, die auf einem Zifferblatt aus „38 Uhr“ die 2 macht)

Dividend 38 $=$ Divisor 12 $\times$ Quotient 3 $+$ Rest 2

$38 = 12 \times 3 + 2$

$38 \bmod 12 = 2$

Der Grundgedanke

In der Mathematik wählt man den Rest $r$ immer im Bereich $0 \le r < n$ – auch bei negativen Zahlen. Teilt man $-7$ durch $3$, schreibt man $-7 = 3 \times (-3) + 2$: Der Quotient wird zur kleineren ganzen Zahl ($-3$) abgerundet, damit der Rest $2$ ist (abrundende Division). Der %-Operator beim Programmieren verhält sich dagegen je nach Sprache unterschiedlich. In C, Java und JavaScript rundet -7 % 3 den Quotienten in Richtung 0 (auf $-2$), das Ergebnis ist also $-1$ (der Rest hat das Vorzeichen des Dividenden). Der %-Operator in Python und Ruby sowie die Excel-Funktion REST geben dem Rest das Vorzeichen des Divisors und liefern daher $2$, wie in der Mathematik. In Programmen, die mit Resten negativer Zahlen arbeiten, ist dieser Unterschied eine häufige Fehlerquelle.

Definition der Kongruenz (was a ≡ b (mod n) bedeutet)

Mathematische Schreibweise (die übliche Formel)

$a - b$ $=$ $n$ $\times$ $m$

In Worten (Symbole durch Wörter ersetzt)

③ $a - b$: Differenz der beiden Zahlen $=$ ① $n$: Modul $\times$ ② $m$: eine ganze Zahl

Die Formel in Worten

① Ist der $n$: Modul

② mal $m$: eine ganze Zahl

③ genau gleich der $a - b$: Differenz der beiden Zahlen (ist die Differenz also ein Vielfaches von $n$), schreibt man $a \equiv b \pmod{n}$ und sagt „$a$ ist kongruent zu $b$ modulo $n$“

Einfaches Beispiel

38 und 14 sind kongruent modulo 12 ($38 \equiv 14 \pmod{12}$)

Differenz (38 − 14 = 24) $=$ Modul 12 $\times$ ganze Zahl 2

$38 - 14 = 24 = 12 \times 2$

$38 \equiv 14 \pmod{12}$

Der Grundgedanke

„Die Differenz ist ein Vielfaches von $n$“ und „die Reste beim Teilen durch $n$ sind gleich“ sagen dasselbe auf zwei Arten (tatsächlich ist $38 \bmod 12 = 2$ und $14 \bmod 12 = 2$, die Reste stimmen überein). Deshalb kann man eine Kongruenz als „Gleichung, die nur auf die Reste schaut“ lesen. Stellen Sie sich ein Zifferblatt vor: „38 Uhr“, 14 Uhr und 2 Uhr zeigen alle auf dieselbe Stelle. Die Welt modulo $n$ ist ein Zifferblatt, das nach $n$ Schritten einmal herum ist, und kongruente Zahlen landen auf diesem Zifferblatt an derselben Stelle.

Multiplikation und Reste (die Grundlage für Potenzen modulo n)

Mathematische Schreibweise (die übliche Formel)

$(a \times b) \bmod n$ $=$ $\{(a \bmod n) \times (b \bmod n)\} \bmod n$

In Worten (Symbole durch Wörter ersetzt)

② Rest des Produkts $=$ ① Rest nach dem Multiplizieren der beiden Reste

Die Formel in Worten

① Der Rest nach dem Multiplizieren der beiden Reste

② ist gleich dem Rest des Produkts (man darf jede Zahl zuerst durch ihren Rest ersetzen und dann multiplizieren)

Einfaches Beispiel

Den Rest von 38 × 15 geteilt durch 12 erhält man allein aus den beiden Resten 2 und 3

Rest des Produkts (38 × 15 = 570) $=$ Rest 2 × Rest 3 = 6

$38 \bmod 12 = 2,\quad 15 \bmod 12 = 3$

$2 \times 3 = 6$

$(38 \times 15) \bmod 12 = 570 \bmod 12 = 6$

Der Grundgedanke

Dank dieser Eigenschaft müssen Sie eine große Multiplikation nie zu Ende rechnen: Sie dürfen die Zahlen zuerst durch ihre Reste ersetzen und diese multiplizieren. Eine Potenz ist wiederholte Multiplikation, also findet man den Rest von zum Beispiel $7^{100}$, indem man nur den Resten folgt – ohne die riesige Zahl je auszurechnen. Darauf beruht das schnelle Potenzieren (immer wieder quadrieren und dabei jeweils den Rest bilden, den Exponenten in eine Summe von Zweierpotenzen zerlegen und die Teile multiplizieren). Die Berechnung „Potenz modulo n“ dieses Rechners zeigt den Rechenweg genau so. Außerdem hat eine Potenz nur $n$ mögliche Reste. Sie muss also irgendwann zu einem früheren Rest zurückkehren und sich dann im Kreis wiederholen (Periodizität). Die letzte Ziffer von $7^{k}$ (ihr Rest modulo $10$) durchläuft zum Beispiel der Reihe nach 7, 9, 3, 1. Solche Zyklen zu finden, ist ein klassischer Trick bei Mathe-Wettbewerben wie der Mathematik-Olympiade.

Rechenregeln für Kongruenzen (beide Seiten addieren, subtrahieren, multiplizieren)

Mathematische Schreibweise (die übliche Formel)

$a + c$ $\equiv$ $b + d$ $\pmod{n}$

$a - c$ $\equiv$ $b - d$ $\pmod{n}$

$a \times c$ $\equiv$ $b \times d$ $\pmod{n}$

In Worten (Symbole durch Wörter ersetzt)

① $a + c$: Summe der linken Seiten $\equiv$ ② $b + d$: Summe der rechten Seiten $\pmod{n}$

$a - c$: Differenz der linken Seiten $\equiv$ $b - d$: Differenz der rechten Seiten $\pmod{n}$

$a \times c$: Produkt der linken Seiten $\equiv$ $b \times d$: Produkt der rechten Seiten $\pmod{n}$

Die Formel in Worten

① Gilt $a \equiv b$ und $c \equiv d \pmod{n}$, dann bleibt die Summe, Differenz oder das Produkt der linken Seiten

② kongruent zur Summe, Differenz oder zum Produkt der rechten Seiten (Kongruenzen lassen sich wie gewöhnliche Gleichungen addieren, subtrahieren und multiplizieren)

Einfaches Beispiel

Mit $38 \equiv 2$ und $15 \equiv 3 \pmod{12}$ gilt:

38 + 15 = 53 $\equiv$ 2 + 3 = 5 $\pmod{12}$

$38 + 15 = 53 \equiv 5,\quad 2 + 3 = 5 \pmod{12}$

$38 \times 15 = 570 \equiv 6,\quad 2 \times 3 = 6 \pmod{12}$

Der Grundgedanke

Praktisch an dieser Eigenschaft ist: Auch bei großen Zahlen dürfen Sie zuerst die Reste bilden und dann addieren, subtrahieren oder multiplizieren. Nur das Dividieren ist nicht ohne Weiteres erlaubt. Zum Beispiel stimmt $6 \equiv 12 \pmod{6}$, aber teilt man beide Seiten durch 2, erhält man $3 \equiv 6 \pmod{6}$, und das ist falsch (die Differenz 3 ist kein Vielfaches von 6). Beide Seiten darf man nur dann durch eine Zahl teilen, wenn diese Zahl und der Modul teilerfremd sind (ihr ggT also 1 ist).

Der Rest einer ganzen Zahl $a$ beim Teilen durch $n$ ist das $r$ in der einzigen Darstellung $a = n \times q + r$ mit $0 \le r < n$. Die Kongruenz $a \equiv b \pmod{n}$ bedeutet, dass die Differenz von $a$ und $b$ ein Vielfaches von $n$ ist (dass beide beim Teilen durch $n$ also denselben Rest lassen), und Kongruenzen lassen sich wie Gleichungen addieren, subtrahieren und multiplizieren. Deshalb findet man selbst den Rest einer riesigen Potenz schnell mit dem schnellen Potenzieren, das nur den Resten folgt.

Symbole und Begriffe

Symbole

$\equiv$	ist kongruent zu	Das Zeichen für Kongruenz. Es ist ein Gleichheitszeichen mit drei statt zwei Strichen und bedeutet „gleich in der Welt der Reste“ – schwächer als „genau gleich“.
$\bmod$ (mod)	modulo	Kurz für „modulo“, vom lateinischen modulus („kleines Maß“). „$a \bmod n$“ steht für „den Rest von $a$ geteilt durch $n$“, und „$\pmod{n}$“ hinter einer Gleichung legt fest: „Wir rechnen modulo $n$.“
$a,\ b$	a, b	Die ganzen Zahlen, deren Reste betrachtet werden. In einer Kongruenz sind es die beiden Zahlen links und rechts. Für feste Zahlen nimmt man traditionell Buchstaben vom Anfang des Alphabets.
$n$	n	Der Modul (die Zahl, durch die geteilt wird). Oft verwendet man $n$ wie „Zahl“ im Englischen („number“). Auf dieser Seite ist es eine ganze Zahl ab 1.
$q$	q	Der Quotient, nach dem Anfangsbuchstaben von „Quotient“. Beim Teilen einer negativen Zahl wird der Quotient zur kleineren ganzen Zahl abgerundet, damit der Rest mindestens 0 ist (abrundende Division).
$r$	r	Der Rest, nach dem Anfangsbuchstaben des englischen „remainder“ (Rest). In der Mathematik liegt er immer im Bereich $0 \le r < n$.
$m$	m	Die ganze Zahl in der Definition der Kongruenz, die angibt, das Wievielfache des Moduls die Differenz ist. Sie kann auch negativ oder 0 sein.
$a^{k}$	a hoch k	$a$ $k$-mal mit sich selbst multipliziert (eine Potenz). Die kleine hochgestellte Zahl $k$ ist der Exponent und gibt an, wie oft multipliziert wird.
%	Prozent (als Operator modulo)	Der Modulo-Operator, der in vielen Programmiersprachen den Rest berechnet. Es ist dasselbe Zeichen wie das Prozentzeichen, hat aber eine andere Aufgabe. In C, Java und JavaScript kann sein Ergebnis bei negativen Zahlen vom mathematischen Rest abweichen (siehe Grundgedanke der Formelkarte 1).

Begriffe

Rest	Was übrig bleibt, wenn eine Division nicht aufgeht. In der Mathematik ist er immer mindestens $0$ und kleiner als der Divisor.
Quotient	Die ganze Zahl, die angibt, wie oft der Divisor in den Dividenden passt. Sie ist das $q$ in der Grundgleichung $a = n \times q + r$.
Modul	Die Zahl $n$, durch die geteilt wird, um die Reste zu erhalten, mit denen man rechnet. Auf einem Zifferblatt ist es die Zahl der Markierungen in einer vollen Runde. „Modulo 12“ heißt kurz „Wir betrachten die Reste beim Teilen durch 12“.
kongruent	Zwei ganze Zahlen sind kongruent modulo $n$, wenn sie beim Teilen durch $n$ denselben Rest lassen. Der Begriff gehört zu den ganzen Zahlen und ist etwas anderes als kongruente Figuren in der Geometrie (gleiche Form und Größe).
Kongruenz	Eine Aussage der Form $a \equiv b \pmod{n}$. Kongruenzen lassen sich wie Gleichungen addieren, subtrahieren und multiplizieren, sodass man Restaufgaben durch Umformen löst. Sie sind ein Grundwerkzeug der Zahlentheorie und werden bei Mathe-Wettbewerben und in der Informatik verwendet.
Vielfaches	Eine Zahl, die man erhält, wenn man eine ganze Zahl mit einer anderen ganzen Zahl multipliziert. „Die Differenz ist ein Vielfaches des Moduls“ ist die Definition der Kongruenz.
abrundende Division (Floor-Division)	Eine Division, bei der der Quotient zur kleineren ganzen Zahl abgerundet wird. Ist der Divisor positiv, ist der Rest auch bei negativem Dividenden mindestens 0. So arbeiten der Operator // in Python und die Excel-Funktion GANZZAHL.
Modulo-Operator	Der Operator %, der beim Programmieren den Rest berechnet. C, Java und JavaScript runden den Quotienten in Richtung 0 (der Rest hat das Vorzeichen des Dividenden). Python und Ruby verwenden die abrundende Division (der Rest hat das Vorzeichen des Divisors und ist bei positivem Modul mindestens 0).
schnelles Potenzieren	Ein Verfahren, um den Rest einer riesigen Potenz mit wenigen Multiplikationen zu bestimmen: immer wieder quadrieren und dabei den Rest bilden, den Exponenten in eine Summe von Zweierpotenzen zerlegen und die Teile multiplizieren. Es heißt auch binäre Exponentiation oder Square-and-Multiply und steckt unter anderem in Umsetzungen der RSA-Verschlüsselung.
Restklasse	Die Idee, ganze Zahlen nach ihrem Rest beim Teilen durch $n$ zu gruppieren. In der Welt modulo $n$ gehört jede ganze Zahl zu genau einer von $n$ Gruppen, den Resten $0$ bis $n-1$. Gerade und ungerade Zahlen sind die Einteilung nach dem Rest beim Teilen durch 2.
Periodizität	Dass sich die Reste von Potenzen im gleichen Muster wiederholen. Weil es nur $n$ mögliche Reste gibt, muss irgendwann ein früherer Rest wiederkehren. Den Zyklus bei Aufgaben zur letzten Ziffer (modulo 10) zu finden, ist ein Klassiker bei Mathe-Wettbewerben.
teilerfremd	Zwei ganze Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler (ggT) 1 ist. Das ist die Bedingung dafür, beide Seiten einer Kongruenz durch dieselbe Zahl teilen zu dürfen.

Das sollten Sie vorher wissen

Damit Sie die Rechnung auf dieser Seite nicht nur per Knopfdruck, sondern mit echtem Verständnis nutzen, hilft Ihnen dieses Vorwissen.
Wenn Sie nicht weiterkommen, ist es am schnellsten, diese Themen noch einmal zu wiederholen.

Division mit Rest (Klasse 3–4, 8–10 Jahre)	Sie können Aufgaben wie $17 : 5 = 3$ Rest $2$ rechnen Sie können die Probe „Divisor × Quotient + Rest = Dividend“ machen
Vielfache und Teiler (Klasse 5–6, 10–12 Jahre)	Sie erkennen, dass $24$ ein Vielfaches von $12$ ist Sie wissen, was der ggT ist (er steckt in der Bedingung „teilerfremd“ für das Teilen einer Kongruenz)
Negative Zahlen (Klasse 6–7, 11–13 Jahre)	Sie können mit negativen Zahlen addieren, subtrahieren und multiplizieren (zum Beispiel $3 \cdot (-3) = -9$) Sie wissen, dass $-3$ auf dem Zahlenstrahl kleiner als $-2$ ist (links davon liegt)
Potenzen und Potenzgesetze (Klasse 5–10, 10–16 Jahre)	Sie wissen, dass der hochgestellte Exponent angibt, wie oft multipliziert wird, wie in $3^{4} = 3 \cdot 3 \cdot 3 \cdot 3 = 81$ Sie können die Potenzgesetze $a^{m} \cdot a^{n} = a^{m+n}$ und $(a^{m})^{n} = a^{mn}$ anwenden (sie begründen das schnelle Potenzieren)
Division mit Rest für ganze Zahlen (Oberstufe, Mathe-AG oder Studium, ab 16 Jahren)	Sie wissen, dass sich das Teilen einer ganzen Zahl $a$ durch eine positive ganze Zahl $n$ auf genau eine Weise als $a = nq + r$ (mit $0 \le r < n$) schreiben lässt Sie kennen die Idee, ganze Zahlen nach ihren Resten in Restklassen einzuteilen (gerade und ungerade Zahlen sind die Einteilung nach dem Rest beim Teilen durch 2)

So berechnen Sie es in Excel

Kopieren Sie die ganze Tabelle und fügen Sie sie in Zelle A1 von Excel ein – dann funktioniert sie direkt.

Tabelle für a mod n (den Rest)

Dividend a	-7
Modul (Divisor) n	3
Mathematischer Rest (ab 0)	=REST(B1;B2)
Quotient (abgerundet)	=GANZZAHL(B1/B2)
Probe n × Quotient + Rest	=B2*B4+B3
Rest wie in C/Java (Richtung 0 gerundet)	=B1-B2*KÜRZEN(B1/B2)

Tabelle zur Prüfung von a ≡ b (mod n)

Ganze Zahl a	38
Ganze Zahl b	14
Modul n	12
Differenz a − b	=B1-B2
Rest von Differenz : n	=REST(B4;B3)
Ergebnis (WAHR = kongruent)	=REST(B4;B3)=0

Tabelle für eine Potenz modulo n (schnelles Potenzieren)

Basis a	7
Exponent k	100
Modul n	13
Rest von a^1	=REST(B1;B3)
Rest von a^2 (Zeile darüber quadrieren, Rest bilden)	=REST(B4^2;$B$3)
Rest von a^4	=REST(B5^2;$B$3)
Rest von a^8	=REST(B6^2;$B$3)
Rest von a^16	=REST(B7^2;$B$3)
Rest von a^32	=REST(B8^2;$B$3)
Rest von a^64	=REST(B9^2;$B$3)
Rest zusammengesetzt für 100 = 64 + 32 + 4	=REST(REST(B10B9;$B$3)B6;$B$3)

Nach dem Einfügen ändern Sie nur die oberen Zeilen (die Eingaben); die unteren Zeilen werden automatisch berechnet.
Die Excel-Funktion REST liefert denselben „mathematischen Rest“ (ab 0) wie dieser Rechner – auch bei negativen Zahlen ist =REST(-7;3) gleich 2. Brauchen Sie den Rest wie in C/Java, nehmen Sie die letzte Zeile der ersten Tabelle, die den Quotienten mit KÜRZEN in Richtung 0 rundet.
Die erste Tabelle teilt −7 durch 3: Der Rest ist 2, der Quotient −3.
Die zweite Tabelle prüft 38 ≡ 14 (mod 12). Der Rest der Differenz 24 ist 0, also erscheint WAHR (kongruent).
Die dritte Tabelle berechnet den Rest von 7 hoch 100 geteilt durch 13 mit dem schnellen Potenzieren. Das Ergebnis ist 9. „^“ ist das Potenzzeichen. Excel rechnet nur auf etwa 15 Stellen genau; hat der Modul n mehr als 7 Stellen, werden die Quadrate ungenau. Nutzen Sie dann den Rechner auf dieser Seite oder Python.

So berechnen Sie es in Google Tabellen

Kopieren Sie die ganze Tabelle und fügen Sie sie in Zelle A1 von Google Tabellen ein – dann funktioniert sie direkt.

Tabelle für a mod n (den Rest)

Dividend a	-7
Modul (Divisor) n	3
Mathematischer Rest (ab 0)	=REST(B1;B2)
Quotient (abgerundet)	=GANZZAHL(B1/B2)
Probe n × Quotient + Rest	=B2*B4+B3
Rest wie in C/Java (Richtung 0 gerundet)	=B1-B2*KÜRZEN(B1/B2)

Tabelle zur Prüfung von a ≡ b (mod n)

Ganze Zahl a	38
Ganze Zahl b	14
Modul n	12
Differenz a − b	=B1-B2
Rest von Differenz : n	=REST(B4;B3)
Ergebnis (WAHR = kongruent)	=REST(B4;B3)=0

Tabelle für eine Potenz modulo n (schnelles Potenzieren)

Basis a	7
Exponent k	100
Modul n	13
Rest von a^1	=REST(B1;B3)
Rest von a^2 (Zeile darüber quadrieren, Rest bilden)	=REST(B4^2;$B$3)
Rest von a^4	=REST(B5^2;$B$3)
Rest von a^8	=REST(B6^2;$B$3)
Rest von a^16	=REST(B7^2;$B$3)
Rest von a^32	=REST(B8^2;$B$3)
Rest von a^64	=REST(B9^2;$B$3)
Rest zusammengesetzt für 100 = 64 + 32 + 4	=REST(REST(B10B9;$B$3)B6;$B$3)

Dieselben Formeln wie in Excel (REST, GANZZAHL, KÜRZEN) funktionieren unverändert. Kopieren Sie die ganze Tabelle, fügen Sie sie in Zelle A1 ein und ersetzen Sie die Eingaben durch Ihre eigenen Zahlen.

So berechnen Sie es in Python

a = -7
n = 3

# % in Python liefert denselben „mathematischen Rest“ wie dieser Rechner (ab 0 bei positivem Modul)
print(a % n)                 # 2

# divmod liefert den abgerundeten Quotienten und den Rest zusammen (a = n × Quotient + Rest)
quotient, remainder = divmod(a, n)
print(quotient, remainder)   # -3 2

# Kongruenz prüfen: Gilt 38 ≡ 14 (mod 12)? (Ist die Differenz ein Vielfaches von 12?)
print((38 - 14) % 12 == 0)   # True

# Potenz modulo n: Rest von 7 hoch 100 geteilt durch 13
# pow mit 3 Argumenten nutzt schnelles Potenzieren und ist auch bei riesigen Exponenten sofort fertig
print(pow(7, 100, 13))       # 9

def c_style_mod(x, m):
    # gleiches Ergebnis wie % in C, Java und JavaScript (Quotient in Richtung 0 gerundet)
    r = x % m
    if r != 0 and x < 0:
        r -= m
    return r

print(c_style_mod(-7, 3))    # -1

Der %-Operator in Python entspricht dem mathematischen Rest. Bei positivem Divisor liefert er auch für negative Zahlen einen Wert ab 0 (-7 % 3 ergibt 2). Für Potenzen modulo n führt die Form pow(Basis, Exponent, Modul) mit 3 Argumenten intern das schnelle Potenzieren aus und findet so nur den Rest – selbst bei Potenzen mit Zehntausenden Stellen in kürzester Zeit. Brauchen Sie dasselbe Ergebnis wie % in C, Java und JavaScript, ergänzen Sie wie in der letzten Funktion eine Korrektur, die den Quotienten in Richtung 0 rundet.

So schreiben Sie die Formel in LaTeX und anderen Formelsprachen (zum Kopieren)

Die Grundgleichung der Division mit Rest (was ein Rest ist)

a = n × q + r (0 ≤ r < n)

a = nq + r \quad (0 \le r < n)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><mo>=</mo><mi>n</mi><mi>q</mi><mo>+</mo><mi>r</mi>
    <mo>,</mo>
    <mn>0</mn><mo>&#x2264;</mo><mi>r</mi><mo>&lt;</mo><mi>n</mi>
  </mrow>
</math>

a = n q + r, \ 0 <= r < n

{Quotient[a, n], Mod[a, n]}

q := floor(a/n); r := a mod n;

q = floor(a/n); r = mod(a, n);

a = nq + r (0 ≤ r < n)

Definition der Kongruenz (was a ≡ b (mod n) bedeutet)

a ≡ b (mod n)  ⇔  a − b = n × m

a \equiv b \pmod{n} \iff a - b = nm

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><mo>&#x2261;</mo><mi>b</mi>
    <mspace width="0.3em"/>
    <mo>(</mo><mi>mod</mi><mspace width="0.3em"/><mi>n</mi><mo>)</mo>
    <mo>&#x21D4;</mo>
    <mi>a</mi><mo>&#x2212;</mo><mi>b</mi><mo>=</mo><mi>n</mi><mi>m</mi>
  </mrow>
</math>

a -= b (mod n) iff a - b = n m

Mod[a - b, n] == 0

(a - b) mod n = 0;

mod(a - b, n) == 0

a ≡ b (mod n)

Multiplikation und Reste (die Grundlage für Potenzen modulo n)

(a × b) mod n = {(a mod n) × (b mod n)} mod n

(a \times b) \bmod n = \{(a \bmod n)(b \bmod n)\} \bmod n

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mo>(</mo><mi>a</mi><mo>&#xD7;</mo><mi>b</mi><mo>)</mo>
    <mspace width="0.3em"/><mi>mod</mi><mspace width="0.3em"/><mi>n</mi>
    <mo>=</mo>
    <mo>{</mo>
    <mo>(</mo><mi>a</mi><mspace width="0.3em"/><mi>mod</mi><mspace width="0.3em"/><mi>n</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mo>(</mo><mi>b</mi><mspace width="0.3em"/><mi>mod</mi><mspace width="0.3em"/><mi>n</mi><mo>)</mo>
    <mo>}</mo>
    <mspace width="0.3em"/><mi>mod</mi><mspace width="0.3em"/><mi>n</mi>
  </mrow>
</math>

(a * b) mod n = ((a mod n) * (b mod n)) mod n

Mod[a b, n] == Mod[Mod[a, n] Mod[b, n], n]

(a * b) mod n = ((a mod n) * (b mod n)) mod n;

mod(a*b, n) == mod(mod(a, n)*mod(b, n), n)

(a×b) mod n = ((a mod n)×(b mod n)) mod n

Rechenregeln für Kongruenzen (beide Seiten addieren, subtrahieren, multiplizieren)

a ≡ b, c ≡ d (mod n) ⇒ a+c ≡ b+d, a−c ≡ b−d, a×c ≡ b×d (mod n)

a \equiv b,\ c \equiv d \pmod{n} \Rightarrow a + c \equiv b + d,\ a - c \equiv b - d,\ ac \equiv bd \pmod{n}

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>a</mi><mo>+</mo><mi>c</mi><mo>&#x2261;</mo><mi>b</mi><mo>+</mo><mi>d</mi>
    <mo>,</mo>
    <mi>a</mi><mo>&#x2212;</mo><mi>c</mi><mo>&#x2261;</mo><mi>b</mi><mo>&#x2212;</mo><mi>d</mi>
    <mo>,</mo>
    <mi>a</mi><mi>c</mi><mo>&#x2261;</mo><mi>b</mi><mi>d</mi>
    <mspace width="0.3em"/>
    <mo>(</mo><mi>mod</mi><mspace width="0.3em"/><mi>n</mi><mo>)</mo>
  </mrow>
</math>

a + c -= b + d, \ a - c -= b - d, \ a c -= b d (mod n)

Mod[a + c, n] == Mod[b + d, n] && Mod[a - c, n] == Mod[b - d, n] && Mod[a c, n] == Mod[b d, n]

(a + c) mod n = (b + d) mod n;

mod(a + c, n) == mod(b + d, n)

a + c ≡ b + d (mod n)

So lassen Sie ChatGPT rechnen

Sie sind ein Rechenassistent für Zahlentheorie (Eigenschaften ganzer Zahlen). Führen Sie die folgende Berechnung aus, indem Sie tatsächlich Python-Code ausführen, und stützen Sie Ihre Antwort nur auf die Zahlen aus dem Ausführungsergebnis (nicht im Kopf rechnen und nicht schätzen).

Berechnen Sie die folgenden 3 Aufgaben.
1. Den mathematischen Rest von −7 geteilt durch 3 (so gewählt, dass er mindestens 0 ist) und den Quotienten
2. Ob 38 ≡ 14 (mod 12) gilt (zeigen Sie auch, ob die Differenz ein Vielfaches von 12 ist)
3. Den Rest von 7 hoch 100 geteilt durch 13 (mit pow(7, 100, 13))

Verwenden Sie in Python %, divmod und pow(Basis, Exponent, Modul) und zeigen Sie die verwendeten Formeln und die Zahlen aus dem Ausführungsergebnis.

Anleitung

1

Werte eingeben

Tragen Sie die Zahlen, mit denen Sie rechnen möchten, in die Eingabefelder ein
2

Berechnen

Klicken Sie auf die Schaltfläche „Berechnen“
3

Ergebnis ansehen

Das Ergebnis erscheint sofort. Auf derselben Seite finden Sie auch den Rechenweg und die Erklärung der Formel

Die Vorteile von DataChef

Einfach und kostenlos

Kostenlose Umwandlung ohne Limit
Kein Fachwissen nötig – einfach und intuitiv

Keine Anmeldung erforderlich

Sofort nach dem Öffnen der Seite nutzbar
Keine persönlichen Daten erforderlich

Sicher und geschützt

Stark verschlüsselte Verbindung (SSL)
Die Datei wird nach dem Download automatisch gelöscht

Schnell

Schnelle Anzeige und Umwandlung – ganz ohne Wartezeit

Keine Wasserzeichen

Kein Wasserzeichen
Keine Quellenangabe nötig

Kommerzielle Nutzung möglich

Kostenlos auch für die kommerzielle Nutzung
Keine vorherige Genehmigung erforderlich

\(\equiv\)	ist kongruent zu	Das Zeichen für Kongruenz. Es ist ein Gleichheitszeichen mit drei statt zwei Strichen und bedeutet „gleich in der Welt der Reste“ – schwächer als „genau gleich“.
\(\bmod\) (mod)	modulo	Kurz für „modulo“, vom lateinischen modulus („kleines Maß“). „\(a \bmod n\)“ steht für „den Rest von \(a\) geteilt durch \(n\)“, und „\(\pmod{n}\)“ hinter einer Gleichung legt fest: „Wir rechnen modulo \(n\).“
\(a,\ b\)	a, b	Die ganzen Zahlen, deren Reste betrachtet werden. In einer Kongruenz sind es die beiden Zahlen links und rechts. Für feste Zahlen nimmt man traditionell Buchstaben vom Anfang des Alphabets.
\(n\)	n	Der Modul (die Zahl, durch die geteilt wird). Oft verwendet man \(n\) wie „Zahl“ im Englischen („number“). Auf dieser Seite ist es eine ganze Zahl ab 1.
\(q\)	q	Der Quotient, nach dem Anfangsbuchstaben von „Quotient“. Beim Teilen einer negativen Zahl wird der Quotient zur kleineren ganzen Zahl abgerundet, damit der Rest mindestens 0 ist (abrundende Division).
\(r\)	r	Der Rest, nach dem Anfangsbuchstaben des englischen „remainder“ (Rest). In der Mathematik liegt er immer im Bereich \(0 \le r < n\).
\(m\)	m	Die ganze Zahl in der Definition der Kongruenz, die angibt, das Wievielfache des Moduls die Differenz ist. Sie kann auch negativ oder 0 sein.
\(a^{k}\)	a hoch k	\(a\) \(k\)-mal mit sich selbst multipliziert (eine Potenz). Die kleine hochgestellte Zahl \(k\) ist der Exponent und gibt an, wie oft multipliziert wird.
%	Prozent (als Operator modulo)	Der Modulo-Operator, der in vielen Programmiersprachen den Rest berechnet. Es ist dasselbe Zeichen wie das Prozentzeichen, hat aber eine andere Aufgabe. In C, Java und JavaScript kann sein Ergebnis bei negativen Zahlen vom mathematischen Rest abweichen (siehe Grundgedanke der Formelkarte 1).

Division mit Rest (Klasse 3–4, 8–10 Jahre)	Sie können Aufgaben wie \(17 : 5 = 3\) Rest \(2\) rechnen Sie können die Probe „Divisor × Quotient + Rest = Dividend“ machen
Vielfache und Teiler (Klasse 5–6, 10–12 Jahre)	Sie erkennen, dass \(24\) ein Vielfaches von \(12\) ist Sie wissen, was der ggT ist (er steckt in der Bedingung „teilerfremd“ für das Teilen einer Kongruenz)
Negative Zahlen (Klasse 6–7, 11–13 Jahre)	Sie können mit negativen Zahlen addieren, subtrahieren und multiplizieren (zum Beispiel \(3 \cdot (-3) = -9\)) Sie wissen, dass \(-3\) auf dem Zahlenstrahl kleiner als \(-2\) ist (links davon liegt)
Potenzen und Potenzgesetze (Klasse 5–10, 10–16 Jahre)	Sie wissen, dass der hochgestellte Exponent angibt, wie oft multipliziert wird, wie in \(3^{4} = 3 \cdot 3 \cdot 3 \cdot 3 = 81\) Sie können die Potenzgesetze \(a^{m} \cdot a^{n} = a^{m+n}\) und \((a^{m})^{n} = a^{mn}\) anwenden (sie begründen das schnelle Potenzieren)
Division mit Rest für ganze Zahlen (Oberstufe, Mathe-AG oder Studium, ab 16 Jahren)	Sie wissen, dass sich das Teilen einer ganzen Zahl \(a\) durch eine positive ganze Zahl \(n\) auf genau eine Weise als \(a = nq + r\) (mit \(0 \le r < n\)) schreiben lässt Sie kennen die Idee, ganze Zahlen nach ihren Resten in Restklassen einzuteilen (gerade und ungerade Zahlen sind die Einteilung nach dem Rest beim Teilen durch 2)

Modulo-Rechner – Rest berechnen (a mod n), Kongruenz prüfen, Potenz modulo n

Inhaltsverzeichnis

Das können Sie auf dieser Seite

Wofür braucht man diese Berechnung?

Formeln und Abbildungen

Symbole und Begriffe

Symbole

Begriffe

Das sollten Sie vorher wissen

So berechnen Sie es in Excel

So berechnen Sie es in Google Tabellen

So berechnen Sie es in Python

So schreiben Sie die Formel in LaTeX und anderen Formelsprachen (zum Kopieren)

So lassen Sie ChatGPT rechnen

Anleitung

Die Vorteile von DataChef

Verwandte Funktionen

Lineare diophantische Gleichung ax + by = c lösen – ganzzahlige Lösungen mit euklidischem Algorithmus

Bestimmt die ganzzahligen Lösungen von ax + by = c mit euklidischem Algorithmus, allgemeiner Lösung und nur positiven Lösungen

ggT berechnen – größter gemeinsamer Teiler (ggT-Rechner)

Berechnet den ggT von zwei oder mehr ganzen Zahlen, erklärt mit Primfaktorzerlegung und euklidischem Algorithmus

Schriftliche Division – Rechner mit Rest und Rechenweg

Teilt ganze Zahlen und Dezimalzahlen schriftlich und erklärt jeden Schritt (teilen, malnehmen, abziehen, herunterholen)

Empfohlen

Wahrscheinlichkeit und Zufallszahlen

Mittelwerte und Statistik

Prozent und Verhältnis

Geschwindigkeit

Dichte und Konzentration

Physik und Elektrizität

Einheitenumrechnung

Ganze Zahlen und Vorzeichen

Brüche, Dezimalzahlen und Runden

Gleichungen und Ungleichungen

Polynome

Quadratwurzeln und n-te Wurzeln

Potenzen und Logarithmen

Komplexe Zahlen

Funktionen und Graphen

Folgen

Vektoren

Matrizen

Ebene Geometrie

Raumgeometrie

Datum und Uhrzeit

Finanzen und Wirtschaft

Online-Marketing und Werbekennzahlen

Gesundheit und Fitness

Sport

Wetter

Informatik

Haushaltsenergie und Budget

Auto

Solarstrom und Batteriespeicher

Haus und Heimwerken