If you have been programming for a while you probably already used the mod operator a lot. Same here. What I hadn’t done was to explore the world of modular arithmetic, and it turns out it’s quite interesting and useful (e.g., cryptography).

First of all let’s talk about the mod, or modulus, operator itself. The mod symbol on most programming languages is %. We are used to see it as the remainder of a division. So 5 % 3 = 2. That is, 5 divided by 3 is 1 (remember we are talking about integers) and the remainder is 2.

Splitting the Integers

Another way of interpreting the modulus is the number of groups we split the integers into. For example, if we use modulus 2, we basically split the integers into even numbers and odd numbers. That’s why we use % 2 to find whether a given number is even (in which case result is 0) or odd (in which case result is 1).

Under this perspective the modulus will also be the difference between two consecutive numbers in the same group (i.e., in case of modulus 2, it will be the difference between 2 and 4 and 5 and 7).

We could use modulus 3 (breaking the integers into 3 groups), modulus 4 and so on, but modulus 2 is particularly useful because of the concept of even and odd numbers, so we’ll stick with it.

Now let’s talk about what happens when we add and multiply even and odd numbers. The results look like this:

• Even + Even = Even
• Odd + Odd = Even
• Even + Odd = Odd
• Even * Even = Even
• Odd * Odd = Odd
• Even * Odd = Even

It turns out that modular arithmetic is quite useful to represent those results. But first let’s define a symbol to represent each group. Convention tends to use 0 to represent the even numbers and 1 to represent the odd ones. Now we can say that:

0 + 0 ≡ 0 mod 2

This means that if we add an even number with an even number the result will be even as well (as far as modulus 2 is concerned). The ≡ sign is called congruence, which can be interpreted as being part of a specific group (in the case of module 2 we can say that every integer is either congruent to 0 or to 1). So read the above expression as “zero plus zero is congruent to zero, modulo two.” All six results look like this:

• 0 + 0 ≡ 0 mod 2
• 1 + 1 ≡ 0 mod 2
• 0 + 1 ≡ 1 mod 2
• 0 * 0 ≡ 0 mod 2
• 1 * 1 ≡ 1 mod 2
• 0 * 1 ≡ 0 mod 2

Now the cool thing is that we can apply those rules to expressions with normal integers by reducing each number to its modulus 2 equivalent. For example:

12 * 3 + 15 + 7 * 3

is equal to

(0 * 1) + 1 + (1 * 1)

which is equal to

0 + 1 + 1

and finally

0 + 0 ≡ 0 mod 2

So the result of the initial expression would be an even number.

You can use the same technique with equations. For example:

2x + 5 = 12

By reducing the integers to their modulus 2 we have:

0 + 1 ≡ 0 mod 2

But an even number added to an odd number will always produce an odd number, so the above equation has no solution.

Congruence

Back to the congruence sign now. What does it mean? If we say that x and y are congruent modulo 2 it means that the result of x – y will be perfectly divisible by 2. We could write this as

x ≡ y mod 2

Another way of putting this is to say that x and y are congruent modulo 2 if there’s a k such that:

x – y = k * 2

In other words, the difference between x and y is a multiple of 2.

Remember when I said that congruence could also be interpreted as “being part of a group”? Here’s what I mean by that. Suppose we are working with module 7. The 7 possible results of taking any integer mod 7 are:

0 1 2 3 4 5 6

So those results could be seen as groups of integers we’ll be working with under modulo 7. Now what’s the result of 7 % 7? It’s 0. What about 8 % 7? It’s one. 9 % 7 is two, and so on. Basically we can keep writing more lines, and each integer will fall on a specific column (i.e., group):

 0   1   2   3   4   5   6
 7   8   9  10  11  12  13
14  15  16  17  18  19  20
...

Now you can see that 8 is congruent to 1 modulo 8, as 10 is congruent to 3 modulo 7 and so on.

Clock Arithmetic

Some people call modular arithmetic as “clock arithmetic”, because that is what we do when trying to figure out times. For instance, suppose it’s 3pm. What time will it be 47 hours from now?

You simply need to take 47 % 12, which is 11, and add it to 3pm, so within 47 hours it will be 2 am.

Further reading on the topic:

• Modular Arithmetic
• Introduction to Modular Arithmetic
• Cryptography and Modular Arithmetic