#modular-inverse

[trojanguy]

Modular Inverse

This topic pata nai q is one of favourite topic of one of my friend named Ankur Rana.

So the September Challenge made me learn about this.

So lets see what it is.

Suppose you need to calculate the following 

(n*(n-1)/5!)%10000

so as u can see the mod can easily be distributed over the numerator part but when it comes to denominar part, you have to write denominator in inverse form.

like (n*(n-1) * 5! ^-1)%10000

so now how to calculate modular inverse. It is very simple.

power(5!,10000-2,10000)

yes this much of simple. Now simple multiply this term and then take mod.

For this you can exponentiation by squaring method.