Like Clockwork: Modulo Addition and Finite Groups of Integers

Like Clockwork: Modulo Addition and Finite Groups of Integers

Modulo arithmetic always scared me in college. (Honestly, it’s still not something I can do as easily as integration or spotting pdfs hidden inside icky integrals.) Then when you add abstract algebra (or modern algebra as some call it) and group theory on top of it, the whole topic can become intimidating. Many books on algebra don’t slow down enough to really examine the examples they give, so I’m going dive in and explore some of these. Algebra is a powerful branch of mathematics, with ripple effects all throughout mathematics, engineering, experimental design, and computer science. It’s worth study and understanding, and the topics that scare us tend to lose their fangs after we get to know them a bit.

Addition on the clock

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?

I picked 2 o’clock because I think it should become a standard in America to break at 2 for tea.

 

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 \mod 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 remainder1. We write mathematically that for integers a,b, and n, that

a \equiv b \bmod n \Leftrightarrow b-a= k\cdot n \text{ for an integer } k

You read this as  a is equivalent to b modulo n if b-a is a multiple (integer multiple) of n. Another way to write it is to say that

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

That n matters. If I changed the n, that statement doesn’t hold true anymore. That is, 2  is not equivalent to 14 \mod 5 because the remainder when you divide 14 by 5 is 4. Next, let’s study the set of possible remainders when we divide an integer by a given n

The Finite Groups \mathbb{Z}_{n}

Since you’re super clever, I bet you’re already one step ahead. 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\}

Let’s look at a few with n=12. As an exercise, verify each of these on your own:

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

That 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 the operation modulo addition.

So what’s a group?

group is a set paired with an operation that has to have 3 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:

  • First, your operation has to fit the formal definition of an operation. An operation is defied mathematically as a rule that takes any two elements in a 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 it’s not an operation on that set because the result of 3/4 isn’t an integer. I escaped the set. The uniqueness requirement is what it means to be well-defined. If my rule is that I 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). Now, to meet the definition of a group, the set and operation must follow these three axioms

  1. The operation is associative. That is, the grouping or order shouldn’t matter when I go to execute the operation on 3 elements. That is, [(a+b) + c] \bmod n \equiv [a + (b+c)]\bmod n.
  2. There is an identity element in my set. In other words, 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. If you take some element and operate on it using the identity, or if you take the identity element and operate on it using that other element, you would always get that other element. 2
  3. Every element in the set has to have an inverse. This means that 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).3

 

We have a special way of writing the set of the integers modulo n: \mathbb{Z}_{n} = \{0,1,\ldots,n-1\}. We’ll do a specific example and verify that \mathbb{Z}_{3} under modulo addition is a group.

\mathbb{Z}_{3} and operation tables

We can examine groups via operation tables, which are a nice visual. Think of your multiplication tables when you were young. 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}{l|rrr}\color{purple}{+}&\color{purple}{0} &\color{purple}{1} & \color{purple}{2}\\\color{purple}{0} & 0 & 1 & 2\\\color{purple}{1} & 1 & 2 & 0\\\color{purple}{2} & 2 & 0 & 1\end{array}

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. It gives good practice, and if you can comfortably generate this, then you’re doing great!

Now, let’s verify that \mathbb{Z}_{3} under modulo addition is a group

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:

 

Axiom 1: Associativity:

We need to show the following to satisfy the first axiom:

[(a+b) + c] \bmod 3 \equiv [a + (b+c)]\bmod 3.

First, let’s take any three unspecified elements of \mathbb{Z}_{3}. Call the a, b, and c. We don’t specify these because we have to keep things general in order to show that it doesn’t matter which three elements we pick.4 We are going to start with [(a+b) + c]\bmod 3 and manipulate it to show that it’s equivalent to [a+(b+c)]\bmod 3. To differentiate between regular old addition and modulo addition (modulo 3 in this case), I am going to use the notation +_{3} when I mean addition modulo 3.

First, by the definition of modulo arithmetic,

[(a+b)+c]\bmod 3 = (a+b)\bmod 3 +_{3} c\bmod 3

The right hand side of the above is the same thing as using regular addition to add a, b, and c together first, then take that result modulo 3. 5 So we write that

\begin{aligned}[(a+b)+c]\bmod 3 &= (a+b)\bmod 3 +_{3} c\bmod 3\\&= (a+b+c)\bmod 3\end{aligned}

Look inside the parentheses. Now we’re back in the nice, safe world of regular addition, and we know we can group and add any ol’ way we want to inside those parentheses. So let’s do that. We know that

(a+b+c) = (a+b) + c = a + (b+c).

Grab that last equality.6 Then we can write

\begin{aligned}[(a+b)+c]\bmod 3 &= (a+b)\bmod 3 +_{3} c\bmod 3\\&= (a+b+c)\bmod 3\\&=[a+(b+c)]\bmod 3\end{aligned}

Hmm, now it looks like we can “descend” the same ladder we walked up to start with. If [(a+b)+c]\bmod 3 = (a+b)\bmod 3 +_{3} c\bmod 3, then it also holds that [a+(b+c)]\bmod 3 = a\bmod 3 +_{3} (b+c)\bmod 3.7 \begin{aligned}[(a+b)+c]\bmod 3 &= (a+b)\bmod 3 +_{3} c\bmod 3\\&= (a+b+c)\bmod 3\\&=[a+(b+c)]\bmod 3\\&= a \bmod 3 +_{3} (b+c) \bmod 3\end{aligned}

Last step. We are now basically done. Use the definition of modulo arithmetic one more time to finish.

\begin{aligned}[(a+b)+c]\bmod 3 &= (a+b)\bmod 3 +_{3} c\bmod 3\\&= (a+b+c)\bmod 3\\&=[a+(b+c)]\bmod 3\\&= a \bmod 3 +_{3} (b+c) \bmod 3\\&\equiv [a+(b+c)]\bmod 3\end{aligned}

 

Axiom 2: Existence of an identity 

This one is nice and easy here. We already did the work by calculating out that operation table. Which element when added to any other element returns the other element? Does the order matter? Use the multiplication table to verify that 0 is the identity element of \mathbb{Z}_{3}

 

Axiom 3: Every element has to have an inverse

We also did the setup for this one too. Look at each element (there are only 3). Each element needs to have a corresponding pair that you can modulo add to it to retrieve the identity element 0 \mod 3. Clearly, 08 is its own inverse.9 (0+0) \bmod 3 = 0\mod 3. Also,

(1+2)\bmod 3 \equiv (2+1) \bmod 3 \equiv 0 \bmod 3.

So 1 and 2 are inverses of each other. Therefore, every element has an inverse, and we’ve proven that \mathbb{Z}_{3} is a group under the operation modulo addition.

 

I read all the way down to here, so what should I take from this?

All the things we just did were to learn a couple things:

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

This article will be just the start of various explorations of group theory. Here I gave an introduction to a specific type of group, the integers modulo n, because it will turn out that the structure and behavior of these groups are actually the same as other groups that look much harder to study, like symmetries of regular shapes. For example, \mathbb{Z}_{3} has the same mathematical structure as all the lines of symmetry through an equilateral triangle.10. This has vast uses in chemistry and physics, studying the shapes of molecules.

Abstract algebra is a vastly useful subject, despite its reputation for living “in the clouds.” Since I myself need to deepen my understanding of this remarkable branch of mathematics, join me on the journey and stay tuned for more posts exploring notions in group theory. Perhaps as I become better friends with algebra, it will appear more useful and beautiful to you as well.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Footnotes

  1. A subtlety should be noted that b may not necessarily be the exact remainder. The congruence relation actually means that if you divide b and a by n, then you will get the same remainder. We’re going to keep the simple interpretation for the purpose of this post.
  2. Quick example, 0 is the identity element for integers under regular addition. If you add 0 to any integer, you get that integer back, and it doesn’t matter if you add an integer to 0, or 0 to that integer.
  3. With the integers under regular addition, the inverse element of an integer is the negative of that integer. The inverse of -1 is 1, and the inverse of 1 is -1. No matter which order you add them, you get 0, which is the identity element under regular addition.
  4. I know it’s possible to verify this by trying all combinations. The set is small enough to do this, but it’s a bad habit to get into. To learn to prove, you must learn to do this in general and not rely on “brute force” crutches.
  5. Try verifying this for yourself using the table above, just so you get comfortable with this. It’s true regardless of what you are modding out by, but playing with a few examples on your own is the best way to get it to sink in.
  6. Hint: because it looks an awful lot like what we’re trying to get to, just with modular arithmetic
  7. Again, think of the stuff in the parenthesis to be a new object. Rename it is you want, because you add that first anyway. You’re just reusing the definition of modulo arithmetic.
  8. I write 0, but remember that this is not really the number 0. It represents all things that are a multiple of 3. In these groups, each element is actually an object we represent lazily by a number, rather than the number as we usually think of number.
  9. Yes, this is totally possible. In fact, for finite groups with an odd number of elements, one element will have to be its own inverse.
  10. In mathematics, this is called an isomorphism
Comments are closed.