A doubtregarding MMI(modulo multiplacative inverse)

Is calculating MMI of 2**n through pow(pow(2,n),M-2,M) and pow(pow(2,n),M-1,M) is same,when do we use M-1 and when do we use M-2,given that 2 and M are co-prime.
See this question


Here is lalit kundu’s solution.Why p-1 instead of p-2?
https://www.hackerrank.com/rest/contests/infinitum10/challenges/number-of-subsets/hackers/xorfire/download_solution

Hi sandeep,

no doubt for calculating MMI we use M-2 because it is case of (2 power n) but what happen when power of 2 is much large like (2 power m : where m = 2 power n) so in this case we apply Fermat’s little theorem https://en.wikipedia.org/wiki/Fermat’s_little_theorem
so according to theorem (2 power m = 2 power g : where g = m %(M-1)) that’s why M-1 is used in the code and after that we use M-2 also because both thing are different

M-2 is due to MMI. and M-1 is due to Fermats theorem
(a power p-1)%p=1

lets take simple example of Fermats theorem you have to calculate (2 power 9)%7 then first method is to call power function which calculate power in logarithmic time but second method is to apply Fermat’s theorem means first find 9%(7-1) =3 and now call power function to calculate (2 power 3)%7 answer will be same in both case means first you have to reduce that power and then calculate power of number both of these operation require logarithmic power function. i think it would help you but please open wikipedia for more info and limitation of theorem :slight_smile:

2 Likes