Man beweise folgende Regeln für das Rechnen mit Kongurenzen:
- Restklassen
Restklassen modulo
:
Allgemeines:
Modulo teilt Werte in Restklassen durch Division mit dem Mod-Wert e, d.h. beide Werte haben bei der Division durch den Faktor m (Modulo) denselben Rest.
a
b mod m bedeutet daher bei Bestehen der Kongruenz daß a/m und b/m denselben Rest haben. Daraus folgt, daß m | (b-c) gilt und somit m den Term (b-c) ohne Rest teilt (sonst nicht kongruent!).
Oder anders gesagt, eine kongruente Zahl a besteht aus m*k + r, wobei k eine beliebige Zahl ist und r der Rest. Und wenn die Reste gleich sind, liegt Kongruenz vor. Das könnte man für den Beweis verwenden und beim Nachweis der Äquivalenz jeweils alle m*k eliminieren, da ja nur die Reste für die Kongruenz von Bedeutung sind.
a
b (mod m)
m*k1 + r1
m*k2 + r1 (mod m)
r1 = r1
c
d (mod m)
m*k3 + r2
m*k4 + r2 (mod m)
r2 = r2
Hapi
(a + c)
(b + d) (mod m)
(m*k1 + m*k3 + r1 + r2)
(m*k2 + m*k4 + r1 +r2) (mod m)
r1 + r2 = r1 + r2 somit Äquivalenz gegeben.
a
b (mod m)
m*k1 + r1
m*k2 + r1 (mod m)
r1 = r1
c
d (mod m)
m*k3 + r2
m*k4 + r2 (mod m)
r2 = r2
(a * c)
(b * d) (mod m)
(m*k1 + r1)* (m*k3 + r2)
(m*k2 +r1) * (m*k4 + r2) (mod m)
r1 * r2 = r1 * r2 somit Äquivalenz gegeben.
a
b (mod m)
m*k1 + r1
m*k2 + r1 (mod m)
r1 = r1
c
d (mod m)
m*k3 + r2
m*k4 + r2 (mod m)
r2 = r2
(a / c)
(b / d) (mod m)
(mod m)
r1 / r2 = r1 / r2 somit Äquivalenz gegeben.
Hapi