1Around the clock

$23+2$ is not always $25$. Think of the 24‐hour clock. When it’s 23:00, then two hours later, it will be 1:00, not 25:00. This is because the clock only counts hours from $0$ to $23$, and after that, it starts over from $0$.

This is exactly the idea of modular arithmetic. The term sounds fancy, but it really works just like a clock, except that there is no reason for a mathematician to restrict attention to 24‐hour clocks; instead, modular arithmetic talks about $m$‐hour clocks, where $m$ can be any positive integer. For example, a 5‐hour clock counts the hours as follows:

When a 24‐hour clock is at hour 0, we know that 24 (or 48, or 72) hours later, it’s again at 0. And 36 hours later, it’s at 12, and 25 hours later, it’s at 1.

When an $m$‐hour clock is at hour $0$, where is it $n$ hours later? For this, we introduce the notation

pronounced as “$n$ modulo $m$”. We always assume that $n$ and $m$ are integers, and that $m>0$.

As we have previously discussed, $24\bmod 24 = 0$, and also $48\bmod 24=0$ and $72\bmod 24=0$. Furthermore, $36\bmod 24=12$ and $25\bmod 24=1$.

In general, the $n \bmod m$ values tell us exactly how an $m$‐hour clock counts. To illustrate this, we come back to the 5‐hour clock:

2Computing modulo $m$

How can we compute $n\bmod m$, without simulating the passing of $n$ hours on an $m$‐hour clock? For example, what is $753\bmod 24$? This is asking where a 24‐hour clock is after $753$ hours. Well, as $753$ hours are exactly $753/24=31.375$ days, we know that $753$ hours are $31$ full days (equal to $31\cdot 24=744$ hours), plus $9$ extra hours (the difference between $753$ and $744$). Since the clock is at $0$ after each full day, it is therefore at $9$ after the $753$ hours. So,

Here is the general recipe for computing $n\bmod m$:

1. Compute how many full “$m$‐hour days” are passing within $n$ hours, by taking $n/m$ and rounding down. The mathematical symbol for this is $\lfloor n/m\rfloor$.

2. Multiply the result with $m$ to get the hours passing in these full days. The result is $m \cdot \lfloor n/m\rfloor$, and after this many hours, the clock is again at $0$.

3. We still have $n-m \cdot \lfloor n/m\rfloor$ extra hours to go, and this is also where the clock is after the total of $n$ hours.

So the formula is

Recall the rule “multiplication and division first, then addition and subtraction.” We have also (usual practice) omitted the multiplication symbol $\cdot$ between $m$ and $\lfloor n/m\rfloor$. Also note that we need $m>0$: a 0‐hour‐clock makes no sense, and you cannot compute $n/m$ when $m=0$. The number $n$ may be $0$, though.

While we’re at it: there is no reason to exclude negative values of $n$. We can also ask where the clock was some hours ago. For example, $(-6)\bmod 24= 18$, because when the clock is now at $0$, then $6$ hours ago, it was at $18$. The formula still works. If we compute $-6/24=-0.25$ and round down, we get $-1$. Multiplying this with $24$ gives $-24$. And finally, the extra hours still to go are $-6-(-24)=-6+24=18$.

We can also think of it like this: $6$ hours ago, $-1$ full day and $18$ extra hours have passed.

Just to get some more practice...

3Division with remainder

You may have encountered modular arithmetic back in school, in the context of division with remainder. For example, 16 divided by 5 is 3, with a remainder of 1. By this we mean that you can “fit" the number 5 three times into 16, but doing this, you only reach 15, so you have a remainder of 1. In the clock metaphor, a 5‐hour‐clock makes 3 full turns within 16 hours, after which 15 hours have passed. So after 16 hours, the clock is at 1. In formulas, $16\bmod 5=1$. The result of the division with remainder also has a name, we call it $16 \mathop {\textrm {div}}5$, and it has the value 3. We also know how to compute $n \mathop {\textrm {div}}m$ for arbitrary integers $n$ and $m>0$: take $n/m$ and round down. So the following holds:

Our previous formula for computing $n\bmod m$ was With the $\mathop {\textrm {div}}$ notation, it becomes and we can again rewrite this as This is known as the div‐mod identity.