compute a^b^c mod p

found this problem in a book to compute a ^ b ^ c mod p where p is prime and a, b, c are long longs.

what can be the best way??


Compute res=(b^c) mod (p-1) using fast exponentiation method and then (a^res)mod p using the same.


can u explain how would this work exactly…??

also, can i extend your answer to the possibility of optimizing
the calculation of a ^ b m by doing b = (m-1) beforehand…??

is there any exceptional/corner case??

Hello , the answer that @phantom11 gave is based on Fermat’s Little theorem .
Fermat’s Little theorem states that a^(p-1) = 1 (mod p) . Where p is prime . This is valid for all integers a .
So if you have to calculate a^b mod ( p ) and b = k * (p-1) + m . Then you know a^b = (a^(p-1))^k * a^m . = 1^k * a^m = a^m . So yes you can indeed extend this to optimize calculation of a^b . And also you can use above to calculate a1^a2^a3… modulo a prime number p.


thanx for the nice explanation…

However, the wikipedia page for “fermat’s” little theorem states that the relation a^(p-1) = 1 (mod p) would hold only in the case when a is not divisible by prime p. I guess in our case this should not affect anything 'coz if a % p == 0 then answer will automatically be zero.

Also, when we extend this for a1^a2^a3… modulo a prime number p
i shud calculate a2 ^ a3 mod (p-1) but a3 ^ a4 modulo (what)??(considering that p - 1 will not be prime)

@code_master01 : Yes if a is divisible by p , answer will be 0 . I thought you will take a mod p in the beginning itself and if its zero you output 0.
Also it doesn’t seem to extend easily as you said .

1 Like

@vineetpaliwal : if p is not necessarily prime … then how to solve this problem…

@surajtripathi : I will answer that . You question seems related to an ongoing contest at hackerrank , so I will answer it only after the contest is over which is five hours from now . I have solved all questions in Ad Infinitum at Hackerrank , you are welcome to ask your questions after the contest is over .

okay thanks @vineetpaliwal
plz tell the method after this contest

this is also related to a cool spoj problem…:slight_smile:

If p is not prime you may use Euler’s Theorem, Fermat’s theorem is a special case of it.