• + 2 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!