Die Kürzungsregel für Kongruenzen

 Wir beginnen mit einer sehr nützlichen Regel über das Kürzen von Faktoren in Kongruenzen.

Satz (Kürzungsregel für Kongruenzen)

Seien a, b, c, m  ∈  ℤ mit m ≥ 1. Dann sind äquivalent:

(a)

ca ≡  cb  mod(m).

(b)

a ≡  b  mod(m/(c, m)).

Sind c und m teilerfremd, so gilt

ca ≡  cb  mod(m)  genau dann, wenn  a ≡  b  mod(m)

Beweis

Die zweite Äquivalenz ergibt sich aus der ersten für den Spezialfall (m, c) = 1. Es genügt also, die erste Äquivalenz zu zeigen. Zur Vereinfachung der Notation setzen wir

m′  =  m(c, m)  und  c′  =  c(c, m).

(a) impliziert (b):

Es gelte ca ≡  cb (m). Wegen m | c(a − b) gilt m′ | c′ (a − b). Da die Zahlen m′ und c′ teilerfremd sind, muss m′ | (a − b) gelten. Also gilt wie gewünscht a ≡  b (m′).

(b) impliziert (a):

Es gelte a ≡  b (m′). Dann gilt m′ | (a − b), sodass m | (c, m) (a − b). Aus (c, m) | c folgt m | c (a − b) = ca − cb und damit ca ≡  cb (m).

 Wir betrachten einige Beispiele.

Beispiele

(1)

Es gilt 4 ≡  28 (3). Wegen (2, 3) = (4, 3) = 1 können wir durch 2 und 4 Kürzen. Es gilt 2 ≡  14 (3) und 1 ≡  7 (3).

(2)

Es gilt 4 ≡  8 (4). Wegen non(2 ≡  4 (4)) ist das Kürzen durch 2 ohne Veränderung des Moduls nicht möglich. Die Kürzungsregel liefert wegen 4/(2, 4) = 2 die korrekte Aussage 2 ≡  4 (2).

(3)

Es gilt 4 ≡  12 (4). Weiter ist 2 ≡  6 (4) korrekt, aber durch die Kürzungsregel nicht abgedeckt, da (2, 4) = 2. Die Kürzungsregel liefert lediglich 2 ≡  6 (2).