Modulo-Rechner (a mod n, Kongruenz und Potenz mod n)

Wählen Sie eine Betriebsart und geben Sie ganze Zahlen ein. „Rest“ funktioniert auch mit negativen Zahlen und zeigt, wie sich der mathematische Rest (0 oder mehr) vom %-Operator in der Programmierung unterscheidet.

Was soll berechnet werden?

Ganze Zahl a

Ganze Zahl b (zum Vergleich)

Exponent k (Hochzahl)

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 höchstens 9 Stellen, und der Modul n ist mindestens 1.

Ergebnis und Figur

Wählen Sie links eine Betriebsart, geben Sie ganze Zahlen ein und klicken Sie auf „Berechnen“. Das Ergebnis erscheint hier (ist der Modul n zwischen 2 und 24, zeigt außerdem ein Zifferblatt-Diagramm, wo der Rest landet).

Inhaltsverzeichnis

[ Schließen X ]

Was Sie auf dieser Seite tun können
Wofür ist diese Berechnung nützlich?
Anleitung
Formeln und Abbildungen
Symbole und Begriffe
- Symbole
- Begriffe
Was Sie vorab wissen sollten
Mit Excel berechnen
Mit Google Tabellen berechnen
Mit Python berechnen
Die Formel in LaTeX und anderen mathematischen Schreibweisen (zum Kopieren)
Die Berechnung von ChatGPT ausführen lassen
Die Vorteile von DataChef
Verwandte Funktionen
Alle NumberChef-Rechner

Was Sie auf dieser Seite tun können

Berechnen Sie den Rest, wenn eine ganze Zahl $a$ durch $n$ geteilt wird. 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 Sie, ob die Kongruenz $a \equiv b \pmod{n}$ gilt, mit der Begründung, ob die Differenz $a - b$ ein Vielfaches von $n$ ist
Bestimmen Sie den exakten Rest einer riesigen Potenz, etwa $7^{100}$ geteilt durch $13$, mit den Schritten des wiederholten Quadrierens (Zahlen, die für einen normalen Taschenrechner zu groß sind, sind kein Problem)
Sehen Sie den Rest auf einem Zifferblatt-Diagramm (dem Kreis von mod $n$) und bekommen Sie ein Gefühl dafür, wie die Reste immer wieder um dieselben Stellen laufen (das Zifferblatt erscheint, wenn der Modul $n$ zwischen 2 und 24 liegt)
Eine leicht verständliche Erklärung der Formeln sowie Formeln zum Kopieren für Excel, Google Tabellen und Python finden Sie ebenfalls auf dieser Seite

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 ist diese Berechnung nützlich?

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

Auf einer Uhr ist „14 Uhr gleich 2 Uhr auf dem Zifferblatt“ genau die Rest-Rechnung 14 mod 12 = 2. Bei den Wochentagen ist es genauso, mit einer Uhr, die alle 7 Tage einmal herumgeht. Ist heute zum Beispiel Montag, dann ist wegen 100 mod 7 = 2 der Tag in 100 Tagen „2 Tage nach Montag“, also Mittwoch.
Papierkalender und Kalender-Apps ordnen Daten den Wochentagen mit dieser Rest-Rechnung zu.

Prüfziffern, die falsche Nummern entlarven (Barcode, ISBN und IBAN)

Die letzte Ziffer eines Produkt-Barcodes (EAN-13) oder der ISBN-13 eines Buchs ist eine Prüfziffer, die aus den übrigen Ziffern mit einer Rest-Rechnung gebildet wird. Beim EAN-13 zum Beispiel werden die Ziffern abwechselnd mit 1 und 3 multipliziert und addiert, und die letzte Ziffer ergänzt die Summe auf das nächste Vielfache von 10, sie hängt also vom Rest der Summe geteilt durch 10 ab.
Vertippt man sich in einer Ziffer, passt der Rest nicht mehr, und Kassen und Online-Shops können den Fehler sofort erkennen. Auch die Prüfziffern der IBAN (Rest bei der Division durch 97) und der Kreditkartennummern beruhen auf demselben Gedanken.

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

RSA, die bekannteste Public-Key-Verschlüsselung, um zum Beispiel Kreditkartennummern sicher zu übertragen, benutzt „den Rest einer riesigen Potenz“ direkt in ihren Berechnungen. Eine Potenz mod n lässt sich schnell berechnen, aber vom Ergebnis auf die ursprüngliche Zahl zurückzurechnen ist extrem schwer. Diese Einwegeigenschaft macht sie sicher.
Das wiederholte Quadrieren, dessen Schritte die Betriebsart „Potenz mod n“ auf dieser Seite zeigt, ist die Rechnung, die Verschlüsselungssoftware jeden Tag ausführt.

Alltag beim Programmieren (gerade oder ungerade, der Reihe nach im Kreis)

Beim Programmieren wird der %-Operator ständig gebraucht: i % 2 unterscheidet gerade von ungerade, und i % n bildet eine Reihenfolge, die alle n Elemente von vorn beginnt (den nächsten Spieler in einem rundenbasierten Spiel wählen, nach der letzten Folie wieder zur ersten springen und so weiter).
Kommen negative Zahlen ins Spiel, liefert % in verschiedenen Sprachen verschiedene Ergebnisse. Der Unterschied „mathematischer Rest gegenüber % in C und Java“ hilft deshalb bei der Fehlersuche.

Gleichmäßig verteilen und zählen, was übrig bleibt (austeilen, verpacken)

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

Formeln und Abbildungen

Die Grundgleichung der Division (was ein Rest ist)

Zifferblatt-Diagramm (mod 12)

Mathematische Schreibweise (die übliche Schreibweise)

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

In Worten (die Symbole durch Wörter ersetzt)

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

Die Formel in Worten

① Nehmen Sie den $n$: Divisor (Modul)

② multiplizieren Sie ihn mit dem $q$: Quotient

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

④ so erhalten Sie den $a$: Dividend . Es gibt genau eine Möglichkeit, ihn in dieser Form zu schreiben, und $r$ ist „der Rest von $a$ geteilt durch $n$“ ($a \bmod n$)

Einfaches Beispiel

Teilt man 38 durch 12 (dieselbe Rechnung, die auf einer Uhr aus „38 Uhr“ 2 Uhr macht), erhält man

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

$38 = 12 \times 3 + 2$

$38 \bmod 12 = 2$

Der Kerngedanke

In der Mathematik wählt man den Rest $r$ immer im Bereich $0 \le r < n$. Das gilt auch für negative Zahlen. Um $-7$ durch $3$ zu teilen, schreibt man $-7 = 3 \times (-3) + 2$: Der Quotient wird auf die kleinere ganze Zahl ($-3$) abgerundet, damit der Rest $2$ ist (Floor-Division). Der %-Operator in der Programmierung verhält sich dagegen je nach Sprache unterschiedlich. In C, Java und JavaScript rundet -7 % 3 den Quotienten zur 0 hin (auf $-2$), das Ergebnis ist also $-1$ (der Rest übernimmt das Vorzeichen des Dividenden). Der %-Operator in Python und Ruby und die Excel-Funktion REST geben dem Rest das Vorzeichen des Divisors und liefern deshalb $2$, wie in der Mathematik. In Programmen, die mit Resten negativer Zahlen umgehen, ist dieser Unterschied eine häufige Fehlerquelle, seien Sie also vorsichtig.

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

Mathematische Schreibweise (die übliche Schreibweise)

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

In Worten (die Symbole durch Wörter ersetzt)

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

Die Formel in Worten

① Wenn der $n$: Modul

② mal $m$: eine ganze Zahl

③ genau gleich der $a - b$: Differenz der beiden ganzen Zahlen ist (das heißt, wenn die Differenz ein Vielfaches von $n$ ist), schreibt man $a \equiv b \pmod{n}$ und sagt „$a$ und $b$ sind kongruent modulo $n$“

Einfaches Beispiel

38 und 14 sind modulo 12 kongruent ($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 Kerngedanke

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

Multiplikation und Reste (die Grundlage der Potenz mod n)

Mathematische Schreibweise (die übliche Schreibweise)

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

In Worten (die 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 derselbe wie der Rest des Produkts (man darf zuerst jede Zahl 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 Kerngedanke

Dank dieser Eigenschaft müssen Sie eine große Multiplikation nie zu Ende rechnen: Sie können die Zahlen zuerst durch ihre Reste ersetzen und diese multiplizieren. Eine Potenz ist eine wiederholte Multiplikation, den Rest von etwas wie $7^{100}$ findet man also, indem man nur den Resten folgt, ohne je die riesige Zahl zu bilden. Das ist die Grundlage des wiederholten Quadrierens (immer wieder quadrieren und jedes Mal den Rest bilden, den Exponenten in eine Summe von Zweierpotenzen zerlegen und die Teile multiplizieren). Die Betriebsart „Potenz mod n“ dieses Rechners zeigt ihre Schritte auf diese Weise. Außerdem hat eine Potenz nur $n$ mögliche Reste, sie muss also irgendwann zu einem Rest zurückkehren, den sie schon hatte, und wiederholt sich dann in einem Zyklus. Zum Beispiel durchläuft die letzte Ziffer von $7^{k}$ (ihr Rest mod $10$) der Reihe nach 7, 9, 3, 1. Einen solchen Zyklus zu finden, ist eine klassische Technik bei Mathematikwettbewerben.

Eigenschaften von Kongruenzen (beide Seiten addieren, subtrahieren und multiplizieren)

Mathematische Schreibweise (die übliche Schreibweise)

$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 (die 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 ist die Summe, Differenz oder das Produkt der linken Seiten

② kongruent zur Summe, Differenz oder dem Produkt der rechten Seiten (man kann Kongruenzen 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 Kerngedanke

Praktisch an dieser Eigenschaft ist, dass Sie auch bei großen Zahlen zuerst die Reste bilden und dann addieren, subtrahieren oder multiplizieren können. Nur die Division ist nicht frei möglich. Zum Beispiel ist $6 \equiv 12 \pmod{6}$ wahr, 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 größter gemeinsamer Teiler ist 1).

Der Rest einer ganzen Zahl $a$ geteilt durch $n$ ist das $r$ in der einzigen Möglichkeit, $a = n \times q + r$ mit $0 \le r < n$ zu schreiben. Die Kongruenz $a \equiv b \pmod{n}$ besagt, dass die Differenz von $a$ und $b$ ein Vielfaches von $n$ ist (anders gesagt, dass beide bei der Division durch $n$ denselben Rest haben), und man kann Kongruenzen wie Gleichungen addieren, subtrahieren und multiplizieren. Deshalb lässt sich sogar der Rest einer riesigen Potenz schnell durch wiederholtes Quadrieren finden, das nur den Resten folgt.

Symbole und Begriffe

Symbole

$\equiv$	ist kongruent zu	Das Zeichen für die Kongruenz. Es ist ein Gleichheitszeichen mit drei statt zwei Strichen und sagt „gleich in der Welt der Reste“, was lockerer ist als „genau gleich“.
$\bmod$ (mod)	mod	Kurzform für „Modul“, vom lateinischen Wort „modulus“ (kleines Maß). „$a \bmod n$“ steht für „der Rest von $a$ geteilt durch $n$“, und ein „$\pmod{n}$“ hinter einer Gleichung erklärt: „Wir rechnen modulo $n$“.
$a,\ b$	a, b	Die ganzen Zahlen, deren Reste man betrachtet. In einer Kongruenz sind es die beiden ganzen Zahlen links und rechts. Für feste Zahlen nimmt man traditionell Buchstaben vom Anfang des Alphabets.
$n$	n	Der Modul (die Zahl, durch die man teilt). Oft nimmt man den Buchstaben $n$, vom lateinischen „numerus“ (Zahl). Auf dieser Seite ist er eine ganze Zahl ab 1.
$q$	q	Der Quotient, vom Anfangsbuchstaben von „Quotient“. Bei der Division einer negativen Zahl wird der Quotient auf die kleinere ganze Zahl abgerundet, damit der Rest mindestens 0 ist (Floor-Division).
$r$	r	Der Rest, vom Anfangsbuchstaben von „Rest“. In der Mathematik wählt man ihn immer im Bereich $0 \le r < n$.
$m$	m	Die ganze Zahl in der Definition der Kongruenz, die angibt, wie oft der Modul in der Differenz enthalten ist. Sie kann negativ oder 0 sein.
$a^{k}$	a hoch k	$a$, $k$-mal mit sich selbst multipliziert (eine Potenz). Die kleine Zahl $k$ rechts oben ist der Exponent, der angibt, wie oft multipliziert wird.
%	Prozentzeichen (als Operator: mod)	Der Modulo-Operator, der in vielen Programmiersprachen einen Rest berechnet. Er sieht aus wie das Prozentzeichen, hat aber eine andere Aufgabe. In C, Java und JavaScript kann sein Ergebnis für negative Zahlen vom mathematischen Rest abweichen (siehe den Kerngedanken der Formelkarte 1).

Begriffe

Rest (Divisionsrest)	Das, 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 man den Divisor abziehen kann. Es ist das $q$ in der Grundgleichung der Division $a = n \times q + r$.
Modul	Die Zahl $n$, durch die man teilt, um die Reste zu erhalten, mit denen man rechnet. Auf einem Zifferblatt ist es die Zahl der Striche einer ganzen Runde. „Modulo 12“ ist die Kurzform für „die Reste bei der Division durch 12 betrachten“.
kongruent	Zwei ganze Zahlen sind modulo $n$ kongruent, wenn sie bei der Division durch $n$ denselben Rest haben. Das ist ein Begriff für ganze Zahlen und etwas anderes als kongruente Figuren in der Geometrie (gleiche Form und Größe).
Kongruenz	Eine Aussage der Form $a \equiv b \pmod{n}$. Man kann Kongruenzen wie Gleichungen addieren, subtrahieren und multiplizieren, deshalb lassen sich Rest-Aufgaben durch Umformen lösen. Sie ist ein Grundwerkzeug der Zahlentheorie, das bei Mathematikwettbewerben und in der Informatik gebraucht wird.
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.
Floor-Division (abrundende Division)	Eine Art zu dividieren, bei der der Quotient auf die kleinere ganze Zahl abgerundet wird. Ist der Divisor positiv, ist der Rest auch bei negativem Dividenden mindestens 0. Der //-Operator in Python und die Excel-Funktion GANZZAHL arbeiten so.
Modulo-Operator	Der %-Operator, der in der Programmierung einen Rest berechnet. C, Java und JavaScript runden den Quotienten zur 0 hin (der Rest übernimmt das Vorzeichen des Dividenden). Python und Ruby verwenden die Floor-Division (der Rest übernimmt das Vorzeichen des Divisors, ist also mindestens 0, wenn der Modul positiv ist).
wiederholtes Quadrieren (schnelle Exponentiation)	Ein Verfahren, den Rest einer riesigen Potenz mit wenigen Multiplikationen zu finden: immer wieder quadrieren und dabei den Rest bilden, den Exponenten in eine Summe von Zweierpotenzen zerlegen und die Teile multiplizieren. Man nennt es auch Square-and-Multiply, und es steckt unter anderem in Implementierungen der RSA-Verschlüsselung.
Restklasse	Der Gedanke, ganze Zahlen nach ihrem Rest bei der Division durch $n$ in Gruppen einzuteilen. In der Welt von mod $n$ fällt jede ganze Zahl in eine von $n$ Gruppen, den Resten $0$ bis $n-1$. Gerade und ungerade Zahlen sind die Einteilung nach dem Rest bei der Division durch 2.
Periodizität	Die Eigenschaft, dass sich die Reste von Potenzen im selben Muster wiederholen. Es gibt nur $n$ mögliche Reste, sie müssen also irgendwann zu einem schon dagewesenen zurückkehren. Den Zyklus bei Aufgaben zur letzten Ziffer (mod 10) zu finden, ist ein Klassiker bei Mathematikwettbewerben.
teilerfremd	Zwei ganze Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler 1 ist. Das kommt in der Bedingung vor, unter der man beide Seiten einer Kongruenz durch dieselbe Zahl teilen darf.

Was Sie vorab wissen sollten

Hier steht, was Ihnen hilft, die Berechnung auf dieser Seite mit echtem Verständnis zu nutzen und nicht nur auf die Schaltfläche zu klicken.
Wenn Sie nicht weiterkommen, ist es der schnellste Weg, diese Themen noch einmal durchzugehen.

Division mit Rest (Klasse 3 bis 4, 8–10 Jahre)	$17 : 5 = 3$ Rest $2$ rechnen können Mit „Divisor × Quotient + Rest = Dividend“ die Probe machen können
Vielfache und Teiler (Klasse 5 bis 6, 10–12 Jahre)	Wissen, dass $24$ ein Vielfaches von $12$ ist Wissen, was der größte gemeinsame Teiler ist (er wird in der Bedingung „teilerfremd“ für das Teilen einer Kongruenz gebraucht)
Negative Zahlen (Klasse 6 bis 7, 11–13 Jahre)	Mit negativen Zahlen addieren, subtrahieren und multiplizieren können (zum Beispiel $3 \times (-3) = -9$) Wissen, dass $-3$ auf dem Zahlenstrahl kleiner als $-2$ ist (links davon liegt)
Potenzen (Klasse 6 bis 8, 11–14 Jahre)	Wissen, dass der Exponent rechts oben angibt, wie oft multipliziert wird, wie in $3^{4} = 3 \times 3 \times 3 \times 3 = 81$ Die Potenzgesetze $a^{m} \times a^{n} = a^{m+n}$ und $(a^{m})^{n} = a^{mn}$ anwenden können (sie sind der Grund dafür, dass das wiederholte Quadrieren funktioniert)
Die Division mit Rest bei ganzen Zahlen (Oberstufe, 16–19 Jahre)	Wissen, dass sich die Division 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 Den Gedanken kennen, ganze Zahlen nach ihrem Rest einzuteilen (gerade und ungerade Zahlen sind die Einteilung nach dem Rest bei der Division durch 2)

Mit Excel berechnen

Kopieren Sie die gesamte Tabelle unten und fügen Sie sie in Zelle A1 von Excel ein. Sie funktioniert unverändert.

Tabelle zur Berechnung von a mod n (dem Rest)

Dividend a	-7
Modul (Divisor) n	3
Mathematischer Rest (0 oder mehr)	=REST(B1;B2)
Quotient (Floor-Division)	=GANZZAHL(B1/B2)
Probe n × Quotient + Rest	=B2*B4+B3
Rest im C/Java-Stil (zur 0 hin 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 der Differenz : n	=REST(B4;B3)
Ergebnis (WAHR = kongruent)	=REST(B4;B3)=0

Tabelle zur Berechnung einer Potenz mod n (wiederholtes Quadrieren)

Basis a	7
Exponent k	100
Modul n	13
Rest von a^1	=REST(B1;B3)
Rest von a^2 (die Zeile darüber quadrieren, den 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), und die unteren Zeilen werden automatisch berechnet.
Die Excel-Funktion REST liefert denselben „mathematischen Rest“ (0 oder mehr) wie dieser Rechner. Auch für negative Zahlen ist =REST(-7;3) gleich 2. Brauchen Sie den Rest im C/Java-Stil, nehmen Sie die letzte Zeile der ersten Tabelle, die mit KÜRZEN den Quotienten zur 0 hin rundet.
Die erste Tabelle teilt −7 durch 3: Der Rest ist 2 und der Quotient −3.
Die zweite Tabelle prüft 38 ≡ 14 (mod 12). Der Rest der Differenz 24 ist 0, deshalb erscheint WAHR (kongruent).
Die dritte Tabelle bestimmt den Rest von 7 hoch 100 geteilt durch 13 durch wiederholtes Quadrieren. Das Ergebnis ist 9. „^“ ist das Zeichen für die Potenz. Excel rechnet nur mit etwa 15 Stellen exakt. Hat der Modul n mehr als 7 Stellen, verlieren die Quadrate deshalb an Genauigkeit. Nutzen Sie dann den Rechner auf dieser Seite oder Python.

Mit Google Tabellen berechnen

Kopieren Sie die gesamte Tabelle unten und fügen Sie sie in Zelle A1 von Google Tabellen ein. Sie funktioniert unverändert.

Tabelle zur Berechnung von a mod n (dem Rest)

Dividend a	-7
Modul (Divisor) n	3
Mathematischer Rest (0 oder mehr)	=REST(B1;B2)
Quotient (Floor-Division)	=GANZZAHL(B1/B2)
Probe n × Quotient + Rest	=B2*B4+B3
Rest im C/Java-Stil (zur 0 hin 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 der Differenz : n	=REST(B4;B3)
Ergebnis (WAHR = kongruent)	=REST(B4;B3)=0

Tabelle zur Berechnung einer Potenz mod n (wiederholtes Quadrieren)

Basis a	7
Exponent k	100
Modul n	13
Rest von a^1	=REST(B1;B3)
Rest von a^2 (die Zeile darüber quadrieren, den 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, wenn Google Tabellen auf Deutsch eingestellt ist. Kopieren Sie die gesamte Tabelle, fügen Sie sie in Zelle A1 ein und ersetzen Sie die Eingaben durch Ihre eigenen Zahlen.

Mit Python berechnen

a = -7
n = 3

# Pythons % liefert denselben „mathematischen Rest“ wie dieser Rechner (0 oder mehr, wenn der Modul positiv ist)
print(a % n)                 # 2

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

# Kongruenzprüfung: gilt 38 ≡ 14 (mod 12)? (prüfen, ob die Differenz ein Vielfaches von 12 ist)
print((38 - 14) % 12 == 0)   # True

# Potenz mod n: Rest von 7 hoch 100 geteilt durch 13
# das pow mit 3 Argumenten nutzt wiederholtes Quadrieren, ist also selbst bei riesigen Exponenten sofort fertig
print(pow(7, 100, 13))       # 9

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

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

Der %-Operator von Python entspricht dem mathematischen Rest. Ist der Divisor positiv, liefert er auch bei negativen Zahlen einen Wert ab 0 (-7 % 3 ist 2). Für die Potenz mod n führt die Form mit 3 Argumenten pow(Basis, Exponent, Modul) im Innern das wiederholte Quadrieren aus und findet deshalb selbst bei Potenzen mit Zehntausenden von Stellen schnell nur den Rest. Brauchen Sie dasselbe Ergebnis wie das % in C, Java und JavaScript, ergänzen Sie eine Korrektur, die den Quotienten zur 0 hin rundet, wie in der letzten Funktion.

Die Formel in LaTeX und anderen mathematischen Schreibweisen (zum Kopieren)

Die Grundgleichung der Division (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 der Potenz mod 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

Eigenschaften von Kongruenzen (beide Seiten addieren, subtrahieren und 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)

Die Berechnung von ChatGPT ausführen lassen

Sie sind ein Rechenassistent für Mathematik (Eigenschaften ganzer Zahlen, Zahlentheorie). 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 Ergebnis der Ausführung (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 (verwenden Sie 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 Ergebnis der Ausführung.

Anleitung

1

Zahlen eingeben

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

Berechnen

Klicken Sie auf die Schaltfläche „Berechnen“
3

Ergebnis ablesen

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 die Kongruenz. Es ist ein Gleichheitszeichen mit drei statt zwei Strichen und sagt „gleich in der Welt der Reste“, was lockerer ist als „genau gleich“.
\(\bmod\) (mod)	mod	Kurzform für „Modul“, vom lateinischen Wort „modulus“ (kleines Maß). „\(a \bmod n\)“ steht für „der Rest von \(a\) geteilt durch \(n\)“, und ein „\(\pmod{n}\)“ hinter einer Gleichung erklärt: „Wir rechnen modulo \(n\)“.
\(a,\ b\)	a, b	Die ganzen Zahlen, deren Reste man betrachtet. In einer Kongruenz sind es die beiden ganzen Zahlen links und rechts. Für feste Zahlen nimmt man traditionell Buchstaben vom Anfang des Alphabets.
\(n\)	n	Der Modul (die Zahl, durch die man teilt). Oft nimmt man den Buchstaben \(n\), vom lateinischen „numerus“ (Zahl). Auf dieser Seite ist er eine ganze Zahl ab 1.
\(q\)	q	Der Quotient, vom Anfangsbuchstaben von „Quotient“. Bei der Division einer negativen Zahl wird der Quotient auf die kleinere ganze Zahl abgerundet, damit der Rest mindestens 0 ist (Floor-Division).
\(r\)	r	Der Rest, vom Anfangsbuchstaben von „Rest“. In der Mathematik wählt man ihn immer im Bereich \(0 \le r < n\).
\(m\)	m	Die ganze Zahl in der Definition der Kongruenz, die angibt, wie oft der Modul in der Differenz enthalten ist. Sie kann negativ oder 0 sein.
\(a^{k}\)	a hoch k	\(a\), \(k\)-mal mit sich selbst multipliziert (eine Potenz). Die kleine Zahl \(k\) rechts oben ist der Exponent, der angibt, wie oft multipliziert wird.
%	Prozentzeichen (als Operator: mod)	Der Modulo-Operator, der in vielen Programmiersprachen einen Rest berechnet. Er sieht aus wie das Prozentzeichen, hat aber eine andere Aufgabe. In C, Java und JavaScript kann sein Ergebnis für negative Zahlen vom mathematischen Rest abweichen (siehe den Kerngedanken der Formelkarte 1).

Division mit Rest (Klasse 3 bis 4, 8–10 Jahre)	\(17 : 5 = 3\) Rest \(2\) rechnen können Mit „Divisor × Quotient + Rest = Dividend“ die Probe machen können
Vielfache und Teiler (Klasse 5 bis 6, 10–12 Jahre)	Wissen, dass \(24\) ein Vielfaches von \(12\) ist Wissen, was der größte gemeinsame Teiler ist (er wird in der Bedingung „teilerfremd“ für das Teilen einer Kongruenz gebraucht)
Negative Zahlen (Klasse 6 bis 7, 11–13 Jahre)	Mit negativen Zahlen addieren, subtrahieren und multiplizieren können (zum Beispiel \(3 \times (-3) = -9\)) Wissen, dass \(-3\) auf dem Zahlenstrahl kleiner als \(-2\) ist (links davon liegt)
Potenzen (Klasse 6 bis 8, 11–14 Jahre)	Wissen, dass der Exponent rechts oben angibt, wie oft multipliziert wird, wie in \(3^{4} = 3 \times 3 \times 3 \times 3 = 81\) Die Potenzgesetze \(a^{m} \times a^{n} = a^{m+n}\) und \((a^{m})^{n} = a^{mn}\) anwenden können (sie sind der Grund dafür, dass das wiederholte Quadrieren funktioniert)
Die Division mit Rest bei ganzen Zahlen (Oberstufe, 16–19 Jahre)	Wissen, dass sich die Division 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 Den Gedanken kennen, ganze Zahlen nach ihrem Rest einzuteilen (gerade und ungerade Zahlen sind die Einteilung nach dem Rest bei der Division durch 2)

Modulo-Rechner (a mod n, Kongruenz und Potenz mod n)

Inhaltsverzeichnis

Was Sie auf dieser Seite tun können

Wofür ist diese Berechnung nützlich?

Formeln und Abbildungen

Symbole und Begriffe

Symbole

Begriffe

Was Sie vorab wissen sollten

Mit Excel berechnen

Mit Google Tabellen berechnen

Mit Python berechnen

Die Formel in LaTeX und anderen mathematischen Schreibweisen (zum Kopieren)

Die Berechnung von ChatGPT ausführen lassen

Anleitung

Die Vorteile von DataChef

Verwandte Funktionen

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

Löst ax + by = c in ganzen Zahlen, mit den Schritten des euklidischen Algorithmus, der allgemeinen Lösung und der Eingrenzung auf positive Lösungen

ggT Rechner (größter gemeinsamer Teiler)

Berechnet den größten gemeinsamen Teiler von zwei oder mehr ganzen Zahlen, erklärt mit Primfaktorzerlegung und euklidischem Algorithmus

Schriftliche Division (Rechner mit Rest und Rechenschritten)

Rechnet Divisionen mit ganzen Zahlen und Dezimalzahlen im Layout der schriftlichen Division, mit Erklärung jedes Schritts (teilen, multiplizieren, subtrahieren, 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