We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I dont know if its too late to answer, but this is regarding your question about b % (MOD - 1). Consider Fermat's theorem, a^(p - 1) = 1(mod p) when p is prime. Now the question dictates the calculation to be a^b % p. If b is a multiple of (p - 1) say (p - 1)x, then a^b % p is a^((p - 1)x) % p which is 1 since 1^x(mod p) = 1(mod p). Now if b is not a multiple of (p - 1) say ((p - 1)x + y), then we have a^b % p as (a^(p - 1)x + y) % p. Split this into two terms and take mods to multiply (its a property of mods).
((a^(p - 1)x) % p) * (a^y % p) = 1^(x)*(a^y % p) which is the answer to your question. y = b % (p - 1) = ((p - 1)x + y) % (p - 1). Hope this helps!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Power of large numbers
You are viewing a single comment's thread. Return to all comments →
I dont know if its too late to answer, but this is regarding your question about b % (MOD - 1). Consider Fermat's theorem, a^(p - 1) = 1(mod p) when p is prime. Now the question dictates the calculation to be a^b % p. If b is a multiple of (p - 1) say (p - 1)x, then a^b % p is a^((p - 1)x) % p which is 1 since 1^x(mod p) = 1(mod p). Now if b is not a multiple of (p - 1) say ((p - 1)x + y), then we have a^b % p as (a^(p - 1)x + y) % p. Split this into two terms and take mods to multiply (its a property of mods). ((a^(p - 1)x) % p) * (a^y % p) = 1^(x)*(a^y % p) which is the answer to your question. y = b % (p - 1) = ((p - 1)x + y) % (p - 1). Hope this helps!