In competitive programming, Modular Arithmetic Properties are essential tools in solving big number problems. In the problem statement, whenever they say, “print the answer  “, 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 →  . 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.  

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 –

2.  

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 –

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

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,

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

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,    or, simply,   . Now, in this formula if we multiply on both sides by a^-2, we get,

Now, we will combine all the equations to get our end formula. Now, can be written as,

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

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

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,

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   . 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 –

Now, applying our equation 4, we get,

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

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

part, firstly, compute the value of

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

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. If you find this post helpful, please appreciate my efforts by recommending or tweet or liking. Happy Coding…! 🙂

Other resources –

• Congruences –  Contributor – Sai Avinash