What will be the remainder when $ 32^{32^{32}} $ is divided by 9?
I was able to solve this by using the cyclicity of remainders when $2^{2^n}$ is divided by 9. For $n$ =even it gave remainder 7 and for $n$ =odd it gave remainder 4. So using this I worked out the above to get answer as 4.
However, can there be a more concise way possible using some theorem like Fermat's or something else?
Best Answer
Euler's theorem says that any number coprime to $9$, raised to the sixth power is congruent to $1$ mod $9$. We have that $32$ is coprime to $9$, so $32^6\equiv 1 \mod 9$.
Now, we need to know what the exponent $32^{32}$ is mod $6$. By the chinese remainder theorem, we can reduce to mod $2$ and mod $3$. The exponent is obviously even, so it's congruent to $0$ mod $2$. It then remains to check congruency modulo $3$. We have (working mod $3$): $$ 32^{32} \equiv 2^{32} \equiv (2^2)^{16} \equiv 1^{16} \equiv 1 $$ so that finally we get $32^{32}\equiv 4$ mod $6$.
Back to the original question, this means that for some natural number $n$ $$ 32^{32^{32}} = 32^{6n + 4} \equiv 32^4 \equiv 5^4 \mod 9 $$ This is not too difficult to calculate, since $5^2 = 25 \equiv -2$ mod $9$, so $5^4 \equiv (-2)^2 \equiv 4$.