In this article we’ll go through what modular arithmetic is and how it is useful in programming. We’ll also go through various conventions in Modular Arithmetic and equivalence relations which simplify computing modulo.
What is Modular Arithmetic?
Modular arithmetic is a system in mathematics which deals with remainders of any number N when divided by a specific modulus M. In other words, when we say: “take modulo of a number N using modulus M”, it means to find the remainder/residue after dividing an number N with M.
For example, in order to find modulo of number 8 with respect to modulus 3:
- Number
8is first divided into parts of modulus:3 + 3 + 2 - Now all the full parts of Modulus (
3) are removed:2 - The remainder
2is the modulus of8with respect to3 - So
Modulo(8, 3) = (8 Mod 3) = 2. - Or simply, (8 Mod 3) is the remainder after dividing number
8with3
How is Modular Arithmetic useful in Programming?
Consider the below below example:
Let’s say there are 5 billing counters in a shopping mall. Let’s represent the counters in an array: [C0, C1, C2, C3, C4]
Customers are tagged with an auto incrementing id starting from 0. The first customer’s id is 0, the next customers id is 1 and so on. We need to map each customer to a single billing counter.
For the first 5 customers, mapping is easy. We can map customer with id 0 to C0, customer with id 1 to C1, customer with id 4 to billing counter C4. But which counter should we map to customer with id 5, 6 and so on?
This is where modulo is useful. In the above example, the total number of counters is 5. So if we take modulo of customer id with respect to 5, the result will always lie between 0 and 4. Eg: for a customer with id 201, the counter to map is (201 mod 5) = 1 so C1 is mapped to 201.
One low level use case of the above example is in hash maps or hash tables. There the size of hash table is determined (let’s say N). For storing any number in the has table, modulo of the number with respect to N is computed and the number is then stored in the corresponding slot.
TODO: Add 24 hour time example.
Congruence in Modular Arithmetic
For any positive number n, two numbers x and y are said to be congruent with respect to mod n, if their remainders when divided by n are the same.
For example, both number 8 and 14 leave a remainder of 2 when divided by 3. So number 8 is congruent to number 14 with respect to modulus 3. It is shortly expressed as: 8≡14 (mod 3).
This congruence relation is commonly used in competitive programming when the result might be really large and we need to return a small congruent number with respect to a given modulus (mostly 10e9 + 7)
Useful Properties/Identities of Modular Arithmetic
Addition
( (a mod m) + (b mod m) ) mod m ≡ (a + b) mod m
The above property is useful in finding the answer without accumulating numbers to the point of over flow. For example, let’s say the maximum number an integer can store is 1000. We need to add 900 and 800 and find modulo with respect to 13. One way to do it is by computing (900 + 800) mod 13. But 900+800 can’t be stored in an integer with maximum size as 1000. In this case, we can use the above congruence relation and compute the answer as (900 mod 13) + (800 mod 13). If these are chained a lot, we can perform another modulo after adding so the sum doesn’t exceed the maximum number that can be stored.
Subtraction
( (a mod m) - (b mod m) ) mod m ≡ (a - b) mod m
The above congruence relation is similar to the one we discussed for addition. There is one edge case though were the answer can be a negative value. For example (22 - 17) mod 3 is (22 mod 3) - (17 mod 3) is 1 - 2 is -1. For cases like this, we check if the final result is negative and if it is negative, we add the modulus to the result: -1 + 3 = 2 and so 2 is the answer.
Multiplication
( (a mod m) * (b mod m) ) mod m ≡ (a * b) mod m
The above identity is also widely used in finding the required answer without storing the exact true values after each step. So for example if we have to find modulo of a * b * c with respect to number n, if the product of a * b * c is very large that it can’t be stored easily, we can compute the answer by taking the modulo individually and then multiplying.
So (a * b * c) mod n = (a mod n) * (b mod n) * (c mod n)
If we wish to be extra cautious and prevent overflow after multiplication of two terms, we can do something this:
(a * b * c) mod n = ( (a mod n) * (b mod n) ) mod n * (c mod n)
TODO: Multiplicative Inverse.
Exponentiation
x^n mod m = (x mod m)^n mod m
The above identity follows from the multiplicative identity.
Other derived formulas
While computing rolling hash, we normally have the value of (a+b+c+d) mod n (Let’s name it as H). How do we find (b+c+d+e) mod n using H?
Instead of computing the mod by adding modulo of each of b, c, d & e, we can just subtract a from (a+b+c+d) mod n, take the mod, then add e to the result and finally take another modulo.
So (b+c+d+e) mod n is equal to ( (H - a) mod n + e mod n ) mod n, where H = (a+b+c+d) mod n.