Modular Arithmetic Properties


In competitive programming, modular arithmetic is an essential tool 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!

/* 
 * Code to print the mod of
 * sum of two factorials x!
 * and y!, where both x and
 * y can be around 1000 or so.
 *
 * by,
 * Vamsi Sangam.
 */

#include <stdio.h>

#define PRIME 1000000007		// Or any prime

// Returns (n! % PRIME)
long long int factorial(long long int n)
{
	if (n == 0) {
		return 1;
	} else if (n == 1) {
		return 1;
	} else {
		// Applying our eq.(2) to --> n * factorial(n - 1)
		// to get --> (n! % PRIME)
		return ((n % PRIME) * (factorial(n - 1) % PRIME)) % PRIME;
	}
}

int main()
{
	long long int x, y;
	
	scanf("%lld%lld", &x, &y);		// Don't forget the &'s...!

	x = factorial(x);
	//Overwriting the value of (x! % PRIME) in x itself
	y = factorial(y);
	//Overwriting the value of (y! % PRIME) in y itself
	
	//Applying our eq.(1) to get --> (x! + y!) % PRIME
	long long int answer = (x + y) % PRIME;
	
	printf("%lld\n", answer);
	
	return 0;
}

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 ap – a is an integer multiple of ‘p’. In the notation of modular arithmetic, this is expressed as,  a^{P} \equiv a \bmod P    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,

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.

/*
 * Binary Exponentiation Technique
 *
 * by,
 * Vamsi Sangam.
 */

#define PRIME 1000000007		// Or any prime

// Returns (x^n) % PRIME
long long int binary_exp(long long int x, long long int n)
{
	if (n == 0) {
		return 1;
	} else if (n == 1) {
		return x % PRIME;
	} else {
		long long int temp = binary_exp(x, n / 2);
		temp = (temp * temp) % PRIME;
		
		if (n % 2 == 0) {
			return temp;
		} else {
			return ((x % PRIME) * temp) % PRIME;
		}
	}
}

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. Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 … If you find this post helpful, please appreciate my efforts by recommending or tweet or liking. Happy Coding…! 🙂

Other resources –

You may also like –

More in the Navigation Page ! →

Advertisements

6 thoughts on “Modular Arithmetic Properties

  1. 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)

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s