Modular Arithmetic

Motivation

Modular arithmetic is a familiar idea dressed in mathematical terminology. This is best illustrated by several examples from everyday use.

Days of the week

When we work out what day of the week something will happen on, we often (unconsciously) make mental calculations such as ‘two days after Tuesday is Thursday.’ We could write this in a pseudo-mathematical way as follows:

$$Tuesday + 2 = Thursday$$

When such a calculation takes us beyond the end of a particular week, we will make statements such as ‘three days after Friday is Monday.’ Although this is Monday of the following week, this does not cause us any problem since we treat all Mondays as the same for this purpose. So:

$$Friday + 3 = Monday$$

Similarly, we can make statements such as:

$$Thursday - 2 = Tuesday$$

We can also say:

$$Friday + 7 = Friday$$

We can restate this simple idea by now replacing the days of the week, starting with Monday, by the numbers 0 to 6 (so Monday is 0, Tuesday is 1, and Sunday is 6). It is now possible to write all our previous pseudo-mathematical equations as mathematical equations. In other words:

$$1+2 = 3$$

$$4+3 = 0$$

$$3-2 = 1$$

$$4+7 = 4$$

Computing the days of the week in this manner is an example of modulo 7 arithmetic (often abbreviated as mod 7). It’s like normal arithmetic, except we ‘wrap back around’ when we reach the number 7 by treating 7 as the beginning again (starting back at 0).

Months of the year

Another example of modular arithmetic is when we calculate the months of the year. When we try to work out what month of the year an event will occur, we often make calculations such as ‘three months after January is April’. We can write this as:

$$January + 3 = April$$

Similarly, ‘four months after October is February’ is:

$$October + 4 = February$$

By replacing January to December with the numbers 0 to 11, we can write these calculations as:

$$0+3 = 3$$

$$9+4 = 1$$

This is modulo 12 arithmetic. There are many other examples of this type of ‘unconscious’ use of modular arithmetic. For example, the 24-hour clock provides an example of modulo 24 arithmetic.

Modular numbers

We can perform modular arithmetic using any positive integer as the modulus, where a positive integer means a whole number bigger than 0 (a number such as 2, 18, 754, etc.). When working modulo $n$ (mod $n$), where $n$ is some positive integer, which we call the modulus, the only numbers we deal with are:

$$0,\; 1,\; 2,\; 3\;,\; ... \;,\; n - 1$$

So, instead of having numbers that go on forever, when working modulo $n$, we only have n different numbers to work with. For example, mod 6 arithmetic only uses the numbers 0, 1, 2, 3, 4, and 5, and mod 359 arithmetic only uses the numbers 0, 1, 2, 3, …, 355, 356, 357, 358. Using modular arithmetic, we will later see that we can add, subtract, and multiply numbers. So long as the answer is less than the modulus, these operations are just the same as if no modulus was used. For example, when working modulo 358, 57 + 101 = 158. However, we need to consider what happens when the answer takes us beyond the modulus value.

Adding multiples of the modulus

First, let’s consider what happens if we add two numbers using modulo $n$ and end up with $n$ itself. For example, when working modulo 7, what happens when we compute 3 + 4? We know 3 + 4 = 7, but in modulo 7 arithmetic, there is no number 7.

Recall the example based on days of the week. When working modulo 7, we see that asking ‘what is 3 + 4?’ in modulo 7 arithmetic is equivalent to asking ‘what day comes four days after Thursday?’ The answer is Monday, which is day 0, so:

$$3 + 4 = 0 \; mod \; 7$$

The ‘mod 7’ at the end of the line indicates that we are performing the calculation modulo 7. Unless it is clear from the context, it is important to include this indicator since the answer to ‘what is 3 + 4?’ depends very much on what modulus we are working with.

The important lesson is that when working modulo $n$, adding $n$ to a number will not change it. For the days of the week example, if we calculate seven days after Tuesday, it is Tuesday again:

$$2 + 7 = 2 \; mod \; 7$$

In fact, 14 days after Tuesday, it is Tuesday once again:

$$2 + 14 = 2 \; mod \; 7$$

Similarly, seven days before Tuesday is also Tuesday:

$$2 - 7 = 2 \; mod \; 7$$

So, in modulo $n$ arithmetic, the number n behaves just like 0 does for the numbers we normally use. This is an important principle of modular arithmetic.

One number modulo another

Consider two numbers $a$ and $n$, where $a$ and $n$ are both positive integers. Although $a$ is a positive integer, let’s suppose we want to know what value $a$ would take if we considered it a number modulo $n$. This question is often phrased as ‘what is the value of $a$ modulo $n$?’

It is important to recognize that there will be an answer to this question. This is because any number can be expressed uniquely modulo any other number. Since we have just seen that in modulo $n$ arithmetic, all multiples of $n$ are 0, the answer to our question is that $a$ will take the value that is the remainder when we divide $a$ by $n$.

To see a simple example, let $a$ = 6 and $n$ = 5. We know 5 is the same as 0 in modulo 5 arithmetic. Since 6 is just one more than 5, 6 will be the same as 1 in modulo 5 arithmetic. This is just another way of saying that when we divide 6 by 5, we get a remainder of 1. Thus, 6 is equal to 1 when 6 is considered a number modulo 5. In other words:

$$6 = 1 \; mod \; 5.$$

Similarly, let $a$ = 5417 and $n$ = 7. We can divide 5417 by 7 using traditional arithmetic to discover that:

$$5417 = (773 \times 7) + 6$$

Since we know 7 = 0 when working modulo 7, it follows that $(773 \times 7)$ will also be 0. Thus, 5,417 is equal to 6 when we work modulo 7, which we write as:

$$5417 = 6 \; mod \; 7$$

Returning to our analogy, if we ask, ‘what day of the week is it 5,417 days after Wednesday?’ we now know that in 5,417 days, it will be 6 days after Wednesday, so it will be Tuesday!

We will also need the following idea later. Suppose we know that a positive integer $a$ takes the value $r$ modulo $n$. In other words, we know that when we divide $a$ by $n$, we get the remainder $r$. This tells us that, for some number $k$ us it is possible to write $a$ as:

$$a = (k \times n) + r$$

We do not necessarily know what $k$ is, but there must be a $k$ for which this is true. Returning to our previous example, knowing that 5,417 takes the value 6 modulo 7 allows us to claim that:

$$5417 = (k \times 7) + 6$$

The claim given above is for some number $k$ (in fact, it is easy to work out, in this case, that $k$ = 773).

Terminology and notation

We have kept our terminology as simple as possible. However, other texts may explain modular arithmetic using slightly different language. For example, calculating one number modulo another is sometimes called modular reduction. Thus, we might say that 5,417 reduces to 6 modulo 7. Also, just to make sure it is recognized that a modular reduction has taken place, often the symbol ≡ is used instead of =. Thus, we would write 5417 ≡ 6 mod 7 rather than 5417 = 6 mod 7. This idea is often expressed by stating that 5,417 is congruent to 6 modulo 7.

Note: While 5,417 is congruent to 6 mod 7, it is also congruent to 13 mod 7 and to 20 mod 7. It is congruent to any multiple of 7 with 6 added. However, when asked ‘what number is congruent to 5,417 mod 7?’ there will only be one answer lying between 0 and 6. This is the default answer and usually the most useful one.

Negative modular numbers

We can also work with negative numbers in modular arithmetic. These behave in almost the same way. To start, we can regard any negative multiple of the modulus $n$ as equal to 0 modulo $n$. In other words, -7 and -14 are equal to 0 modulo 7. More generally, any negative integer can be uniquely expressed as a number modulo $n$. For example, let’s suppose that we wish to compute -17 mod 10. We divide -17 by 10 and take the remainder. When we do this, we need a positive remainder because our answer modulo 10 must be one of the numbers between 0 and 9. So, we see that:

$$-17 = (-2 \times 10) + 3$$

In other words:

$$-17 = 3 \; mod \; 10$$

Modular arithmetic operations

We’ll now consider computing basic arithmetic operations modulo $n$.

Addition, subtraction, and multiplication

The good news is that the basic arithmetic operations of addition, subtraction, and multiplication behave just as we would expect them to. In other words, we can add numbers, subtract them, or multiply them, just as we would do with ‘normal’ numbers. We just need to remember to reduce the answer modulo $n$. For example:

$$3 + 3 = 6 = 1 \; mod \; 5$$

$$5 + 4 = 9 = 2 \; mod \; 7$$

$$3 - 5 = -2 = 7 \; mod \; 9$$

$$4 \times 5 = 20 = 2 \; mod \; 18$$

$$3 \times 3 \times 3 = 27 = 3 \; mod \; 4$$

$$0 \times 6 = 0 \; mod \; 7$$

Importantly, the division is intentionally left out of this list because it does not work in the same way for normal numbers.

Modular reduction: before or after?

One issue worth clarifying when doing a calculation such as 15 + 20 mod 6 is whether we should reduce 15 and 20 modulo 6 before or after they have been added together. Fortunately, it does not matter since we will still get the same answer.

This is best seen by example:

1. Add then reduce: We first compute $15 + 20 = 35$ and then note $35 = 5 \; mod \; 6$. So $15 + 20 = 5 \; mod \; 6$.

2. Reduce then add: We first compute $15 = 3 \; mod \; 6$, and then $20 = 2 \; mod \; 6$. Now we add the answers, in other words: $15 + 20 = 3 + 2 = 5 \; mod \; 6$.