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?

3 3 3 Uhr nachmittags und 15 15 15 Uhr sind auf der Zeigeruhr dieselbe Stelle . Ebenso 2 2 2 Uhr und 14 14 14 Uhr. Für die Uhr sind solche Zahlen „gleich gut“ – sie lassen beim Teilen durch 12 12 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 3^{2026} 3 2026 zu finden. Am Zahlenstrahl: Die Zahlen 2 , 5 , 8 , 11 , 14 2, 5, 8, 11, 14 2 , 5 , 8 , 11 , 14 haben alle Abstand 3 3 3 voneinander und lassen beim Teilen durch 3 3 3 alle den Rest 2 2 2 :
Kongruent modulo 3 – alle mit Rest 2
0123456789101112131415
Die Zahlengerade

Formel mit Erklärung

Definition Zwei ganze Zahlen a a a und b b b heißen kongruent modulo m m m , wenn sie beim Teilen durch m m m denselben Rest lassen. Man schreibt: a ≡ b ( m o d m ) a \equiv b \pmod{m} a ≡ b ( mod m ) gelesen: „ a a a ist kongruent zu b b b modulo m m m “ (auch: „restgleich“). Gleichwertig – oft schneller zu prüfen: a ≡ b ( m o d m ) ⟺ m ∣ ( a − b ) a \equiv b \pmod{m} \quad\Longleftrightarrow\quad m \mid (a - b) a ≡ b ( mod m ) ⟺ m ∣ ( a − b ) Die Differenz ist durch m m m teilbar. Das passt zum Zahlenstrahl: Man kommt mit lauter m m m -Schritten von a a a nach b b b . Rechenregeln – man darf jede Zahl durch eine kongruente (meist kleinere) ersetzen: Ist a ≡ b ( m o d m ) a \equiv b \pmod{m} a ≡ b ( mod m ) und c ≡ d ( m o d m ) c \equiv d \pmod{m} c ≡ d ( mod m ) , dann gilt a + c ≡ b + d , a − c ≡ b − d , a ⋅ c ≡ b ⋅ d , a n ≡ b n ( alles    m o d   m ) 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) a + c ≡ b + d , a − c ≡ b − d , a ⋅ c ≡ b ⋅ d , a n ≡ b n ( alles  mod m ) Achtung: Kürzen (Teilen) ist so nicht erlaubt: 2 ⋅ 3 ≡ 2 ⋅ 1 ( m o d 4 ) 2 \cdot 3 \equiv 2 \cdot 1 \pmod{4} 2 ⋅ 3 ≡ 2 ⋅ 1 ( mod 4 ) , aber 3 ≢ 1 ( m o d 4 ) 3 \not\equiv 1 \pmod{4} 3  ≡ 1 ( mod 4 ) .

Beispiele

Leicht#1
Gilt 11 ≡ 5 ( m o d 3 ) 11 \equiv 5 \pmod{3} 11 ≡ 5 ( mod 3 ) ? Gilt 14 ≡ 6 ( m o d 4 ) 14 \equiv 6 \pmod{4} 14 ≡ 6 ( mod 4 ) ? Weg 1 – Reste vergleichen: 11 : 3 = 3  Rest  2 , 5 : 3 = 1  Rest  2 ⇒ 11 ≡ 5 ( m o d 3 )   ✓ 11: 3 = 3 \text{ Rest } 2, \qquad 5: 3 = 1 \text{ Rest } 2 \qquad\Rightarrow\qquad 11 \equiv 5 \pmod{3}\ ✓ 11 : 3 = 3  Rest  2 , 5 : 3 = 1  Rest  2 ⇒ 11 ≡ 5 ( mod 3 )   ✓ Weg 2 – Differenz prüfen: 14 − 6 = 8 , 4 ∣ 8 ⇒ 14 ≡ 6 ( m o d 4 )   ✓ 14 - 6 = 8, \qquad 4 \mid 8 \qquad\Rightarrow\qquad 14 \equiv 6 \pmod{4}\ ✓ 14 − 6 = 8 , 4 ∣ 8 ⇒ 14 ≡ 6 ( mod 4 )   ✓

Zusammenfassung

a ≡ b ( m o d m ) a \equiv b \pmod{m} a ≡ b ( mod m ) : a a a und b b b lassen beim Teilen durch m m m denselben Rest. Gleichwertig: m m m teilt die Differenz a − b a - b a − b . Plus, minus, mal und Potenzieren darf man mit kleineren kongruenten Zahlen rechnen. Teilen/Kürzen ist nicht einfach so erlaubt. Trick für große Potenzen: Potenz suchen, die ≡ 1 \equiv 1 ≡ 1 ist, dann die Hochzahl zerlegen.

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: