In this post, we are going to discuss Modular Arithmetics Operations and some problems based on it.
Modular Arithmetics is been used frequently in Competitive Programming and we will discuss every bit of it, so let’s start.
Given three integers a, b, m where m > 0, we say a and b are equivalent mod m, written a ≡ b (mod m), if (a − b) is a multiple of m.
For example, 23 ≡ 2(mod 7), here (23-2) is multiple of 7, in other words (23-2) % 7 = 0.
Another example can be, (-19) ≡ (-4)mod 5, here (-19+4) is also a multiple of 5. So, we can even represent negative numbers is terms of mod, remember.
Properties of Modular Operation
Now, you have understood the modulo operation, now there are some properties of Modulo Operation which are useful,
If a ≡ b (mod m), then a + c ≡ b + c (mod m).
If a ≡ b (mod m), then ac ≡ bc (mod m).
If ac ≡ bc (mod mc), then a ≡ b (mod m).
If a ≡ b (mod m) and c ≡ d (mod n) then ac ≡ bd (mod m)
If a ≡ b (mod m), then a^k ≡ b^k (mod m) (Very Important)
Now, let’s understand it one by one, we know that a ≡ b (mod m) is written as (a – b) % m = 0, so a + c ≡ b + c (mod m) can also be written as,
a + c ≡ b + c (mod m), (a + c) - (b+c) % m = 0, (a + c - b - c) % m = 0, (a - b) % m = 0
So, finally we get the same result which concludes us adding and subtracting a constant in both side doesn’t effect the modulo operation.
Similarly, ac ≡ bc (mod m) holds for a ≡ b (mod m),
(ac - bc) % m = 0, c*(a - b) % m = 0, (c % m) * ((a - b) % m) = 0, (a - b) % m = 0 as (c % m) is a constant.
It also concludes us that multiplying a constant in both side also doesn’t effect the modulo operation.
Now, let prove that that if a ≡ b (mod m) & c ≡ d (mod m) then,
ac ≡ bd (mod m).
If a ≡ b (mod m) and c ≡ d (mod m) then, (a - b) % m = 0 and (c - d) % m = 0 By division rule, a = (b + xm) and c = (d + ym) => ac – bd = (b + xm) ( d + ym) – bd => bd + bym + xmd +(xym)^2 – bd => bym + xmd + (xym)^2 => m (br + qd + qrm) which concludes (ac - bd) % m = 0
Hope you get all logic behind the properties, from last property we can also conclude,
If a ≡ b (mod m), then a^k ≡ b^k (mod m)
Try it once, it is similar to what we did in last proof.
Although we don’t require proofs but for understanding the properties, it is required and these are really simple.
Basic problems on modulo properties
Modulo operations are really helpful for solving mathematical problems, we will discuss some basic problems.
What is the remainder when 3^(202) + 5^(9) is divided by 8?
It’s seems very difficult in first look but thanks to modulo operation which can solve this problem quite easily. Let’s discuss it step by step.
For, 3^(202) we don’t need to calculate it, we can start from simple, we know that –
9 ≡ 1 (mod 8)
3^2 ≡ 1 (mod 8)
((3^2))^101 ≡ (1^101) (mod 8)
As (1^101) is 1, so 3^(202) ≡ (1^101) (mod 8)
Similarly we can calculate, 5^(9) ≡ 5 (mod 8)
and now by a ≡ b (mod m), then a + c ≡ b + c (mod m),
3^(202) + 5^(9) ≡ 1+5 (mod 8) which gives us 6.
Hope you get it, there are hundreds such problems, so you can practice it to understand the properties really well. Now let’s move ahead.
Modular Arithmetics in CS
Now, come to the main part of this post. I could have started from here but thought that I should give you a basic understanding of Modulo Operations which will help you to understand this part very easily.
We will discuss some basic use of modulo arithmetic, modulo multiplicative inverse and some algorithms as well.
Before that have you ever seen a problem where you are asked to print result in mod 1000000007 ?
Yes, we are asked to print mod(1e9+7) result in many mathematics problems and the main objective is to avoid overflow.
Sometime result is very big which we cannot store it in our basic datatypes, so to avoid such overflows we use mod operations.
These are some basic rules which you need to consider which using modulo in your code.
(a + b) % c = ((a % c) + (b % c) % c)
(a – b) % c = (((a % c) – (b % c) + c) % c)
(a * b) % c = ((a % c) * (b % c) % c)
So, if you are multiplying two big integers instead of (a*b) % c, you should use ((a % c) * (b % c)) % c to avoid overflow.
I have discussed some basic modular arithmetics in this post, in the most I will continue with it.