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?
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)
To prove the congruence relation ab ≡ [(a mod m) · (b mod m)] (mod m) for all m ≥ 2, we can use the definition of congruence.
Let's start by considering the left-hand side (LHS) of the congruence: ab (mod m). This means that ab and (a mod m) · (b mod m) differ by a multiple of m.
Now, let's represent a = qm + r and b = sm + t, where q, r, s, and t are integers. This is possible since a and b are integers and m ≥ 2.
Substituting these representations into the LHS (ab (mod m)), we get:
ab = (qm + r)(sm + t) = qs(m^2) + (qt + rs)m + rt
Now, let's consider each term in the expression qs(m^2) + (qt + rs)m + rt modulo m:
qs(m^2) ≡ 0 (mod m) [since m divides m^2]
(qt + rs)m ≡ 0 (mod m) [since m divides m]
rt ≡ r (mod m) [since m divides t, leaving r as the remainder]
Therefore, ab ≡ rt (mod m).
Now let's consider the right-hand side (RHS) of the congruence: (a mod m) · (b mod m) (mod m). This means that (a mod m) · (b mod m) and rt differ by a multiple of m.
(a mod m) = r and (b mod m) = t, so (a mod m) · (b mod m) = rt.
Therefore, (a mod m) · (b mod m) ≡ rt (mod m).
Since both the LHS and RHS are congruent to rt (mod m), we can conclude that ab ≡ [(a mod m) · (b mod m)] (mod m) for all m ≥ 2.
This completes the proof for all cases, including cases where m > 2.