Definition: Modular Arithmetic

Modular arithmetic gives us a very simple and straightforward—but also non-trivial—example of a group, and since we’ve only covered it explicitly in the solutions to lesson 22, we should devote a little time to it here.

Let’s begin with an example. Consider the set $\{0, 1, 2, 3, 4, 5\}$ , which has 6 integers in it. We can then define addition modulo 6 as follows. Take any two elements in this set and add them together normally. If their sum is less than 6, leave it alone (so that, for example, $2+3=5$ like usual), and if their sum is greater than or equal to 6, subtract 6 from it and then leave it alone (so that, for example, $5+3=8=2$ and we say that “five plus three equals two modulo six”). Some more examples of addition in this somewhat whacky group would be $4+2=0$ , $5+4=3$ and $2+2=4$ , all modulo 6.

One practical example of this kind of group is the type of addition we do whenever we tell time. Namely, telling time is nothing but doing addition modulo 12 or 24, depending on the country in which you’re reading this. For example, if you’re in an am-pm country and it’s 11 o’clock right now, and someone asks to meet you in 2 hours, you know that you need to check your schedule for 1 o’clock and not for 13 o’clock (since in an am-pm country the latter does not exist). Similarly, addition modulo 6 or 14 or 75 is nothing but “cycling around a clock” with 6 or 14 or 75 hours on it, respectively. This realization lets us define modular arithmetic more generally.

Definition: Let $\mathbb{Z}_N$ be the set $\{0, 1, 2, 3, ..., N-1\}$ (so that, for example, $\mathbb{Z}_6=\{0, 1, 2, 3,4, 5\}$ and $\mathbb{Z}_{25}=\{0, 1, 2, 3, ..., 22, 23, 24\}$ ). Then addition modulo N is the addition within this set such that a) if the sum of any two numbers in the set is less than $N$ we leave the sum unchanged and b) if the sum of any two numbers is greater than or equal to $N$ we subtract $N$ from the sum and then leave it unchanged.\\

The first and most important thing we’ll note about this definition is that addition modulo $N$ always turns $\mathbb{Z}_N$ into a group with the abstract group product being, of course, addition modulo $N$ and with the identity being $0$ . Understanding the inverses in this group is easy once we’ve seen a few examples, so let’s do that now.

In $\mathbb{Z}_{25}$ we have that, for example, $20+15=10$ and $17+12=4$ . The inverse of, say, 23, is 2, since $23+2=0$ modulo 25. However, in $\mathbb{Z}_{30}$ , we have that $20+15=5$ and $17+12=29$ , and now the inverse of 23 is 7 since $23+7=0$ modulo 30.

The notion of “something modulo something else” is in fact much more general than this. In fact, we can take any positive whole number $N$ and ask about “any integer modulo $N$ ” as follows. Let’s take the positive whole number 6 and the integer 85. We say that 85 is 1 modulo 6 because $85=14\times 6+1$ . In other words, what we do is take the integer that we’re asking about and “multiply up” the positive whole number that we’ve chosen as far as we can without “overshooting” the integer itself. Namely, in the above example, $15\times 6=90$ so that if we “multiplied up” 6 one more time, we’d “overshoot” the integer that we were interested in. Additionally, $13\times 6=78$ , so we could “multiply up” one more time without overshooting our integer. This is why stick with $14\times 6=84$ , which is as close as we can get while still staying less than 85, our integer of interest. Once we’ve done this, we simply take the remainder, i.e. what’s left, which in this case is 1. By definition of us not “overshooting” our intended integer, this remainder will always be non-negative and by definition of us getting “as close as we can get”, this remainder will always be less than 6. Note that if our integer if interest is perfectly divisible by 6 (e.g. 30) then that integer will be 0 modulo 6.

In this way we can calculate any integer modulo 6, and we find that, for example, $90=0$ modulo 6, $104=2$ modulo 6, and $17=5$ modulo 6. We do, however, need to be a little more careful when our integer of interest is negative. The process is the exact same, only slightly more confusing, because we need to recall what it means to be “less than” a negative number, i.e., “more negative than” a negative number. For example, $-1=5$ modulo 6 because the largest multiple of 6 which is less than $-1$ is $-6$ (because zero is greater than $-1$ ). Similarly, $-14=4$ modulo 6 because the greatest multiple of 6 that is still less than $-14$ is $-18$ , and the non-negative remainder is then 4. We note that while this may be confusing (or it may not be), it is exactly what we would expect when we try “continuing the pattern” of “modulo” from the positive integers. Namely, 8 modulo 6 is 2, 7 modulo 6 is 1, 6 modulo 6 is 0, 5 modulo 6 is 5, 4 modulo 6 is 4, 3 mod 6 is 3, 2 mod 6 is 2, 1 mod 6 is 1, 0 mod 6 is 0, -1 mod 6 is 5, -2 mod 6 is 4, and so on, so that we get the more enlightening chart (with the integer on the left and its value modulo 6 on the right)

$\vdots$

$8\rightarrow 2$

$7\rightarrow 1$

$6\rightarrow 0$

$5\rightarrow 5$

$4\rightarrow 4$

$3\rightarrow 3$

$2\rightarrow 2$

$1\rightarrow 1$

$0\rightarrow 0$

$-1\rightarrow 5$

$-2\rightarrow 4$

$\vdots$

By examining this list we see that there is a natural pattern even when we go into the negative integers, which is in line with the fact that a clock (with any given number of hours on it) just goes around and around over and over again (in the above list, this manifested by the fact that the pattern is 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, …).

We can then add any numbers and take their value “modulo 6”, and are no longer limited to the numbers 0, 1, 2, 3, 4, and 5 as we were in the group $\mathbb{Z}_6$ . In fact, we can simply view the group $\mathbb{Z}_6$ as addition modulo 6 restricted to the elements in the set $\{0,1,2,3,4,5\}$ . This restricted set of numbers then turns into a group, as previously discussed.

Finally, it should be clear how to extend modular arithmetic to being “modulo any particular number,” i.e., modulo $N$ for any $N$ . For example, 85 modulo 6 is 1, as we discussed, and modulo 10 it’s 5, and modulo 30 it’s 25. The same exact logic applies as for “modulo 6”, but now with 6 replaced with any positive whole number. We’ll skip these details here, as modular arithmetic will come up a lot in the lessons, but hopefully this gives a sufficiently self-contained introduction to the subject so that we can use these ideas elsewhere.

Back to Glossary

Back to Lessons