a quick google search turned up several locations where it is proven as a corollary. Just search for
ab (mod m) = (a(mod m) * b(mod m)) (mod m)
Let a, b, and m be integers, and m ≥ 2. Prove that:
ab ≡ [ (a mod m) · (b mod m) ] (mod m).
So I tried proof by cases:
Assume ab ≡ [(a mod m) ∙ (b mod m)] mod m is true.
Then ab mod m = [(a mod m) ∙ (b mod m)] mod m,
and (ab-[(a mod m) ∙ (b mod m)])/m = k, where k is an integer.
Case 1: m = 2, a is even, b is even
Case 2: m = 2, a is even, b is odd
Case 3: m = 2, a is odd, b is even
Case 4: m = 2, a is odd, b is odd
I won't show all the work I did for cases 1-4, but I was able to conclude that (ab-[(a mod m) ∙ (b mod m)])/m was equal to an integer type expression for those cases. However, I currently only have proofs for m = 2. What about m > 2? Well I tried that, but I keep getting a result that cannot be expressed as an integer. Would someone be willing to help me prove the congruence relation for the cases where m > 2?
1 answer
1 answer