Taking the modulus of the power? So I'm learning about Euler's theorem for reducing large powers modulo $n$ and what I'm wondering about is: can we simply take the modulus of a power of a number the same way we take it of the number itself before we apply the theorem? In all the problems I've found that I'm practicing on, it isn't done, for example $289^{289} \mod 100$ is simplified as $89^{289}$ but not as $89^{89}$. At the same time, I tried taking the modulus of the power and in all the examples the result stayed the same. So can one do it or not?
 A: Suppose we're working modulo $5$, just as an example. If we could reduce the power modulo $5$, that would mean, for example, that $2^5\equiv 2^0\pmod5$. As we can easily see, $1$ and $64$ are not the same modulo $5$, so this doesn't work.
Why doesn't it work? To see this, it helps to reconsider why reducing the base does work. Sticking with $5$, and asking the question more generally, why is it the same to multiply $ab$, or to multiply $a(b+5)$. Since multiples of $5$ are the same as $0$, modulo $5$, the product $a(b+5)=ab+5a$ is just $ab$, plus a multiple of $5$, which counts as nothing.
Digging a little deeper, the reason adding a multiple of $5$ counts as nothing, is because on a wheel with five clicks per revolution, adding any multiple of $5$ leaves your position unchanged.
Now, what about adding $5$ in the exponent? Assume that $a\not\equiv0\pmod5$, and consider how $a^b$ differs from $a^{b+5}$. It's a matter of multiplying by $a$ five times, so if that brings us back to the same place, then great. However, it doesn't, because multiplication here is not a wheel with five clicks per revolution. Non-zero numbers, mod $5$, will never multiply to give you $0$, so the only available stops are $1,2,3,4$. If we start at $1$ (like multiplication should), we can see that multiplication by $2$ comes around in $4$ clicks ($2^1\equiv 2,2^2\equiv 4,2^3\equiv 3,2^4\equiv 1$), as does multiplication by $3$ ($3^1\equiv 3,3^2\equiv 4,3^3\equiv 2,3^4\equiv 1$), while multiplication by $4$ only takes $2$ clicks to get back home ($4^1\equiv 4, 4^2\equiv 1$), and multiplication by $1$ never leaves home. In each case, we have the common result that $a^4\equiv 1$. Thus, it's actually not $a^{b+5}$ that's the same as $a^b$, but rather $a^{b+4}=a^ba^4\equiv a^b\cdot 1=a^b$.
This example worked out the way that it did because $5$ is prime, for a non-prime number things get more complicated, but I think the prime case is a good context to see why something is happening up in the exponent that is different from what happens with multiplication. It really boils down to the fact that addition takes place on a five-click cycle, while multiplication is either by $0$, or else takes place on a four-click cycle among the four non-zero choices.
