2. Die Kongruenz modulo m
Teilbarkeit in den ganzen Zahlen
Eine ganze Zahl a heißt teilbar durch eine ganze Zahl m, in Zeichen m|a (gelesen: m ist ein Teiler von a), falls es eine ganze Zahl d gibt mit dm = a.
Kongruenz modulo m
Sei m ≥ 1 eine natürliche Zahl. Zwei ganze Zahlen a und b heißen kongruent modulo m, falls m|(a − b). Dies ist gleichbedeutend damit, dass a und b denselben Rest bei Division durch m haben. Sind a und b kongruent modulo m, so schreiben wir
a ≡ m b oder a ≡ b mod(m).
Wir setzen:
[ a ] = [ a ]m = a/≡ m = { b ∈ ℤ | b ≡ m a } = { …, a − 2m, a − m, a, a + m, a + 2m, … }, (Restklasse von a modulo m)
ℤ/mℤ = ℤm = { [ a ] | a ∈ ℤ } = { [ 0 ], …, [ m − 1 ] },
[ a ] + [ b ] = [ a + b ], [ a ] · [ b ] = [ a · b ] für alle a, b ∈ ℤ.
Rechenregeln
Für alle a, b, c, x, y ∈ ℤ gelten:
(a) | a ≡ m a, a ≡ m b genau dann, wenn b ≡ m a, a ≡ m b und b ≡ m c impliziert a ≡ m c, |
(b) | a ≡ m b genau dann, wenn a − b ≡ m 0, |
(c) | a ≡ m b und c ≡ m d impliziert xa + yc ≡ m xb + yd und ac ≡ m bd, |
(d) | a ≡ m b impliziert p(a) ≡ m p(b) für jedes Polynom p ∈ ℤ[ X ]. |
Algebraische Eigenschaften
Die Menge ℤm bildet mit den Restklassenoperationen + und ·:
(a) | eine abelsche Gruppe (ℤm, +), |
(b) | einen Ring (ℤm, +, ·) mit 0 = [ 0 ] und 1 = [ 1 ], |
(c) | genau dann eine abelsche Gruppe (ℤm − { [ 0 ] }, ·), wenn m prim ist, |
(d) | genau dann einen Körper (ℤm, +, ·), wenn m prim ist. |