Kongruenz modulo
3 Uhr nachmittags und 15 Uhr sind auf der Zeigeruhr dieselbe Stelle . Ebenso 2 Uhr und 14 Uhr. Für die Uhr sind solche Zahlen „gleich gut“ – sie lassen beim Teilen durch 12 denselben Rest . Diese Art „Gleichheit“ heißt Kongruenz . Damit kann man mit riesigen Zahlen rechnen, ohne sie je auszurechnen – etwa um die letzte Ziffer von 3^{2026} zu finden. Am Zahlenstrahl: Die Zahlen 2, 5, 8, 11, 14 haben alle Abstand 3 voneinander und lassen beim Teilen durch 3 alle den Rest 2 : Definition Zwei ganze Zahlen a und b heißen kongruent modulo m , wenn sie beim Teilen durch m denselben Rest lassen. Man schreibt: a equiv b pmod{m} gelesen: „ a ist kongruent zu b modulo m “ (auch: „restgleich“). Gleichwertig – oft schneller zu prüfen: a equiv b pmod{m} quad Longleftrightarrow quad m mid (a - b) Die Differenz ist durch m teilbar. Das passt zum Zahlenstrahl: Man kommt mit lauter m -Schritten von a nach b . Rechenregeln – man darf jede Zahl durch eine kongruente (meist kleinere) ersetzen: Ist a equiv b pmod{m} und c equiv d pmod{m} , dann gilt a + c equiv b + d, qquad a - c equiv b - d, qquad a cdot c equiv b cdot d, qquad a^n equiv b^n qquad ( text{alles } bmod m) Achtung: Kürzen (Teilen) ist so nicht erlaubt: 2 cdot 3 equiv 2 cdot 1 pmod{4} , aber 3 not equiv 1 pmod{4} . Gilt 11 equiv 5 pmod{3} ? Gilt 14 equiv 6 pmod{4} ? Weg 1 – Reste vergleichen: 11 : 3 = 3 text{ Rest } 2, qquad 5 : 3 = 1 text{ Rest } 2 qquad Rightarrow qquad 11 equiv 5 pmod{3} ✓ Weg 2 – Differenz prüfen: 14 - 6 = 8, qqu
Worum geht's?
Formel mit Erklärung
Beispiele
Zusammenfassung
Jetzt üben
Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff:
