Hello! Today we will be continuing the series on modular arithmetic! We will not be introducing anything new until the very end, rather just confirming/proving Part 2’s theorem. I will start by proving each part of our theorem. Then, in part 3b, we will dive deeper with… Multiplication tables? Oh, and also remember to check out the first 2 blogs of the series below! And with that out of the way, lets begin!
To begin, just in case you forgot, here is last blog’s theorem:
Theorem: Let a≡b mod m, and c≡d mod m. Then, all the following statements are true:
a+c ≡ b+d mod m
ac ≡ bd mod m
ac ≡ bc mod m
Ok, so before we prove this, we need to go back a bit. We didn’t actually define what it means for two numbers to be congruent mod m. So let’s do that!
Modular arithmetic formal definition
We say that a≡b mod m if and only if (In the business of proofs, this is sometimes abbreviated as iff, so if I use this in the future you know what I mean):
a+km=b for some integer k
Why it makes sense
The above definition makes sense, because all it is saying, is “If you start at a, and do k rotations around the clock, you get to b.” The reason why you’re doing the k rotations is because every m steps around the clock you go, you do a full rotation, and you’re doing that k times.
Theorem parts 1 and 2
Since a≡b, we have a+jm=b for some j. And since c≡d, c+lm=d, for some l. Thus, a+c+jm+lm=b+d. Therefore:
Since j and l are integers, j+l is an integer, and thus:
a+c≡b+d mod m
Since a≡b, we have a+jm=b for some j. And since c≡d, c+lm=d, for some l. Thus, (a+jm)(c+lm)=bd. Therefore:
Since a, c, j, l, and m are integers, aj+cl+jlm is an integer, and thus:
ac≡bd mod m
Theorem part 3
I forgot to mention this in the original theorem, but since we are only dealing with integers, we will not be using negative powers, so assume c is non-negative. Now, since a≡b, we have a+jm=b for some j. Now, we use induction:
Base Case: c=0
In this case, a0=1=b0.
Let c=k hold. Then, we know that:
By part 2 of the theorem, we now know that:
Before we end off, I would like to give you something to think about. Like I said at the start we will be exploring multiplication tables next week, so draw a multiplication table for the numbers 5, 6, 7, and 8. Notice anything special about the 5 and 7 grids that the 6 and 8 grids do not have? If you do, then you will be more than prepared for part 4! If not, worry not, as I will explain it all next time!