# Modulo problem

given array Numerator[] = { a1 , a2 , a3 … an }
and Denominator[] = { b1 , b2 , b3 … bn }

we have to find ((a1.a2.a3 … an)/(b1.b2.b3 … bn)) % P
given that final value will always be a integer…

((a1%p.a2%p.a3%p…)/(b1%p.b2%p.b3%p…))%p

To calculate (a/b)%m where m is prime NO ,we use multiplicative inverse
If m is a prime number then

(a / b) % m = (a % m * b^(m - 2) % m) % m
For proof see Fermats theorem…
Hope this helps

2 Likes

http://discuss.codechef.com/questions/4698/use-of-modulo-1000007-in-competitions

1 Like

`(a/b) (mod P) = (a * b``-1``) (mod P) = (a (mod P) * b``-1` `(mod P)) (mod P)`.

Now, by Fermat’s theorem, `b``-1` `(mod P)` will be `b``P-2` `(mod P)`. Of course, for this `b` and `P` must be co-prime to each other and `P` must be a prime. So, `(a.b) (mod P) = (a (mod P) * b``P-2` `(mod P)) (mod P)`.

Now, assuming `a``1`, `a``2`, …, `a``n` and `b``1`, `b``2`, …, `b``n` are co-prime to the prime `P`,

```((a1.a2. ... .an) / (b1.b2. ... .bn)) % P
= ((a1.a2. ... .an) * (b1.b2. ... .bn)P-2) % P
.
.
.
= [(a1 % P) * (a2 % P) * ... * (an % P) * (b1P-2 % P) * (b2P-2 % P) * ... * (bnP-2 % P)] % P
```

NB: This only happens when `P` is a prime and `a``1`, `a``2`, …, `a``n` and `b``1`, `b``2`, …, `b``n` are co-prime to `P`.

1 Like

thanks for the link it was great help…

@nirajs : You are most welcome . Cheers , Happy coding .

what if P is not prime.?