Modular Arithmetic Properties

In competitive programming, Modular Arithmetic Properties are essential tools in solving big number problems. In the problem statement, whenever they say, “print the answer $\bmod (10^{9} + 7)$ “, it’s not that simple. You may have worked a lot to get the logic, but the output must be given as they say. You may get your answer stored in a single variable and just print the value of → $variable \bmod (10^{9} + 7)$ . But what if you can’t get it into a single variable, what if it gets out of the range of long long int or so…? It is then that you have to use modular arithmetic…!

Let’s go systematically, by stating the principles one-by-one. There are two fundamental formula for modular arithmetic, and the third one ins’t exactly fundamental as it needs a lot of derivation –

1. $\left ( a+b \right ) \bmod P$

If we were to print the modulo ‘PRIME’ of the sum of two big numbers stored in variables ‘a’ and ‘b’, we apply the following formula –

$\left ( a+b \right ) \bmod P = \left(\left ( a \bmod P \right ) + \left ( b \bmod P \right ) \right ) \bmod P \qquad \rightarrow eq. \left ( 1 \right )$

2. $\left ( a \times b \right )\bmod P$

Now, if we were to print the modulo ‘PRIME’ of the product of two big numbers stored in variables ‘a’ and ‘b’, we apply the following formula –

$\left ( a \times b \right ) \bmod P = \left(\left ( a \bmod P \right ) \times \left ( b \bmod P \right ) \right ) \bmod P \qquad \rightarrow eq. \left ( 2 \right )$

As we have just gained a little knowledge on the fundamentals of modular arithmetic, it is good time for a quick practice! Let’s try to solve a very straight-forward problem. We will take two inputs from the user, a variable ‘x’ and a variable ‘y’, and we are supposed to print the value of $(x! + y!) \bmod (10^{9} + 7)$ . It’s a super simple problem, you can work out on the paper and solve. Don’t worry if it is taking time, remember, things worth having don’t come easy! Knowledge is one such thing. Once you have coded, check your output by putting a few test cases and verifying it on a calculator. If you are stuck, you can refer to my code below!

3. $\left ( \cfrac{a}{b}\right) \mod P$

This equation is the bid bad guy! Now, if we were to print the modulo ‘PRIME’ of the quotient of two big numbers stored in variables ‘a’ and ‘b’, we don’t have a specific formula. This is what troubles a lot of programmers. It took me a month to learn this. I had to query in a many web sites, but I will explain it all here! So in order to calculate this, we need to learn two things the Modular Inverse, Fermat’s Little Theorem and Binary Exponentiation Technique.

Modular Inverse – Modular Inverse of an integer ‘a’ modulo ‘m’ is an integer ‘x’ such that,

$a x \equiv 1 \mod P \qquad \left ( or \right ) \qquad a a^{-1} \equiv 1 \mod P$

Every non-zero integer ‘a’ has an inverse (modulo p) for a prime ‘p’ and ‘a’ not a multiple of ‘p’. Example,

$1^{-1} \bmod 5 = 1 2^{-1} \bmod 5 = 3 3^{-1} \bmod 5 = 2 4^{-1} \bmod 5 = 4$

Fermat’s Little Theorem – Fermat’s Little Theorem states that if ‘p’ is a prime number, then for any integer a, the number a^p – a is an integer multiple of ‘p’. In the notation of modular arithmetic, this is expressed as, $a^{P} \equiv a \bmod P &s=1$ or, simply, $a^{P} \bmod P = a \bmod P$ . Now, in this formula if we multiply on both sides by a^-2, we get,

$a^{P - 2} \bmod P = a^{-1} \bmod P \quad \left ( or \right ) \quad a^{-1} = a^{P - 2} \bmod P \quad \rightarrow eq. \left ( 3 \right )$

Now, we will combine all the equations to get our end formula. Now, $\left ( \cfrac{a}{b} \right ) \mod P$ can be written as,

$\left ( a \times b^{-1} \right ) \bmod P$

Applying eq. (2) on this, we get,

$\left ( a \times b^{-1} \right ) \bmod P = \left(\left ( a \bmod P \right ) \times \left ( b^{-1} \bmod P \right ) \right ) \bmod P$

Now, applying our Fermat’s Little Theorem formula, i.e., eq.(3), we get,

$\left ( a \times b^{-1} \right ) \bmod P = \left(\left ( a \bmod P \right ) \times \left ( b^{\left ( P - 2 \right )} \bmod P \right ) \right ) \bmod P$

Now, calculating b^{(p – 2)} % p is a challenge here. As the online judges generally keep the prime number pretty big, we cannot afford the naive exponentiation technique. So, we use the Binary Exponentiation for this. It is very simple, for a positive integer ‘n’, we have (assuming integer division),

$x^{n} = \left\{\begin{array}{l} x \times x^{n / 2} \times x^{n / 2} \qquad \, \text{n is odd} \\ x^{n / 2} \times x^{n / 2} \qquad \qquad \text{n is even} \end{array}\right.$

This might seem like a very ordinary exponentiation technique that can be easily implemented by recursion. But if we use a little Dynamic Programming sense, by storing the value of a^{(n / 2)} in a variable temp, we can reduce the complexity to O(log n), which is pretty fast.

So the equation 4 that we derived is the final formula of calculating –

$\left ( \cfrac{a}{b} \right ) \mod P$

So the overall process of computing will have a complexity of O(log n).

Now, as we have the sufficient knowledge, let’s try practice. For the sake of practice, I take up a problem of HackerRank, Sherlock and Permutations. That’s because, I do all my coding practice in HackerRank and this problem will fit for the situation perfectly. On reading the problem statement carefully, one can easily come up with the formula –

$\cfrac{ \left ( n + m - 1 \right ) !}{\left (m - 1 \right ) ! \times n!} \ \bmod ( 10^{9} + 7)$

Now, applying our equation 4, we get,

$(((n + m - 1)! \bmod (10^{9} + 7)) \times (((m - 1)! \times n!)^{10^{9} + 7 - 2}) \bmod (10^{9} + 7)) \bmod (10^{9} + 7)$

Don’t get scared looking at the big formula, trust me, you’ll get it easily if you work it out on paper. If it gets too heavy on you refer to my discussion thread to the same HackerRank problem. Now, the

$(n + m - 1)! \bmod (10^{9} + 7)$

part can be calculated by the above described example. Now, to calculate the

$((m - 1)! \times n!)^{10^{9} + 7 - 2}$

part, firstly, compute the value of

$((m - 1)! \bmod (10^{9} + 7)) \times (n! \bmod (10^{9} + 7)) \bmod (10^{9} + 7)$

and let’s say we store it in a variable ‘temp’. Now all we have to do is to calculate

$temp^{(10^{9} + 7 - 2)} \bmod (10^{9} + 7)$

we do this by Binary Exponentiation Technique. To help you with coding I have put my code of the Binary Exponentiation Function here.

Don’t hurry things, you won’t understand them. This is a new level of difficulty, so try working out everything step-by-step on paper, you will understand them. If you are not able to get it even after trying on paper, I will gladly help you, but it’s a humble request to do your part too.

This is all you have to know about solving problems related to Modular Arithmetic. Though the problems related to this subject can become exceedingly complex, these are the fundamentals of the subject. If you have any doubts, how tiny ever, feel free to comment them. If you find this post helpful, please appreciate my efforts by recommending or tweet or liking. Happy Coding…! 🙂

21 thoughts on “Modular Arithmetic Properties”

b soma naik says:

13 February 2015 at 16:55

is there a method to calculate (a/b)%m when gcd(m,b)!=1. specifically in calculating nCr mod m../

1. Vamsi Sangam says:
  
  13 February 2015 at 17:03
  
  Well, frankly soma, I’ve been trying to figure that out since a long time. Didn’t find any satisfactory answers. But if I could make a guess, I’d say we can use the Fermat’s Theorem’s way of calculating it, only thing is that we’d end up getting zeroes here and there as the GCD != 1….
  
2. Dev says:
  
  15 March 2015 at 14:00
  
  #b soma naik
  
  (a/b)%m = (a*(b^m-2)%m)%m
  
3. pavan says:
  
  4 November 2020 at 20:14
  
  https://www.youtube.com/watch?v=-OPohCQqi_E
  
  I hope this video answers yours question
  
Paras Meena says:

15 March 2015 at 22:09

#b soma naik Using Lucas + Chinese reminder Theorem(Just Google for these topics :P) 😀

Anup Verma says:

7 June 2015 at 13:32

Why did you again compute x % PRIME and y % PRIME at Line 39 of first code:
long long int answer = ((x % PRIME) + (y % PRIME)) % PRIME;

when x is already x % PRIME and y is already y % PRIME before this line?

Also in the paragraph just above this code, the question: x! + y! mod (10^9 + 7) should be modified to
(x! + y!) mod (10^9 + 7)

1. Vamsi Sangam says:
  
  7 June 2015 at 14:15
  
  Yes, it was redundant… The necessary changes have been made… Thanks for pointing it out..! 🙂
  
2. nalin says:
  
  10 May 2020 at 16:29
  
  #anup verma
  where is the first code? I cant find it in my webpage
  
3. vikassinghvs says:
  
  20 May 2021 at 14:00
  
  I think it should have been the same as mentioned in the article take for example let x be 3 y be 5 and PRIME be 7 then x % PRIME + y % PRIME = 3 + 5 = 8 where as if we take (x % PRIME + y %PRIME) % PRIME =1
  
kripal98 says:

15 July 2020 at 17:27

very helpful 🙂

Avishek says:

16 July 2020 at 11:22

Wonderful explanatt 🤩

Manan Varma says:

24 July 2020 at 22:54

Thanks a ton! You made this topic seem interesting, most coders just overlook this and get stuck (like me). Thanks a lot!

vindu says:

19 October 2020 at 23:23

I have done that sherlock problem But it is giving some larger value when we do exponentiation please help me
////Help me with this solution even it is right why it is giving 180942713 as output for 2,3 inputs
static int fact(int n){
int f=1;
for(int i=1;i<=n;i++)
{
f*=i;
f=f%7;

}
return f%7;
}

static int solve(int n, int m) {

int a=fact(m+n-1);
a=a%7;
int b1=(fact(n))%7;
b1=(fastPowerMethod(b1,5,7))%7;
int b2=(fact(m-1))%7;
b2=(fastPowerMethod(b2,5,7))%7;

return (int)(a*b1*b2)%7;

}
static int fastPowerMethod(int base, int exponent, int modulus) {
if (exponent == 0) {return 1;}
else if (exponent % 2 == 0) {
long k = fastPowerMethod(base, exponent/2, modulus);
return (int)((k * k) % modulus);
}
else {
return (int)(((long)base * (long)fastPowerMethod(base, exponent-1, modulus)) % modulus);
}
}

Sagar says:

27 October 2020 at 14:30

My code for (X! +Y!) mod PRIME
is not giving correct answer for X=100 and Y= 80
Because in intermediate steps the wraparound happens.
So what to do for X=100?

1. Vamsi says:
  
  9 December 2023 at 11:03
  
  You’ll have to calculate ((X! mod PRIME) + (Y! mod PRIME)) mod PRIME.
  
Abhinav Gupta says:

7 December 2020 at 10:17

in the binary exponentiation formula when n is odd the power of x is wrong it should be (n-1)/2 in order to match with the lhs.

1. Vamsi says:
  
  9 December 2023 at 10:58
  
  You are right. When I stated n / 2 I meant integer division. I will keep the formula as n / 2 since it is easier to understand, but I will add a line indicating its integer division.
  
dsn says:

6 September 2021 at 20:08

cant’ see the factorial code

1. Vamsi says:
  
  9 December 2023 at 10:52
  
  Fixed now.
  
gauravpareek9 says:

21 September 2021 at 18:29

Hi Bro,
Thanks for detailed explained, really helpful. I am having hard time to understand how you calculated((m-1)!*n!)^109+7-2 mod PRIME part. Firstly you calculate it only (m-1)!*n! and store it in temp then you say now we just need to calculate temp^109+7-2, this part I did not get. How can we say that can you explain that logic, please. Other all details I am able to get but this part not able to quite get it. Thanks

MAnan says:

25 September 2021 at 21:11

what about Subtraction property in modular arithmetic?

Modular Arithmetic Properties

Related

21 thoughts on “Modular Arithmetic Properties”

Leave a Reply Cancel reply