MHB Can you simplify a monstrous remainder problem using modular arithmetic?

[Guest2]

Find ${5^{2009}}^{1492}\mod{503}.$

How do you calculate a beast like this?

 

[Nono713]

Do you know about Euler's theorem, or Fermat's little theorem? Powers of 5 are periodic modulo 503, so your expression can be simplified if you can find what that big exponent is modulo that period. Euler's theorem tells us that the period is divisible by divides 503 - 1 = 502 (since 503 is prime). Does that make sense?

If that doesn't help, what if you replaced 503 by, say, 7, does that make it simpler to reason about?