Why Modular Division?

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

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: Sum of factors of the product of a given array - GeeksforGeeks

1 Like