Modulare-Arithmetik-Uhr

Wähle den Modul n und eine Operation. Sieh das Ergebnis auf einer modularen Uhr und untersuche Additions-/Multiplikationstabellen.

Rechenbeispiel — Modulare-Arithmetik-Uhr

Ausdruck	7 x 5 (mod 12)
Ergebnis	11

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Ein Primmodul erlaubt wieder das Dividieren 🖖

Die modulare Arithmetik befasst sich mit ganzen Zahlen unter einem zyklischen Modul n, geschrieben als a ≡ b (mod n). Dieses algebraische System bildet einen kommutativen Ring Z/nZ. Ist der Modul p eine Primzahl, wird der Ring zu einem Körper, in dem jedes Element außer Null ein multiplikatives Inverses besitzt.

Warum man von Uhrenarithmetik spricht 🖖

Auf einer 12-Stunden-Uhr ist 4 Stunden nach 11 Uhr die 3 und nicht die 15 — die Zahlen springen zurück an den Anfang, sobald sie die 12 überschreiten. Genau das ist modulare Arithmetik: a ≡ b (mod n) bedeutet, dass a und b bei Division durch n denselben Rest lassen. Also gilt 15 ≡ 3 (mod 12). Kern der Sache: Modulare Arithmetik behält nur den Rest nach der Division, und die Uhr dieses Tools zeigt, wie die Zahlen im Kreis laufen.

Die Neunerregel ist versteckte modulare Arithmetik 🖖

Die alte Regel „eine Zahl ist durch 9 teilbar, wenn ihre Ziffernsumme durch 9 teilbar ist“ ist reine modulare Arithmetik. Weil 10 ≡ 1 (mod 9) gilt, ist auch jede Zehnerpotenz ≡ 1, sodass eine Zahl kongruent zu ihrer Ziffernsumme (mod 9) ist. Dieselbe Tatsache steckt hinter der Neunerprobe, einem jahrhundertealten Verfahren, um Rechnungen von Hand zu prüfen.

MODULARE ARITHMETIK — WANN DARF MAN TEILEN UND WANN NICHT?

In welchem Fall der modularen Arithmetik bist du?

Modulo n zu rechnen heißt, nur den Rest zu behalten, und Addition, Subtraktion und Multiplikation überstehen das unbeschadet. Nur die Division nicht. Ob man durch eine Zahl teilen darf — ob sie ein Inverses hat — hängt allein davon ab, ob sie einen Faktor mit n teilt. Deshalb verhält sich ein Primmodul so anders als ein zusammengesetzter. Welcher Fall vorliegt, hängt von der Rechenart ab und davon, was für eine Zahl n ist.

Addition — immer gutartig, ganz gleich welches n 13 + 5 ≡ 6 (mod 12)

Primmodul — durch jedes Element außer null darf man teilen φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Zusammengesetztes Modul — durch die meisten Elemente darf man nicht teilen 2 × 3 ≡ 0, φ(6) = 2

Wiederholte Potenzen — sie kreisen, und Fermat sagt wo a^p−1 ≡ 1 (mod p)

Addition — immer gutartig, ganz gleich welches n

Was du weißt: Beliebiges Modul. Addieren, Subtrahieren und Multiplizieren mod n sind stets definiert, und jedes Element hat ein additives Gegenstück.

Was zu prüfen ist: 13 + 5 ≡ 6 (mod 12)

Rechenbeispiel: Eine 12-Stunden-Uhr: 13 + 5 = 18, und 18 mod 12 = 6. Fünf Stunden nach eins ist sechs.

Diesen Fall öffnen: Uhr mod 12

Addition — immer gutartig, ganz gleich welches n. Die Additionstafel mod 12: jede Zeile ist die vorige um eins verschoben, und jeder Wert kommt genau einmal vor. Beliebiges Modul. Addieren, Subtrahieren und Multiplizieren mod n sind stets definiert, und jedes Element hat ein additives Gegenstück. — Die Additionstafel mod 12: jede Zeile ist die vorige um eins verschoben, und jeder Wert kommt genau einmal vor.

Primmodul — durch jedes Element außer null darf man teilen

Was du weißt: n ist prim. Dann teilt kein Element außer null einen Faktor mit n, also hat jedes ein multiplikatives Inverses.

Was zu prüfen ist: φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Rechenbeispiel: Mod 7: 3 × 4 = 12 ≡ 5. Alle sechs Werte 1…6 sind invertierbar, deshalb enthält die Multiplikationstafel unterhalb der ersten Zeile keine Null.

Diesen Fall öffnen: Primzahl mod 7

Primmodul — durch jedes Element außer null darf man teilen. Die Multiplikationstafel mod 7: unterhalb der ersten Zeile keine Null, und jede Zeile eine Permutation von 1 bis 6. n ist prim. Dann teilt kein Element außer null einen Faktor mit n, also hat jedes ein multiplikatives Inverses. — Die Multiplikationstafel mod 7: unterhalb der ersten Zeile keine Null, und jede Zeile eine Permutation von 1 bis 6.

Zusammengesetztes Modul — durch die meisten Elemente darf man nicht teilen

Was du weißt: n ist zusammengesetzt. Nur die zu n teilerfremden Werte haben Inverse; die übrigen sind Nullteiler, und durch sie zu teilen ist sinnlos.

Was zu prüfen ist: 2 × 3 ≡ 0, φ(6) = 2

Rechenbeispiel: Mod 6: 2 × 4 = 8 ≡ 2. Weder 2 noch 4 ist invertierbar, denn ggT(2,6) = 2 und ggT(4,6) = 2. Nur 1 und 5 sind Einheiten — zwei von sechs.

Diesen Fall öffnen: zusammengesetzt mod 6

Zusammengesetztes Modul — durch die meisten Elemente darf man nicht teilen. Die Multiplikationstafel mod 6, durchsetzt mit Nullen und mit nur zwei Zeilen, die Permutationen sind. n ist zusammengesetzt. Nur die zu n teilerfremden Werte haben Inverse; die übrigen sind Nullteiler, und durch sie zu teilen ist sinnlos. — Die Multiplikationstafel mod 6, durchsetzt mit Nullen und mit nur zwei Zeilen, die Permutationen sind.

Wiederholte Potenzen — sie kreisen, und Fermat sagt wo

Was du weißt: Potenzieren mod n. Für eine Primzahl p und ein nicht durch p teilbares a wiederholen sich die Exponenten mit einer Periode, die p − 1 teilt.

Was zu prüfen ist: a^p−1 ≡ 1 (mod p)

Rechenbeispiel: Mod 13: 7¹² ≡ 1. Der kleine Satz von Fermat garantiert das für jede Basis von 1 bis 12, ohne eine einzige große Potenz auszurechnen.

Diesen Fall öffnen: Fermat mod 13

Wiederholte Potenzen — sie kreisen, und Fermat sagt wo. Die Potenzen jeder Basis mod 13; die Spalte bei Exponent 12 kehrt für jede Einheit zur 1 zurück. Potenzieren mod n. Für eine Primzahl p und ein nicht durch p teilbares a wiederholen sich die Exponenten mit einer Periode, die p − 1 teilt. — Die Potenzen jeder Basis mod 13; die Spalte bei Exponent 12 kehrt für jede Einheit zur 1 zurück.

Aufgabe vollständig gelöst

Auswerten von 7 12 mod 13 auf dem gesamten Gitter 5 Schritte
Berechnen Sie 7¹² mod 13, ohne 7¹² jemals aufzuschreiben. Dies ist die Operation a^k mit n = 13, a = 7 und k = 12, und das Gitter ist die vollständige Tabelle von a^k mod 13.
1. 7¹² ist 13 841 287 201 — elf Stellen für ein Ergebnis, das zwischen 0 und 12 liegen muss. Reduktion bleibt unter Multiplikation erhalten: Der Rest eines Produkts hängt nur von den Resten seiner Faktoren ab, sodass man nach jedem Schritt reduzieren kann statt erst am Ende.
  
  $7^{12} = 13841287201, x y mod n = ((x mod n) (y mod n)) mod n$
2. Fermats kleiner Satz bestimmt das Ergebnis, noch bevor irgendeine Arithmetik stattfindet. Für eine Primzahl p und ein a, das p nicht teilt, gilt a^p−1 ≡ 1; hier ist p = 13 und k ist genau p − 1, sodass das Ergebnis 1 lautet und alles Folgende eher eine Überprüfung des Satzes als eine Suche nach dem Ergebnis ist.
  
  $p = 13 prime, 13 ∤ 7 ⟹ 7^{12} = 7^{p - 1} \equiv 1 (mod 13)$
3. Quadrieren verdoppelt den Exponenten, sodass drei Quadrierungen 7⁸ erreichen. Jede Zeile reduziert, bevor die nächste beginnt, weshalb keine Zahl in der gesamten Berechnung 100 übersteigt.
  
  $7^{2} = 49 \equiv 10, 7^{4} \equiv 1 0^{2} = 100 \equiv 9, 7^{8} \equiv 9^{2} = 81 \equiv 3 (mod 13)$
4. 12 ist 8 + 4, und beide dieser Potenzen wurden auf dem Weg nach oben berechnet, sodass eine weitere Multiplikation die Rechnung abschließt. Insgesamt vier Multiplikationsschritte gegenüber den elf, die ein Produkt von zwölf Siebenen von links nach rechts benötigen würde — und die Ersparnis wächst mit dem Exponenten, nicht mit dem Modul.
  
  $12 = 110 0_{2} = 8 + 4 ⟹ 7^{12} \equiv 7^{8} \cdot 7^{4} \equiv 3 \times 9 = 27 \equiv 1 (mod 13)$
5. Die Ordnung von 7, also das kleinste k mit 7^k ≡ 1, muss 12 teilen; sie ist also eine von 1, 2, 3, 4, 6 und 12. Die Überprüfung der fünf echten Teiler schließt jeden einzelnen von ihnen aus, sodass die Ordnung exakt 12 beträgt.
  
  $7^{1} \equiv 7, 7^{2} \equiv 10, 7^{3} \equiv 5, 7^{4} \equiv 9, 7^{6} \equiv 12 ⟹ ord_{13} (7) = 12$
Antwort

Die drei Quadrierungen und die abschließende Multiplikation geben die Zeile des Werkzeugs für a = 7 fehlerfrei wieder: 10 bei k = 2, 9 bei k = 4, 3 bei k = 8 und 1 bei k = 12, wo Fermat es vorhergesagt hat. Da die Ordnung 12 beträgt und kein echter Teiler davon ist — die Ordnungsprüfung ergab 12 bei k = 6, was ungleich 1 ist —, ist diese Zeile eine Permutation der Zahlen 1 bis 12, die jeden Rest ungleich null genau einmal trifft, was 7 zu einer Primitivwurzel mod 13 macht. Liest man die Zeile nun in der anderen Richtung: Gegeben ist 11, gesucht ist k. Dafür gibt es kein Square-and-Multiply, sondern nur eine Suche, und diese Asymmetrie zwischen einfachem Vorwärts- und schwerem Rückwärtsrechnen ist die gesamte Grundlage des Diffie-Hellman-Schlüsselaustauschs. Der Algorithmus skaliert auf eine Weise, wie es die Tabelle nicht kann: Ein 2048-Bit-Exponent kostet höchstens etwa 4 000 modulare Multiplikationen, während die durch ihn bezeichnete Potenz etwa 2,7 × 10⁶¹⁶ Stellen benötigen würde, um ausgeschrieben zu werden.

$ord_{13} (7) = 12 ⟹ {7^{k} mod 13}_{k = 1}^{12} = {1, 2, \dots, 12}$

Lernpfad

Wenn zwei Dinge auf demselben Wert landen

Führt zu Geburtstagsparadoxon

Quellen (1)

The congruence sign this tool prints, and the book that introduced it: C. F. Gauss, Disquisitiones arithmeticae. Leipzig, 1801 — Section I defines a ≡ b (mod n); Section II is where a prime modulus starts behaving like a field. Digitised by the Smithsonian Libraries.

Vom 42Math-Team · Aktualisiert 2026-08-17

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Mathematik →

Beispielaufgaben

Uhr mod 12 - Uhrzeitarithmetik: 13 ≡ 1 (mod 12), daher ergibt 13+5 im Kreis 6.
Primzahl mod 7 - Primzahlmodul: Die Multiplikationszeilen ungleich null verhalten sich wie Permutationen.
zusammengesetzt mod 6 - Bei einem zusammengesetzten Modul wiederholen sich Zeilen, für die gcd(row,n) > 1 gilt.
Fermat mod 13 - Muster nach Fermat: a^(p-1) ≡ 1 mod p für eine Primzahl p mit gcd(a,p)=1.