Modulo Operator: Practical Uses in Arithmetics
Once you become familiar with the mathematical notion of modulo, you may start wondering why we even bother with such a strange operator. Is it of any use in real life? Yes, of course! In this article, you'll learn what the practical uses of modulo are. Let's start by recalling the basic theory.
What does modulo mean? Modulo operator definition
Modulo is a mathematical operation that means computing the remainder of a division of one integer by some other integer (integers are whole numbers). That is, if for two positive integers
n we have
a = b * n + r
a mod n is equal to
Alternatively, we can say that
a mod n = r if and only if
a − r is divisible by
n (without remainder).
5 mod 2 = 1, because
5 = 2*2 + 1. In fact, if
xis odd, then
x mod 2 = 1.
17 mod 3 = 2, because dividing 17 by 3 leaves the remainder of 2 (
17 = 5*3 + 2).
ais divisible by
a mod n = 0.
We use the modulo operation throughout pure mathematics, as well as in numerous applications, for instance in cryptography.
Can modulo result be negative?
Well, the answer depends on whom you ask 😉 A mathematician will answer "yes of course", because they'd be using the definition that
a mod n = r means that
a−r is divisible by
n. Under this definition, there are in fact infinitely many solutions to the modulo problem (they form what is known in math as an equivalency class) and every member (representant) of this class is a valid solution.
For example, we can say that
7 mod 3 is
1, because when we subtract
7, we get
6, which is divisible by
3. But we also have
7 mod 3 = −2 because
7−(−2) = 9 is divisible by
3 as well. If you think about it, you'll see that in fact every integer of the form
1 + 3k, where
k is an integer, is a solution to the
7 mod 3 problem.
On the other hand, programmers and computer scientists want just one solution and not infinitely many of them, so they will exclude negative modulo results. Most of them understand the modulo problem
a mod n as searching for the remainder of the Euclidean division
a = b * n + r, where
r is between
b−1, so the proper remainder as most of the world understands it.
Modular arithmetic and cryptography
Modular arithmetic occupies a special place in e.g. public-key cryptography, that is, when the sender and the receiver don't have to first share a secret key in order to start communicating secrete messages.
The most famous protocol is the RSA cipher, which was invented in the late 1970’s. It only requires the sender and the receiver to agree publicly on some numbers and then use modulo operations. As a result, they will share a secret number and can use it to communicate privately.
This method relies heavily on the fact that large numbers are extremely hard to factorize. An eavesdropper could quickly break the cipher if they would be able to factorize a public number shared by the sender and the receiver.
Modulo operations in programming languages
The modulus operation is available in various programming languages. The syntax differs, so it's best you consult the documentation of the language at hand to see how to use the modulo and compute
a mod n.
However, it may happen that the modulo operator in two languages will return different results! Namely, if exactly one of
n is negative, then there are two ways of calculating the modulo:
- Truncated division, where the remainder has the same sign as the dividend; and
- Floored division, where the remainder has the same sign as the divisor.
Some languages will use the truncated division, some others will go for the floored version, and some will offer two modulo functions, allowing you to choose which variant of computation you want to perform. So be careful and read the documentation!