CODEWITHSUNDEEP
algorithmmoduluschinese-remainder-theorem
somu Boy
somu Boy

Reputation: 19

Calculating inverse Mod where Mod is not prime

I want to calculate value of

F(N) = (F(N-1) * [((N-R+1)^(N-R+1))/(R^R)]) mod M for given values of N,R and M.

Here A^B shows A power B and NOT any Bitwise operation

Here M need not to be prime.How to approach this question?Please help because if M was prime that it would not have beed so difficult to find inverse of R^R mod M.

But as M can be any value ranging from 1 to 10^9.I am not able to tackle this problem.

N can be between 1 and 10^5 and R is less than or equal to N.

Upvotes: 1

Views: 774

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Assuming you know somehow that the result of the division is an integer:

As N and R are small, you can do this by computing the prime factorisation of N-R+1 and R.

If we know that R=p^a...q^b then R^R = p^(Ra)...q^(Rb).

Similarly you can work out the power of each prime in (N-R+1)^(N-R+1).

Subtract the powers of the primes in R^R from the powers of the primes in (N-R+1)^(N-R+1) gives you the powers of each prime in the result.

You can then use a standard binary exponentiation routine to compute the result modulo M with no inverses required.

Upvotes: 1

Related Questions