Jan 02 2016

Modular Multiplication Rule Proof

I must stay focused. I must stay focused. I must stay … I wonder what’s new on Facebook.

I don’t really feel like writing this post mostly because I know that it will be very similar to the other two I have already done: modular addition rule proof and modular subtraction rule proof, but my New Year’s Resolution is to follow things through to completion. Well, that would’ve been my News Years resolution if I had made one. Either way, it’s back to modular arithmetic.

The rule for doing multiplication in modular arithmetic is:

(a * b) \bmod{c} = (a \bmod{c} * b \bmod{c}) \bmod{c}

This says that if we multiply integer a times integer b and take the product modulo c, we get the same answer as if we had first taken a modulo c and multiplied by b modulo c and taken that product modulo c.

Proof

The fact that this rule looks very similar to the two we have already covered should be a good clue that the proof is going to be similar as well. And it is. We start the same way we previously have – by defining a and b using the quotient remainder theorem:

a = cq_{1} + r_{1} where 0 \leq r_{1} < c this means that a \bmod{c} = r_{1}
b = cq_{2} + r_{2} where 0 \leq r_{2} < c this means that b \bmod{c} = r{2}

Substituting for a and b in the left hand side of the multiplication rule:

(a * b) \bmod{c} = ((cq_{1} + r_{1}) * (cq_{2} + r_{2})) \bmod{c}
(a * b) \bmod{c} = (c^{2}q_{1}q_{2}) + cq_{2}r_{1} + cq_{1}r_{2} + r_{1}r_2{2}) \bmod{c}

Since we are doing modulo c we can remove all of the terms that have a c in them, leaving us with:

(a * b) \bmod{c} = (r_{1} * r_{2}) \bmod{c}

The substitutions for the right hand side of the multiplication rule are exactly the same as the proofs we’ve previously done:

((cq_{1} + r_{1}) * (cq_{2} + r_{2})) \bmod{c} = (r_{1} * r_{2}) \bmod{c}

Left hand side equals right hand side, and all is right with the world. Stay tuned for exponentiation and division. I am sure you are dying to know how their rules get proved.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.