 # 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… 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
//