Modulo umformen?
-
Hallo,
ich arbeite momentan ein paar Aufgaben zum Thema Modulo und Kongruenzen durch. Dabei soll ich u.a. gewisse Teilbarkeiten aufzeigen. In einer Musterlösung wurde dabei wie folgt umgeformt:
(7n) mod 3 = (7 mod 3)(n mod 3) = (n mod 3)
Der letzte Schritt ist mir klar, der erste hingegen überhaupt nicht. Wieso gilt (7n) mod 3 = (7 mod 3)(n mod 3)? Wenn ich es mit einzelnen n nachrechne, so komme ich immer darauf, dass die Umformung richtig ist.
Wenn ich es aber mit anderen Zahlen versuche, scheitere ich. So ist z.B. (5*11) mod 6 = 55 mod 6 = 1, aber (5 mod 6)(11 mod 6) = 5*5 = 55. Hier gilt die Gleichheit also offensichtlich nicht. Nehme ich hingegen diese 55 nochmal modulo 6, stimmt es. Liegt hier einfach ein Fehler in der Musterlösung vor? Oder klappt das hier nur, weil 7 mod 3 = 1, also im Produkt quasi wegfällt und ((n mod 3) mod 3) = (n mod 3) gilt? Der Verfasser also quasi einfach ein paar Umformungsschritte in einem gemacht hat?
Leider habe ich zu den Rechenregeln mit Modulo im Internet kaum brauchbare Hinweise gefunden, und auch Wikipedia bringt mich da nicht weiter. Meine Frage: Gilt Folgendes immer, oder nur unter bestimmten Umständen?
(a+b) mod 5 = ((a mod 5) + (b mod 5)) mod 5
(a*b) mod 5 = ((a mod 5) * (b mod 5)) mod 5
(a^b) mod 5 = ((a mod 5)^b) mod 5Vielen lieben Dank schonmal im Voraus
-
Es wird die vierte Rechenregel von http://de.wikipedia.org/wiki/Kongruenz_(Zahlentheorie)#Rechenregeln benutzt:
a kongruent (a mod c) (mod c)
b kongruent (b mod c) (mod c)=> ab kongruent (a mod c)(b mod c) (mod c)
=> (ab mod c) = ((a mod c)(b mod c) mod c)
Weil im konkreten Fall 7 mod 3 = 1 ist, kann man das letzte "mod c" weglassen.
-
Alles klar! Vielen Dank