In most introductory computer science mathematics courses at the university level, modular arithmetic is a necessity due to it’s prevalence in computer science theory. When I was in high school, I sought to get ahead and teach myself some modular arithmetic to help myself in my cryptography research. So, I’m going to try and give a brief explanation of guide to understanding very basic modular arithmetic.
The best way to start with modular arithmetic is by looking at an analog clock. Let’s take a look at the hours on it. We know that we have 1 o’clock, 2 o’clock, etc. but what happens when we get to 13? Do we have a 13 o’clock on the analog clock? No, we don’t. We just go back to 1 o’clock. This is called reducing. So, let’s continue increasing.
$$1 \rightarrow 1$$
$$2 \rightarrow 2$$
$$3 \rightarrow 3$$
$$\vdots$$
$$12 \rightarrow 12$$
$$13 \rightarrow 1$$
$$14 \rightarrow 2$$
$$15 \rightarrow 3$$
$$\vdots$$
$$21 \rightarrow 9$$
$$22 \rightarrow 10$$
$$23 \rightarrow 11$$
$$24 \rightarrow 12$$
Now, what happens when we get to 25. Does 25 go down to 13 or 1? Well 25 reduces twice. It first reduces down to 13, and we know that 13 reduces down to 1. So, 25 reduces down to 1.
$$25 \rightarrow 1$$
So, let’s start using some math notation. The clock is in base 12 since 12 is the largest value we can have. So, we will start writing our reductions in terms of $\mod 12$. So, we can re-write our table using the mathematical notation.
$$1 \equiv 1 \mod 12$$
$$\vdots$$
$$13 \equiv 1 \mod 13$$
$$\vdots$$
$$25 \equiv 1 \mod 13$$
Do you see any relationship between 1, 12, and 13? Well, in modular arithmetic, the relationship between them is
$$13 = 1 + 12 \times 1$$
So, $25 \mod 12$ would be
$$25 = 1 + 12 \times 2$$
So, since 1, 13, and 25 reduce down to 1, they are part of the same equivalence class mod 12.
This has been the very basics of modular arithmetic. I’ll try to add more posts on more in-depth mathematics once I create a proper teaching plan.