How do you solve where is prime?

Reality check: you can’t just crunch the numbers since this might be .

First, the highest part must be chopped down. Fortunately our answer is taken modulo a prime number. So if we can solve for where , we can safely take .

E.g. if , then ; these exponents disappear.

This is Fermat’s Little Theorem (a.k.a. phi function, totient), giving us when is prime.

So, calculate using modular exponentiation. Then do it again on with . This operation is as follows:

typedef unsigned long long uint64; uint64 modular_pow(uint64 base, uint64 exp, uint64 mod) { uint64 result = 1; base = base % mod; while (exp > 0) { if (exp % 2 == 1) { result *= base; result %= mod; } exp >>= 1; base *= base; base %= mod; } return result; }

**But wait!** There’s one loose end: what if we can’t solve ? This case too must be handled but I’ll leave that to you.