Modular Exponentiation and large numbers

I am having trouble in understanding how this code is giving the correct answer for larger test cases (TL > limit of long long int). Suppose TL = 83478347589347598347598347598347983475983475983475893475983475893475 and N = 348573894578934759834759834759834798327498237498237498237498327482397492384, the above code will give a = 159184929 and b = 749176548. Now we’ll calculate a^b % MOD instead of directly calculating TL^N % MOD. How is a^b % MOD == TL^N % MOD?

2 Likes

U can go through “Fermat’s Little Theorem”…hope this will help…:slight_smile:

1 Like

I understood the part where he takes A as a string input and then did a=(a*10+(A[i]-‘0’))%1000000007;. You can express (a * b)MOD as ((A MOD) * (B MOD) ) MOD. So he makes a = TL % MOD since it does not affect whether you take MOD before or after multiplication. @kunal361 I dont know much about Fermat’s theorem. Could you briefly explain how to apply it here. Does it require that N be of the form prime-1?

1 Like

According to Fermat’s Little Theorm, A^ (p-1) ≡ 1 p , where p is a prime number. Hence we take B(p-1) => B%(10^9+6).
Now we have two 9 digit numbers which we solve using fast exponentiation.

2 Likes
//