Modular Arithmetic Part 2 (Properties and equations)

Hello, and welcome to the second blog of my ‘Quitagy’ on modular arithmetic! Last time we ended off on defining modular arithmetic formally, and this time we will continue that kind of trend by looking at useful properties of the curious systems and mechanisms behind modular arithmetic! To start, I will state what we will be proving in today’s blog. Oh, and also, if you haven’t already, be sure to look at last post, where we introduced modular arithmetic

Modular Arithmetic (Part 1)

Formal statement/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

a^c ≡ b^c mod m

Explanation

All the previous theorem is saying, is that in modular arithmetic, we can simplify most terms before actually solving. This is very helpful, but before we prove it, lets make some more sense of it with some examples!

Exercises!

Easy

Find the simplest positive value for:

2783+2845+8483+3887 mod 3

Medium

Find the simplest positive value for:

19*347*58*95*58*46 mod 3

Hard

Find the simplest positive value for:

38¹⁰ mod 5

Challenge!

Find the simplest positive value for:

3904⁵⁸³⁴*9481⁵⁸⁴⁴*2¹¹ mod 6

Do NOT scroll down until you are done with the problems!

|
|
|
|
|
|
|
|
|
|

Solutions!

Easy

There are 2 good ways to solve this:

Solution 1

We simply add all the number together to get 17998, and then divide by 3 to get remainder 1.

Solution 2

We use the theorem and simplify each term using the divisibility rule for 3 to get:

2+1+2+2≡7≡1 mod 3

Medium

Similar to solution 2 of the last problem, we simplify each number individually first to get:

1*2*1*2*1*1≡4≡1 mod 3

Hard

This one is a bit trickier, mostly because you can’t simplify exponents (Reread the third part of the theorem if you are confused). So to start, we simplify what we can, the base:

38¹⁰≡3¹⁰ mod 5

Now we can use the laws of exponents to make this a bit easier:

3¹⁰≡(3²)⁵≡9⁵≡4⁵ mod 5

Ok, so there are 2 ways to continue this problem from here, the normal way, and the easy way. We will start with the former:

Normal

To start, we rewrite 4⁵ as 4⁴*4 to make the prior easier to simplify. Now, we do something similar to the first part of the solution to get:

4⁴*4≡(4²)²*4≡16²*4≡1²*4≡4 mod 5

Easy

To start, we do something very very clever. Since 5≡0 mod 5, subtracting 5 from 4 will not affect its value mod 5. So, we can do this:

4⁵≡(-1)⁵≡-1≡4 mod 5

Challenge!

I couldn’t figure this one out so do it for yourself lol This is left as an exercise for the reader. Feel free to comment your solution!

Conclusion

This blog is mostly exercises because modular arithmetic is understood more by doing than by reading! Anyway, next time we will prove the theorem we looked at in this blog, explore the analogs of inverses in modular arithmetic, and propose a new theorem!

Modular Arithmetic: Part 3 (Proving stuff)

Next Blog!