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:
a+c+(j+l)m=b+d
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:
ac+ajm+clm+jlm2=bd
ac+(aj+cl+jlm)m=bd
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.
Induction Step:
Let c=k hold. Then, we know that:
ak≡bk
By part 2 of the theorem, we now know that:
aka≡bkb
Thus:
ak+1≡bk+1
Conclusion
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!
The 5 and 7 grids include odd numbers, but the 6 and 8 grids don’t.
Close! But there’s a bigger pattern. Try 9 and 10 to see if you can find anything else.
9 and 10? 9 contains odd numbers, 10 does not!
Each 5 and 7 grid runs through all possible numbers(0 to 4 and 0 to 6, respectively), but the 6 and 8 grids only cover even numbers. BTW, is there a typo at “Why it makes since” ? Does it mean make “sense”?
Oh yeah! I’ll be sure to fix that!
Well, I was got corrected by Erin. She said the 5 and 7 grids do not have 0, while 6 and 8 have 0 divisors.
I found a mistake. It is in the sentence “Then, in part 3b, we will dive deeper with… Multiplication tables?” If this is the entirety of Part 3 now, can you correct it?