{"id":1529,"date":"2014-12-24T10:09:47","date_gmt":"2014-12-24T10:09:47","guid":{"rendered":"http:\/\/theoryofprogramming.wordpress.com\/?p=10"},"modified":"2023-12-12T02:53:09","modified_gmt":"2023-12-12T02:53:09","slug":"modular-arithmetic-properties","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2014\/12\/24\/modular-arithmetic-properties\/","title":{"rendered":"Modular Arithmetic Properties"},"content":{"rendered":"\n

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 \u2192 \" 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…!<\/p>\n\n\n\n

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 –<\/p>\n\n\n\n

1.   \" \left ( a+b \right ) \bmod P \"<\/p>\n\n\n\n

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 –<\/p>\n\n\n

\"<\/p>\n\n\n\n

2.  \" \left ( a \times b \right )\bmod P \"<\/p>\n\n\n\n

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 –<\/p>\n\n\n

\"<\/p>\n\n\n\n

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!<\/p>\n\n\n\n

3.   \" \left ( \cfrac{a}{b}\right) \mod P \"<\/p>\n\n\n\n

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<\/strong>, Fermat’s Little Theorem<\/strong> and Binary Exponentiation Technique<\/strong>.<\/p>\n\n\n\n

Modular <\/strong>Inverse <\/b>– Modular Inverse of an integer ‘a’ modulo ‘m’ is an integer ‘x’ such that,<\/p>\n\n\n

\"<\/p>\n\n\n\n

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

\"<\/p>\n\n\n\n

Fermat’s Little Theorem <\/strong> – Fermat’s Little Theorem states that if ‘p’ is a prime number, then for any integer a, the number ap<\/sup> – a<\/strong> 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<\/sup><\/strong>, we get,<\/p>\n\n\n

\"<\/p>\n\n\n\n

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

\"<\/p>\n\n\n\n

Applying eq. (2) on this, we get,<\/p>\n\n\n

\"<\/p>\n\n\n\n

Now, applying our Fermat’s Little Theorem formula, i.e., eq.(3), we get,<\/p>\n\n\n

\"<\/p>\n\n\n\n

Now, calculating b(p – 2)<\/sup> % p<\/strong> 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<\/strong> for this. It is very simple, for a positive integer ‘n’, we have (assuming integer division),<\/p>\n\n\n

\"<\/p>\n\n\n\n

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)<\/sup><\/strong> in a variable temp, we can reduce the complexity to O(log n), which is pretty fast.<\/p>\n\n\n\n

So the equation 4 that we derived is the final formula of calculating – <\/p>\n\n\n

\"<\/p>\n\n\n\n

So the overall process of computing will have a complexity of O(log n).<\/p>\n\n\n\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<\/strong><\/a>. 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 –<\/p>\n\n\n

\"<\/p>\n\n\n\n

Now, applying our equation 4, we get,<\/p>\n\n\n

\"<\/p>\n\n\n\n

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<\/strong><\/a> to the same HackerRank problem. Now, the<\/p>\n\n\n

\"<\/p>\n\n\n\n

part can be calculated by the above described example. Now, to calculate the<\/p>\n\n\n

\"<\/p>\n\n\n\n

part, firstly, compute the value of<\/p>\n\n\n

\"<\/p>\n\n\n\n

and let’s say we store it in a variable ‘temp’. Now all we have to do is to calculate<\/p>\n\n\n

\"<\/p>\n\n\n\n

we do this by Binary Exponentiation Technique. To help you with coding I have put my code of the Binary Exponentiation Function here.<\/p>\n\n\n\n