2

I seem to be having a lot of trouble finding a place to start in proving that

$$(a \cdot b) \mod m = ((a \mod m) \cdot (b \mod m)) \mod m$$ Any ideas on how I should go about doing this? I've been trying for about 30 minutes now with no progress.

Winther
  • 24,478
user2789945
  • 153

1 Answers1

3

$(a\cdot b)\pmod m = (a\cdot b) - km$ for some natural number $k$ But $(a\pmod m) \cdot (b\pmod m) = (a-k_1m)(b-k_2m) = a\cdot b - (ak_2 + bk_1)m + k_1k_2m^2 = a\cdot b - m(ak_2 +bk_1-k_1k_2m )$ where $(ak_2 +bk_1-k_1k_2m )$ is just a natural number we can call $k$.

elDin0
  • 1,396