Modular Arithmetic: Part 3 (Proving stuff)

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 ab mod m, and cd 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 ab, we have a+jm=b for some j. And since cd, 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+cb+d mod m

Since ab, we have a+jm=b for some j. And since cd, 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:

acbd 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 ab, 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:

akbk

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!

Part 4!

10 Replies to “Modular Arithmetic: Part 3 (Proving stuff)”

  1. 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”?

  2. 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.

  3. 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?

Leave a Reply to Atharv Nadkarni Cancel reply

Your email address will not be published. Required fields are marked *

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