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*. Then, all the following statements are true:

*≡*d mod m*a+c ≡ b+d mod m*

*ac ≡ bd mod m*

*a ^{c} ≡ b^{c} 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+jlm ^{2}=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, *a ^{0}=1=b^{0}.*

Induction Step:

Let c=k hold. Then, we know that:

*a ^{k}≡b^{k}*

By part 2 of the theorem, we now know that:

*a ^{k}a≡b^{k}b*

Thus:

*a ^{k+1}≡b^{k+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?