(a*b) mod m = ((a mod m) * (b mod m)) mod m?
Wie beweist man das?
Ich weiß wie es für + oder - geht, man benutzt das
m | a - (a mod m), aber ich weiß nicht inwiefern mich das hier weiterbringt... Hat jemand einen Tipp?
1 Antwort
Vom Fragesteller als hilfreich ausgezeichnet
Nutzer, der sehr aktiv auf gutefrage ist
Du kannst schreiben
a = a' + n_a * m, b = b' + n_b * m
mit a', b'\in {0...m-1} und n_a, n_b\in Z.
Dann gilt
a * b = a' * b' + m * R
R kannst du ausrechnen, ist in Z.
Dann ist
a * b = a'*b' (mod m)
