Zum Hauptinhalt springen
PlayMemorize

Modulare Arithmetik

17 ≡ 5 (mod 12)
17 und 5 lassen bei Division durch 12 denselben Rest.

Modulare Arithmetik ist Arithmetik auf einem Kreis. Zwei Zahlen sind modulo n kongruent, wenn sie sich um ein Vielfaches von n unterscheiden. Eine Uhr rechnet modulo 12: Zehn Stunden nach 5 Uhr ist 3 Uhr und nicht 15 Uhr. Diese einfache Idee liegt der modernen Kryptographie, Hashfunktionen, Fehlerkorrekturcodes und großen Teilen der Zahlentheorie zugrunde.

Die Uhr modulo 12: Addition läuft im Kreis
1 2 3 4 5 6 7 8 9 10 11 12 17 mod 12 = 5 17 = 1 × 12 + 5
Überprüfung des kleinen Satzes von Fermat
a^(p−1) ≡ 1 (mod p) when p is prime, p∤a
Example p=5, a=2: 2⁴ = 16 = 3×5 + 1 ≡ 1 (mod 5) ✓
Example p=7, a=3: 3⁶ = 729 = 104×7 + 1 ≡ 1 (mod 7) ✓
Used in RSA encryption to prove decryption recovers the original message.
Additionstabelle für ℤ/5ℤ, also die ganzen Zahlen mod 5
Jede Zeile und jede Spalte enthält {0,1,2,3,4} genau einmal. Die fünf Elemente bilden unter Addition modulo 5 eine abgeschlossene Gruppe. Rot markiert sind Summen, die über 4 hinausgehen und umklappen.
+01234
001234
112340
223401
334012
440123
Verwandte Themen
Primzahlen Vollkommene Zahlen Zahlensysteme
Kurzfakten zur modularen Arithmetik

Modulare Arithmetik definiert Kongruenz: a ist kongruent zu b modulo n, wenn n die Differenz a-b teilt. Gauss systematisierte dieses Gebiet 1801. Sie bildet die Grundlage aller modernen Public-Key-Verfahren. RSA-Verschlüsselung beruht auf dem kleinen Satz von Fermat, der besagt, dass a^(p-1) kongruent zu 1 modulo p ist, sofern p prim ist und a nicht durch p teilbar ist. Hashfunktionen nutzen modulare Operationen, um große Eingaben auf feste Ausgaben abzubilden. Die ganzen Zahlen modulo n bilden einen vollständigen Ring, und falls n prim ist, sogar einen endlichen Körper.

Verwendet in
∑Mathematik
✓
⚛Physik
-
⚙Ingenieurwesen
-
🧬Biologie
-
💻Informatik
✓
📊Statistik
-
📈Finanzen
-
🎨Kunst
-
🏛Architektur
-
♪Musik
✓
🔐Kryptografie
✓
🌌Astronomie
-
⚗Chemie
-
🦉Philosophie
-
🗺Geografie
-
🌿Ökologie
-
Möchtest du dein Wissen testen?
Frage
Was ist modulare Exponentiation und warum ist sie schnell?
tippen · Leertaste
1 / 10
Bereit zum Spielen?
π

Pi

Memoriere Pi, e und 38 mathematische Konstanten mit der Zahlenpfad-Methode

Jetzt spielen - kostenlos

Kein Konto nötig. Funktioniert auf jedem Gerät.

Neue Spielvideos auf YouTube Wir machen ein kurzes Video zu jedem Spiel. Abonniere den Kanal für die neuen.

OK

Kostenlos im Web Offline spielen und PlayMemorize unterstützen? Probiere die App.

App holen