Modulo division

There are four well-known basic arithmetic operations: addition, subtraction, multiplication, and division. The last one is probably the most confusing for most people. In this lesson, we'll refresh your knowledge about division and also talk about its "modification" for positive numbers – modulo division.

Basic division and division with remainder

Let's look at the two examples below and try to explain the difference between them:

$$\underbrace{6}_{\text{dividend}} ~/~ \underbrace{2}_{\text{divisor}} = \underbrace{3}_{\text{quotient}} ~~~~~~~~~~ \text{v}\bigg|\text{s} ~~~~~~~~~~ \underbrace{7}_{\text{dividend}} ~/~ \underbrace{2}_{\text{divisor}} = \underbrace{3.5}_{\text{quotient}}$$

Attentive readers may notice that in the left equation above the result of the division is an integer when in the right one it is not a natural number. That happens because $6$ is a multiple of $2$, while $7$ is not. Such examples are called the non-integer division (in programming languages, it is usually known as float division), despite the result could be either integer or real. At an elementary level, the division result (speaking about natural numbers) is the number of times one number is contained within another one. In the previous example, we can see that number six contains number two exactly three times. The fractional part in the second case occurs because number $7$ could not be represented as an exact sum of twos:

$$6 = \underbrace{2+2+2}_{\text{3 times}} ~~~~~~~~~~ \text{v}\bigg|\text{s} ~~~~~~~~~~ 7 = \underbrace{2+2+2}_{\text{3 times}} + 1$$

$\text{or}$

$$~~~~~~ ~~~~~~~~~~~~~~~\underbrace{6}_{\text{dividend}} = \underbrace{3}_{\text{quotient}} \times \underbrace{2}_{\text{divisor}} + ~0 ~~~~~~~~~~ \text{v}\bigg|\text{s} ~~~~~~~~~~\underbrace{7}_{\text{dividend}} = \underbrace{3}_{\text{integer part of division}} \times \underbrace{2}_{\text{divisor}} + \underbrace{1}_{\text{remainder}}$$

The last representation of number $7$ illustrates that number $2$ is fully contained in it three times. The last summand is called the remainder. It illustrates what remains if the maximum possible multiple of the divisor would be subtracted from the original dividend. In case when the dividend is a multiple of the divisor (the quotient is integer), the remainder equals $0$. The remainder is always a non-negative integer, which is strictly less than the divisor.

Two operators which return an integer part of the division and its remainder are $\operatorname{div}$ and $\bmod$ respectively. Let's demonstrate how they work using an example with $7$:

$6\operatorname{div}2 = 3 ~~~~~~~~~~ \text{v}\bigg|\text{s} ~~~~~~~~~~ 7\operatorname{div}2 = 3$

$6\mod2 = 0 ~~~~~~~~~~ \text{v}\bigg|\text{s} ~~~~~~~~~~ 7\mod2 = 1$

Note: $\operatorname{div}$ and $\bmod$ operators are identical to the integer part of quotient and remainder relatively only for positive operands. If one of the operands is negative, $\operatorname{div}$ and $\bmod$ operators work in another way. This is beyond the scope of this topic, but interested readers can find more information by themselves. That is why we will work with positive numbers only.

Modulo division

So let's go into details of how the $\bmod$ operator works.

Assume that we have a number $x=n⋅y+z$, and $0 \leq z < y$. Then

$x\mod y=z$

(read as "x modulo y is equal to z")

In case when $x < y$:

$x\mod y=x$

With the assistance of a $\bmod$ operator, we could check whether one number is divisible by another:

$x$ is divisible by $y$ if and only if $x\mod y = 0$

i.e. x modulo y is equal to 0.

In the majority of programming languages the $\bmod$ operator is written as %, i.e. $x\mod y$ would be written as $x$ % $y$.

Examples

Now let's consider several cases to grasp what we have learned.

1. Even or not

For instance, you have a task to check if the number $x$ is even or not. It is extremely simple using the $\bmod$ operator. You know that a number is even if it is divisible by $2$. So, a given number $x$ is even if and only if $x$ modulo $2$ equals $0$, i.e.:

$x\mod2=0$

And this means that in your code you just need to check if the condition $x$ % $2$ == $0$ is met.

2. What time is it now?

As you know, in the world there are two widespread time conventions: $12$-hour clock and $24$-hour clock. Imagine that you have a friend who uses the $24$-hour clock and you ask him what time is it now in his city. He answered you, but, unfortunately, you live according to the $12$-hour one and don't understand what time is there exactly. However, this problem could be solved with the program code and the assistance of the $\bmod$ operator.

Assume that your friend said that it is $16$ o'clock at the moment. How to transfer it to the $12$-hour clock? No problem! Just think, what is a $24$-hour clock: people who use it just consider the full day as two full turns of the clock. Same as you, but instead of using a.m. or p.m. they numerate times continuously from $00:00$ to $23:59$. And the secret of conversion is taking time in $24$-hour format modulo $12$.

Your friend said that it was $16$ o'clock at the moment. Let's convert it to $12$-hour format:

$16\mod12=4$ because $16 = 1\cdot12 + 4$

And since $16\operatorname{div}12=1$, $16$ o'clock is equal to $4$ p.m.

Is it useful?

The functionality of the mod operator is very simple when you understand it. However, if it is the first time you faced it, some troubles could arise. And the reasonable question is "Is it really useful?". The answer is "Absolutely, yes!".

One of the most significant examples of usage of the mod operator is cryptography. In this area, programmers need to have a function, which is difficult to calculate the original value from, knowing its result. For instance, hackers have known that result of $x$ modulo $25$ is equal to $3$. And they would like to know what is $x$. It is a very hard task, because any number, that looks like $x=n\cdot25+3$, where $n$ is an arbitrary natural number, gives you $x\mod25=3$. There are millions of possible values of $x$. Sure, encryption algorithms are much more complicated than just taking the remainder from the division. But the idea of using it is very important.

It is also used when you need to operate with extremely big numbers and your resources are restricted. Applying mathematical basic operators ($+$, $-$, $\times$, $\div$) not to the big number itself, but to its remainder makes your computation thousands of times easier and allows you to make conclusions faster. It is not possible in every case, but sometimes it helps a lot.