Modular Arithmetic

Question: If it's 9:00 PM today, how many hours until it's 5:00 PM tomorrow?

Counting with Clocks

There are two ways to find the answer. Actually, there are lots of ways to find the answer but two main 'categories' or 'approaches'.

1. Start at 9:00PM and count forwards in time until you get to 5:00PM the next day

   9:00 --> 5:00: (12 hrs from 9PM to 9AM) + (3 hrs from 9AM to 12PM) + (5 hrs from 12PM to 5PM) = 20 hours

2. Start at 9:00PM and count backwards to 5:00PM, then subtract whatever that is from 24

   5:00 --9:00: 24 - (9-5) = 24 - 4 = 20 hours

This is an example of modular arithmetic, also know as "clock math". Though scarcely taught nowadays modular arithmetic is fundamental to our modern world. From more efficient computer algorithms, to encryption of financial data, and even music, clock math creeps up all over. And yet so few know what it is, or that it even exists (a common theme among math and the public). So what is it?

It is the mathematics of remainders. 4/6 equals 0 with 4 left over. 5/6 is 0 with remainders of 5. How about 6/6? The answer is of course 1 with remainder 0. Now, what happens if we only focus on the remainder and forget about the main part of the answer? What's the remainder of 10/6? 4. What about 12/6? It's 0. In modular arithmetic we say 10 and 4 are congruent modulo 6 . We write this as

(10 mod 6) ≡ (4 mod 6) = 4, and (12 mod 6) ≡ (6 mod 6) = 0

Note the ≡ is not an = sign. It stands for "is congruent to" not "is equal to". This is to distinguish between things being explicitly equal, and things being equal mod N for some N. And if the "mod" in there is throwing you off because it seems like weird notation (because it kinda is), just think of it as \, a modified division symbol.

An Example: modulo 4

For a concrete example, let's pick 4 as our number to work with. That is, for the moment, we'll do everything mod 4. And because it's annoying to keep writing "remainder" I'll use the shorthand 'r'. So 9 / 4 = 2r1, or 2 with remainder 1.

If we play around with X mod 4, plugging in different numbers for X, we see a pattern start to emerge:

0 mod 4 = 0r0

1 mod 4 = 0r1

2 mod 4 = 0r2

3 mod 4 = 0r3

4 mod 4 = 1r0

5 mod 4 = 1r1

6 mod 4 = 1r2

7 mod 4 = 1r3

8 mod 4 = 2r0

9 mod 4 = 2r1

Remember, with modular arithmetic, all we care about is remainders. Can you guess what 10 mod 4 would be based on the pattern? It's 2.

Because we're working with numbers mod 4, we will only ever have four possible answers to any problem (assuming we stick to whole numbers, which we will). Why? Because there are only four possible remainders when you divide a (whole) number by 4. Namely, {0, 1, 2, 3}. And this is exactly why the cyclic pattern you see above happens! In the "mod 4 Universe" only four numbers exist. And as you keep cranking X up by one each time, the answers are doomed to repeat 0, 1, 2, 3 in a cycle forever. This "circular" nature is also partly why it's sometimes "clock math".

Beyond Counting

So far, we've only dealt with counting on a clock. But there's absolutely nothing stopping you from asking things like "How does addition or multiplication work in modular arithmetic?", "What about fractions and negative numbers?", and (a very important one) "What if N is a prime number?"

For the most part, math still behaves the same mod N. Old number properties like

(a + b) = (b + a)

almost still hold. But because numbers "wrap around" now, you have to reword it a little to reflect the circular nature of things.

And it's easy to extend modular arithmetic to negative numbers and fractions. Negatives behave the exact same way:

(+) x (+) = +

(+) x ( - ) = ( - ) x (+) = -

( - ) x ( - ) = +

Fractions are easy too. 3 mod 1.5 = 0 because 3 is a multiple of 1.5.