Finding Gemstones: on the quest for mathematical beauty and truth
< Previous Post Next Post >

Days of the week and modular arithmetic

``I hardly ever use all the math I’ve learned these days - I’m thrilled if I ever get to compute so much as a derivative. Trigonometry is about the extent of what I need. I wish I encountered more math in what I do.”

I heard this while running with the Berkeley Running Club this week, jogging alongside one of the runners who works as an engineer. As a mathematician, I was quite struck by his statement.

It reminded me that the American educational system naturally leads one to conclude that math is some sort of linear process: first you have to learn your arithmetic and memorize your multiplication tables, then you learn algebra and how to recite the quadratic formula off the top of your head, and later you memorize a bunch of trig identities and learn triangle rules like Side Angle Side. Finally you’re put in precalculus to prepare you for the Holy Grail - Calculus - which only the really smart high school kids and the science-y college kids learn.

And there’s nothing beyond Calculus, right? Unless you’re some kind of crazy math genius.

But as every mathematician knows, nothing can be further from the truth. There are so many simple concepts in mathematics that just about anyone can learn, that are far more useful in everyday life than algebra or trigonometry, and that, sadly, are not taught as part of this linear march towards Calculus. One such concept is modular arithmetic!

Days of the week and remainders

Suppose you want to know what day of the week it will be 100 days from today. How would you figure this out? You could look at your calendar and count the days one by one, but that would take a while. A slightly better approach is to use the number of days in each month (``30 days has September…’’) to figure out what the date will be 100 days from today, and then look at your calendar to find that date. But this is also rather cumbersome.

As a better approach, we know that every 7 days, we will be back to the same day of the week. So if you start on a Thursday, after 7 days it will also be Thursday, and after 14 days it will still be Thursday, and so on. The smallest multiple of 7 less than 100 is 98, so 98 days from today, it will be a Thursday. (Yes, I am writing this post on a Thursday.) Therefore, 100 days from today it will be a Saturday.

What we’re really doing here is computing the remainder when 100 is divided by 7. The quotient is 14, and 7 times 14 is 98, so the remainder is 2. So the day of the week it will be 100 days from today is the same as the day of the week it will be 2 days from today, namely Saturday. This is the basic concept of modular arithmetic, the art of computing remainders.

The basics

Let’s set up some convenient notation. We’ll write ``$a\bmod b$’’ to denote the remainder when $a$ is divided by $b$. Some examples: \[100\bmod 7=2\] \[26\bmod 5=1\] \[4\bmod 9=4\] And so on.

We’ll also call $b$ the modulus - in the days of the week problem the modulus was $7$ - and when we’re taking something mod $b$, we sometimes say we’re ``working mod $b$’’ or ``modulo $b$’’. Furthermore, when working mod $b$, it sometimes becomes cumbersome to keep writing ``$\bmod b$’’ in our computations, so we’ll also just write ``$a\equiv c$’’ when $a$ and $c$ have the same remainder mod $b$. For instance, if we are working mod $7$, we have $100\equiv 2$ and $12\equiv 19\equiv 5$.

Now, there are three main ``modular arithmetic rules’’ that help us compute remainders quickly:

  1. Subtracting or adding multiples of $b$ to a number doesn’t change the remainder when dividing by $b$.
  2. When computing sums mod $b$, we can reduce each of the summands mod $b$ first before adding and taking the remainder. Formally, when working mod $b$, \[a+c\equiv a\bmod b + c\bmod b\]
  3. When computing products mod $b$, we can also take the factors mod $b$ before multiplying: \[a\cdot c \equiv (a \bmod b) \cdot (c\bmod b)\]

The first fact makes sense: for instance, if we’re working mod $7$, the numbers $9$ and $16$ have the same remainder because they differ by a multiple of $7$. Can you see why the other two are true? (See below for proofs.)

Using modular arithmetic: Factor first!

Let’s try applying the third rule above to our days of the week problem. We can factor $100$ as $10\cdot 10$, and the third rule says that we can reduce the $10$’s mod $7$ without changing the remainder of the product. So, working mod $7$, \[10\cdot 10\equiv 3\cdot 3=9,\] and $9\bmod 7=2$. See how easy? No long division or 98’s involved.

Okay, you might say, but it’s not that hard to divide $100$ by $7$. Well, what if I asked you what day of the week it will be $1000$ days from now? Now you can instantly figure out that it will be a Wednesday, because, working mod $7$, we have \[\begin{eqnarray*} 1000&=&10\cdot 10\cdot 10\\ &\equiv& 3\cdot 3\cdot 3 \\ &\equiv& 9\cdot 3 \\ &\equiv& 2\cdot 3 \\ &\equiv& 6 \end{eqnarray*}\] and so it’s the same as going $6$ days forward from Thursday, which lands you at Wednesday. Voila!

Breaking into sums

That’s all fine and dandy for powers of $10$, but what if the number doesn’t factor so nicely? For instance, there are $365$ days in a (non-leap) year. What if we wanted to know what day of the week it will be exactly one year from today?

Rather than trying to factor $365$ in some nice way, let’s break it up as a sum first, and simplify everything modulo $7$ as we go. \[\begin{eqnarray*} 365&=&300+60+5 \\ &\equiv& 3\cdot 10\cdot 10 + 6\cdot 10 + 5 \\ &\equiv& 3\cdot 3\cdot 3 + 6\cdot 3 + 5 \\ &\equiv& 6+18+5 \\ &\equiv& 29 \\ &\equiv& 1 \end{eqnarray*}\] Therefore, exactly one year from today, it will be a Friday.

Summing up…

Notice that modular arithmetic comes up in other natural scenarios too. For instance, clocks work on a 12-hour cycle. If we want to know what hour it will be $400$ hours from now, we can work mod $12$ and find out and find that $400$ has a remainder of $4$, so we can simply add $4$ hours to the current hour instead.

As another application, modular arithmetic can be used as a quick check for catching your arithmetic mistakes. Looking at numbers mod $10$ is very useful. Notice that any number mod $10$ is just its units digit. So, if you’re multiplying $172$ by $288$, you know that the answer will end in a $6$, because the product of the units digits of the two numbers is \[2\cdot 8=16\equiv 6\] mod $10$. So if your answer didn’t end in a $6$, you know you must have hit the wrong button on your calculator when entering the numbers.

As you can see, modular arithmetic is an incredibly useful tool. I find myself doing quick mental calculations over some modulus all the time, and not just when I’m working on abstract mathematics. Hopefully you will find it useful as well. For now, I’ll leave you with this fun modular arithmetic problem: What day of the week will it be $2^{100}$ days from today?


Proofs:

To see why the second fact is true, say $a$ has a remainder of $r$ when divided by $b$ and $c$ has a remainder of $s$. Then $a=bq+r$ and $c=bt+s$ for some integers $q$ and $t$, and so \[a+c=bq+bt+r+s,\] which has the same remainder as $r+s$ since we can subtract multiples of $b$ without changing the remainder.

The third rule is similar: writing $a$ and $c$ as above, we now have \[a\cdot c=(bq+r)\cdot(bt+s)=b^2qt+b(qs+rt)+rs,\] and again taking away the multiples of $b$ we are left with $rs$.