I didn’t find anything that clears my doubt on Google.
Given three positive integers a,b and m, the task is to find (a/b) under modulo m.(modular division)
modular division is possible if and only if gcd(b,m) is 1.
Why do we calculate (a/b)%m as (mod_inverse(b,m) * a)%m ??
Can’t we simply calculate a/b and then modulo it with m?
Can anyone please explain me the significance of modular division?
For eg., we do (a+b)%m as (a%m + b%m)%m to avoid overflow issues(same with (a*b)%m and (a-b)%m ).
But in case of division, there is no overflow, as the result of (a/b) is always going to be less than or equal to a(given that a and b are integers).
Any help is appreciated. 
It is based on Fermat’s little theorem I guess. Anyways, hope this will help.
An example problem would be,
Given an array A of N integers, your task is to find the sum of factors of the product of those N Integers
Since the answer could be very large, output it modulo 10^9+7
Constraints
1\le N\le 10^{6}
1\le A_i\le 10^{6}
This can be solved using factorisation and a simple binomial formula. But implementation is little bit difficult since the product will definitely exceed the range of primitives. Since it was mentioned to calculate the result modulo 10^9 + 7 which is a prime, Fermat’s little theorem can be used.
The expansion of binomial formula requires division of two big numbers modulo 10^9 + 7. This can be done using the inverse method.
The link where you can practice the problem: https://www.geeksforgeeks.org/sum-of-factors-of-the-product-of-a-given-array/
1 Like