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:

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

### 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 and using the quotient remainder theorem:

where  this means that
where this means that

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

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

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

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.