Some higher powers!

Let's suppose that $99^{99} = 6k + a$ for some $k,a \in \mathbb{N}$ . Then $3^{99^{99}} \equiv 3^{6k + a} \equiv (3^k)^6 \times 3^a \equiv 3^a \mod 7$ . This last congruence is given to us by Fermat's little theorem. So we want to find an $a$ such that $99^{99} = 6k + a$ . But this is just finding an $a$ such that $99^{99} \equiv a \mod 6$ . Computing this is not trivial but if we apply the Chinese Remainder Theorem, we would just need to compute $99^{99} \mod 2$ and $99^{99} \mod 3$ .

On one hand, $99^{99} \equiv 0 \mod 3$ . This is trivial because $3$ already divides $99$ . And it is also obvious that $99^{99} \equiv 1 \mod 2$ because it is odd. So we have $a \equiv 0 \mod 3$ and $a \equiv 1 \mod 2$ . Using the Chinese Remainder Theorem we find that this means $a \equiv 3 \mod 6$ . And for convenience we may pick the smallest value, $a = 3$ .

Substituting this into our original computation, $3^{99^{99}} \equiv 3^3 \equiv 27 \equiv 6 \mod 7$ .