I’ve been meaning, for some time, to write a blog post on two’s complement arithmetic from a mathematician’s point of view. For such a blog post to make sense, it is important, first, to have an understanding of modular arithmetic. This post proves some of the important basics of modular arithmetic which are used in the two’s complement arithemetic post.

What is Modular Arithmetic

Modular arithmetic is just like regular arithmetic except with a maximum number. When you reach the maximum number instead of continuing to increase you go back to zero. For instance, if our maximum number is 10 then counting goes 8, 9, 0, 1, 2. The every day situation where this is most familiar is telling the time, if the time is 10pm and we want to know what the time will be 4 hours later we can count on by 4 hours and get to 2am. Modular arithmetic can be helpful in modelling situations where there are repeating regular patterns. In my time as a developer and researcher, I have come across several situation where it has been a very useful tool, particularly when working with repeating shapes (e.g., circles in geometry, or colour hexagons).

You may be thinking “I’ve been writing code for years and have never needed this,” and you may well be right, however, it is possible that you didn’t know about it and when it could have made life simpler. Regardless of whether you have needed it, the processor in your computer uses it all the time so it may be of some interest.

Getting into the Maths

To get into the maths, we first need a better definition of what modular arithmeic is. In the clock example, we expect to see that $14$ is the same as $2$ and $26$ is, again, the same. This is because in each case $2$ is the value left after we have gone round the clock a whole number of times. E.g., with $26$ we will go round the clock $2$ whole times and $2$ will be left over. This is the same as looking at the remainder after integer division. For example, $26 \div 12 = 2r2$, and $14 \div 12 = 1r2$, as the remainders are the same the numbers are considered the same modulo 12.

We now need to introduce the jargon mathematicians use to talk about modular arithmetic; there are two pieces of jargon, and confusingly they both use the same name, $mod$. The way to write that two sides of an equation are equivalent modulo a number is:

$$ a \equiv b\ (mod\ n)$$

$a$ is equivalent to $b$ modulo $n$, e.g., $15 \equiv 3\ (mod \ 12)$.

The second piece of jargon (which will not be used much in this blog post) is the $mod$ operator, this is the operator which finds the remainder on division e.g., $15\ mod\ 12 = 3$.

The Trick to Proofs in Modular Arithmetic

To do proofs in modular arithmetic we utilise the folling fact:

Given two integers $a$ and $n$ where $n > 0$, $a$ can be written in the form $a$ = $x \times n + r$ where $r < n$ for some calculable $x$

If this does not seem obvious, try it with some examples, e.g., if $a = 108$ and $n = 25$ we can write $104 = 4 \times 25 + 8$. Note that by this definition $r$ is the remainder used in our definition of equivalence in modular arithmetic and $x$ is the result $a \div n$. This leaves a method for expanding values in modular arithmetic. So given:

$$ a \equiv b\ (mod \ n)$$

We can expand $a$ and $b$ so that $a = x_1 \times n + r$ and $b = x_2 \times n + r$, then we can do normal arithmetic with $a$ and $b$ and see what happens. For example, we can do:

$$a - b = x_1 \times n + r - (x_2 \times n + r) = (x_1 - x_2)\cdot n$$

The $r$ value has disappeared (become $0$) and $(x_1 - x_2) \cdot n$ is obviously a multiple of $n$ (as $x_1$ and $x_2$ are integers) therefore $a - b \equiv 0\ (mod \ n)$

Addition

We could try adding a new number to each of $a$ and $b$, let us take a number $c = x_3 \times n + r_1$:

$$a + c = (x_1 + x_3) \cdot n + r + r_1$$

Note that $(x_1 + x_3) \cdot n + r + r_1 \equiv r + r_1 \ (mod \ n)$ as $(x_1 + x_3) \cdot n$ is a multiple of $n$. Also

$$b + c = (x_2 + x_3)\cdot n + r + r_1$$

Similarly, this is equivalent to $r + r_1$ so if we have two numbers that are equivalent to each other and add them to a third number the result will be equivalent (and vice versa):

$$a \equiv b\ (mod\ n) \Leftrightarrow a + c \equiv b + c\ (mod\ n)$$

Note, we proved this fairly informally and only in the forward direction, in the other direction we can just subtract $c$ from both sides, which is the same as adding $-c$, and we have already shown that adding a number to both sides will keep both sides equivalent.

Multiplication

As multiplication is just continued addition, it would be very surprising if it did not maintain equivalence, however, we will continue where we left off with addition and have a look at what happens if we multiply $a$ and $c$ instead:

$$a \times c = (n\cdot x_1 \cdot x_3 + x_1\cdot r_1 + x_3 \cdot r) \cdot n + r\cdot r_1$$

As the first term ($(n\cdot x_1 \cdot x_3 + x_1\cdot r_1 + x_3 \cdot r) \cdot n$) is a multiple of $n$, this is equivalent to $r\cdot r_1$ (this should be a familar argument by now). Similarly:

$$b \times c = (n\cdot x_2 \cdot x_3 + x_2\cdot r_1 + x_3 \cdot r) \cdot n + r\cdot r_1$$

By the same argument, this is equivalent to $r \cdot r_1$, therefore:

$$a \equiv b\ (mod\ n) \Rightarrow a \times c \equiv b \times c\ (mod\ n)$$

Unlike with addition, this does not work in the other direction, this is because we are working with integers and therefore cannot deal with division in the same way. Division is the undoing of multiplication and it may not be possible to undo the multiplication and get an integer, e.g., $5 \div 3 \ (mod\ 12)$ does not make sense, there is no whole number solution to this. On the other hand, in some cases there may be multiple ways of undoing the multiplication. On a clock, we could do $11 \times 3 = 33$, and $33 \equiv 9 \ (mod\ 12)$, but we can also do $3 \times 3 = 9$ (which is obvioulsy equivalent to $9$ modulo $12$), this causes a problem for division becasue if we do $9 \div 3$, we don’t know if we want $11$ or $3$ as the result, and both are entirely valid results modulo 12.

Shortcutting

As shown above, if we have two numbers that are equivalent we can add and multiply them by other values and the results will remain equivalent. This means, by choosing an equivalent value, we make the multiplication or addition easier:

$$(126 + 15) \times 23 \equiv (6 + 5) \times 3 \equiv 1 \times 3 \equiv 1 \ (mod\ 10)$$

By reducing each value to its simplest form modulo $n$, the calculation can be made considerably simpler.

Another example:

$$11 \times 7 \equiv -1 \times 7 \equiv -7 \equiv 5 \ (mod \ 12)$$

(Note that $-1 = 12 \times -1 + 11$ so is equivalent to $11$ similarly $-7 = 12 \times -1 + 5$ so is equivalent to $5$. This can be viewed as counting backward round the clock). This trick stopped us having to calculate $77\ mod\ 12$, the result will be $5$.

What Use is All of This.

Other than implementing clocks, the place where this is used all the time is for representing integers in computers. Your computer/phone will be using these results all of the time (more on this in the next post).

You can also prove some interesting results using this.

Summing Digits for Multiples of $9$

For example, it is common trick to check if a value is divisible by $9$ to add all the digits of the value and see if they are divisible by $9$. E.g., $27 = 2 + 7 = 9$ so 27 is divisible by 9. You may have wondered why this is, or if you’re like me wanted to see a proof of it. So here we go:

To see if a value $a$ is a multiple of $9$ we can do the following check:

$$a \equiv 0 \ (mod\ 9)$$

To go further than this we need to know a little about how we write numbers. The number 14,782 actually means:

$$1 \times 10^4 + 4 \times 10^3 + 7 \times 10^2 + 8 \times 10 + 2$$

For any parents of school children, you will probably be familiar with them ‘partitioning’ numbers in this manner.

Finally, we need to spot that $10^n \equiv 1 \ (mod\ 9)$. It is obvious that $10\ mod\ 9 = 1$ so $10 \equiv 1 \ (mod\ 9)$ now we can do $10 \times 10 \equiv 1 \times 1 \equiv 1 \ mod\ 9$. If we assume $10^n \equiv 1\ (mod\ 9)$ then by induction $10^{n + 1} \equiv 10^n \times 10 \equiv 1 \times 1 \equiv 1 (\ mod\ 9)$.

Going back to our number:

$$1 \times 10^4 + 4 \times 10^3 + 7 \times 10^2 + 8 \times 10 + 2 \equiv 1 \times 1 + 4 \times 1 + 7 \times 1 + 8 \times 1 + 2 \ (mod\ 9)$$

Giving:

$1 + 4 + 7 + 8 + 2 \equiv 22 \equiv 4 \ (mod\ 9)$

As this is not equivalent to $0$, the original number is not divisible by 9, but I can find the closest value that is by subtracting $4$ from the original number.

Therefore, the reason you can find multiples of 9 easily is because $10 \equiv 1\ (mod\ 9)$. Note that $10$ is also $1$ modulo 3, so exactly the same pattern also works for $3$ (if you add the digits in a number and they give a multiple of $3$ the number is divisible by $3$).

Finally, there is a very similar pattern for $11$. If we want to show a number is dvisible by $11$, we can take the first digit, subtract the second, add the third etc., and if they sum to a multiple of $11$ the number is divisible by $11$. For example, $121$, $1 - 2 + 1 = 0$, $0$ is a multiple of $11$ and, therefore, so is $121$.

Here $10 \equiv -1 \ (mod \ 11)$, this means that $10^2 \equiv (-1)^2 \equiv 1 \ (mod\ 11)$, then $10^3 \equiv -1$ and $10^4 \equiv 1$ etc. This pattern goes on indefinitely so $n\ mod\ 2 = 0 \Rightarrow 10^n \equiv 1 \ (mod\ 11)$ and $n\ mod\ 2 = 1 \Rightarrow 10^n \equiv -1 \ (mod \ 11)$. Applying this to our original number gives:

$$1 \times 10^4 + 4 \times 10^3 + 7 \times 10^2 + 8 \times 10 + 2 \equiv 1 \times 1 + 4 \times -1 + 7 \times 1 + 8 \times -1 + 2 \ (mod\ 11)$$

Giving:

$$1 - 4 + 7 - 8 + 2 \equiv -2 \ (mod\ 11)$$

This is not divisible by $11$, but the nearest number that is divisible can be found by adding $2$ to the original number.

Personally, I find these results fastinating. However, if, like me, you’re a programmer, you are much more likely to come across modular arithmetic in reapeating patterns. For example, creating a colour hexagon.

In the next post, I will discuss how modular arithmetic is used to approximate integer numbers in computers and why.