I used to participate in programming competitions and at times I see that the solution should be the remainder when divided with some big prime number (usually that would be 1000000007). In one of the problems, I need to divide a very big number by another very big number and find the modulo of the division. Say one of the big numbers is factorial of 10000. So, the actual problem is how can I find the solution to
$$((A*B*C…)/(a*b*c*…))mod 1000000007$$
where the numerator and denominator are so huge.
I tried this by hand and it holds good.
$$(2 * 3 * 4 * 5) mod 7 = (((((2 mod 7 * 3) mod 7) * 4) mod 7) * 5) mod 7$$
- I would like to know, whether it will be True always. If so I will find the numerator and denominator values with this method.
Now, the second part, is division.
$$(A / B) mod C = ((A mod C)/(BmodC))modC$$
I thought that the above equation would be true. But it doesnt work for,
$$(((2*3)mod5)/(1*2)mod5)mod5\ne((2*3)/(1*2))mod5$$
So, how can I find value for the expression which I mentioned at the beginning?
Best Answer
The way to divide by a number $a$ $(\bmod p)$ is to multiply by its inverse. To find its inverse, you can use the extended Euclidean algorithm.
In your example, we are dividing by $2$ modulo $5$. We calculate
$$5 = 2 \cdot 2 + 1$$ and have found the gcd of $2$ and $5$ after one step of the algorithm.
Now write $1 = 5 - 2 \cdot 2$ and reduce modulo $5$, to get $$1 \equiv (-2) \cdot 2 \equiv 3 \cdot 2 \, (\bmod 5),$$ so $2^{-1} \equiv 3 (\bmod 5).$ In particular, you have $$6 / 2 \equiv 6 \cdot 3 \equiv 1 \cdot 3 \equiv 3 (\bmod 5).$$
For a more difficult example, consider $123456/192$ modulo $17$.
We first reduce $192 \equiv 5 (\bmod 17)$. Now we calculate the inverse of $5$ mod $17$: $$17 = 3 \cdot 5 + 2,$$ $$5 = 2\cdot 2 + 1,$$ and so $$1 = 5 - 2 \cdot 2 = 5 - 2(17 - 3 \cdot 5) =7 \cdot 5 - 2 \cdot 17.$$ This gives $7 \cdot 5 \equiv 1 (\bmod 17)$, so $5^{-1} = 7$.
Now $123456/192 \equiv 123456 \cdot 5^{-1} \equiv 123456 \cdot 7 \equiv 2 \cdot 7 \equiv 14$ (modulo $17$).
In fact, $123456/192 = 643 = 37 \cdot 17 + 14$, so it checks out.