Most of us do modulo arithmetic more often than we think, especially if we look at an analog clock to tell time. For example, if I asked you to convert 14:00 from military time into “regular” time, you’d respond “2 pm” pretty quickly. But how did you do it?

You got that answer because you went all the way around the clock and then had 2 remaining. This is modulo addition — in this case $\bmod 12$.

Modulo addition is regular addition with an extra couple steps: dividing by your “base” $n$ (on a clock $n = 12$) and then grabbing the remainder. For integers $a$,$b$, and $n$,

\[a \equiv b \bmod n \Leftrightarrow b-a= k\cdot n \text{ for an integer } k \] This is read as "$a$ is equivalent to $b$ modulo $n$ if $b-a$ is an integer multiple of $n$". Another way to write this is \[a \equiv b \bmod n \Leftrightarrow b = k\cdot n + a \text{ for an integer } k\]In other words, if $b$ can be expressed as a multiple of $n$ plus some extra amount $a$, then $a$ is equivalent to $b$ modulo $n$.

Back to our clock example, obviously $2 \neq 14$, but $2\equiv 14 \bmod 12$ because

\[14 = 1\cdot 12 + 2\]Here, our $b$, which is 14, can be expressed as an integer multiple of $12$ ($k=1$), plus some extra $a=2$, so we say that $2\equiv 14 \bmod 12$.

The base $n$ matters. If I changed the $n$, equivalence may no longer hold. For instance, $2$ is not equivalent to $14 \bmod 5$ because the remainder when you divide 14 by 5 is 4. The study of these remainders gives us mathematical objects known as finite groups.If we look at dividing any number by 12, the remainder can only be the numbers 0 – 11. Why? Well if the remainder is 12, then it’s a multiple of 12. The remainder of any integer, no matter how big it is, when dividing by $n$ has to be somewhere in the set $\{0,1,2,\ldots, n-1\}{0,1,2,…,n−1}$.

Let’s look at a few with $n=12$. As an exercise, verify each of these on your own: \[\begin{align*}1\equiv 13 \bmod 12 &\text{ because } 13 = 1\cdot 12 + 1 \\ 0\equiv 24 \bmod 12 &\text{ because } 24 = 2\cdot 12 + 0\\ 11\equiv 35 \bmod 12 &\text{ because } 35 = 2\cdot 12 + 11\\ 0\equiv 48 \bmod 12 &\text{ because } 48 = 4\cdot 12 + 0 \\ 3\equiv 123 \bmod 12 &\text{ because } 123 = 10\cdot 12 + 3 \end{align*}\] The multiple $k$ is telling us how many times we’ve gone around the clock. So we’re always stuck on the clock, no matter how many times we go around, which means that the remainder can’t be any larger than 11, or we’ve started another cycle around the clock. The set $\{0,1,2,\ldots, n-1\}$forms an algebraic structure called a group when we pair the set with theA group is a set paired with an operation that has to have three certain properties. The operation doesn’t always have to be addition, or modulo addition, and the set doesn’t have to be integers. Operations can be addition, multiplication, function composition, or some weird one you define. But to pair an operation with a set, we have to check to make sure some rules are followed:

The operation has to fit the formal definition; we cannot use any old rule we want. An *operation* is defined mathematically as a rule that takes any two elements in a given set $A$ and returns a unique element that is still in $A$. This means that you can’t create a rule that lets you escape the set. If my set is integers, and my rule is division, then division is not an operation on the integers because the result of $3/4$ isn’t an integer. By trying to divide 3 by 4, we left the set of integers. The uniqueness requirement ensures our rule is *well-defined*. If my rule is to take two integers $a$ and $b$ and return the number whose square is the product $ab$, then $2\cdot 8 = 16$ could return either 4 or -4. That’s not well-defined. The rule doesn’t guarantee that a unique element is returned.

Assuming our operation really is an operation (and modulo addition on the integers is. If you don’t believe me, try to prove it for yourself.), then we can move on. We have the set (integers modulo $n$) and the operation (modulo addition). To meet the definition of a group, the set and operation must follow these three axioms:

- The operation is
*associative*, meaning that the grouping or order shouldn’t matter when I go to execute the operation on 3 elements. \[[(a+b) + c] \bmod n \equiv [a + (b+c)]\bmod n.\] - There is an
*identity element*in my set. There has to be some element in my set such that performing the operation (in this case, modulo $n$) on any other element in the set return that other element, and the order doesn’t matter. For our set of integers under modulo addition, the identity element is $0$. - Every element in the set has to have an
*inverse*. For every element in my group, there has to be another element such that performing the operation on the element and its proposed inverse in any order returns the identity element we talked ../about in (2).

We can examine groups via operation tables, which are a nice visual. Think of your multiplication tables from primary school. The elements are placed on the rows and columns, and the entries are the result of applying the operation to the two elements. The row entry goes first, then the column entry. For $\mathbb{Z}_{3}$, we know the elements are $\{0,1,2\}$, so the operation table looks like this:

\[\begin{array}{c|ccc} + & 0 & 1 & 2 \\ \hline 0 & 0 & 1 & 2 \\ 1 & 1 & 2 & 0 \\ 2 & 2 & 0 & 1 \end{array} \] Since all integers modulo 3 will leave a remainder of 0, 1, or 2, these are the only three numbers we need to consider. All integers will be equivalent to one of these three. So, reading the table, the first entry is row 1 + column 1 ($\bmod 3\!$), which is $$(0 + 0) \bmod 3 \equiv 0 \bmod 3 $$ Another one is the row 2 + column 3: $$(1 + 2) \bmod 3 = 3 \bmod 3 \equiv 0\bmod 3$$ Why? Well, after we add, we have to divide by 3 and take the remainder. As an exercise, make sure you can generate this table yourself. We know that modulo addition is an operation, so let's see if combining it with $\mathbb{Z}_{3}$ fits the definition of a group. This means we have to verify the three axioms, starting with the first:- There is more than one kind of addition. Modulo addition is very commonly used, with the typical example being clock reading. We also use it when we program computers (because machines operate in binary, which is actually $\mathbb{Z}_{2}$. It also shows up in many programming applications, like calendars (also use modulo addition) and the storage mapping function. (For a fantastic explanation of the "why I should care", check out I Programmer's article on SMF and the article on the mod function. )
- Group theory can simplify our lives by giving us fewer things to study. If I want to study the effect dividing by 3 has on numbers, I can just study $\mathbb{Z}_{3}$, because dividing by 3 can only have, well, 3 possible options: a remainder of 0, 1, or 2. Now I don't have to study all the integers in this situation to get the information I need.