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
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 