Interesting results of powers of numbers modulo some other numbers. Some interesting results on remainders obtained on division of powers of numbers by certain numbers are:

*

*$x^4$ = $5k$ or $5k+1$ depending on whether $x = 5q$ or $5q+r$, where ${r = 1,2,3,4}$.

*$x^4$ is of the form $16k+1$ for all odd integers $x$, and $16k$ for even integers.

These results I find very useful to solve problems from number theory, but the list of these results seems to be never-ending.
It seems that it is expected to "pick them on the way", or do tedious calculations.
What are some other "important" and interesting results that will help me solve an acceptable number of problems from olympiad and below-olympiad level elementary number theory?
Is the list just so enormous that it is unviable to even discuss this question?
(It would be awesome if such a list existed.)
 A: There are three general results, two very common and one somewhat less so, in strictly increasing order of strength:

*

*Fermat's little theorem: if $p$ is prime and $\gcd(a, p) = 1$ then $a^{p-1} \equiv 1 \bmod p$.

*Euler's totient theorem: if $\gcd(a, n) = 1$ then $a^{\varphi(n)} \equiv 1 \bmod n$ where $\varphi(n)$ is the totient function.

*Carmichael's theorem: if $\gcd(a, n) = 1$ then $a^{\lambda(n)} \equiv 1 \bmod n$ where $\lambda(n)$ is the Carmichael function. This bound is sharp; it is not possible to replace $\lambda(n)$ with a smaller number.

The totient can be computed from a prime factorization $n = \prod p_i^{e_i}$ as
$$\varphi(n) = \prod (p_i - 1) p_i^{e_i - 1} = n \prod \left( 1 - \frac{1}{p_i} \right)$$
while the Carmichael function can be computed from a prime factorization as
$$\lambda(n) = \text{lcm}(\lambda(p_i^{e_i}))$$
and $\lambda(p_i^{e_i})$ takes the following values: it is equal to $\varphi(p_i^{e_i}) = (p_i - 1) p_i^{e_i-1}$ if $p_i$ is odd or if $p_i = 2$ and $e_i \le 2$, and equal to $\varphi(2^e) = 2^{e-2}$ otherwise. So it's a bit more fiddly but still pretty easy to compute for a particular small $n$ in practice.
Example. Let $n = 240 = 2^4 \cdot 3 \cdot 5$. We have $\varphi(120) = 2^3 \cdot 2 \cdot 4 = 64$ so Euler's theorem gives that if $\gcd(a, 120) = 1$ then
$$a^{64} \equiv 1 \bmod 240$$
but $\lambda(240) = \text{lcm}(4, 2, 4) = 4$ so Carmichael's theorem gives the considerably sharper
$$a^4 \equiv 1 \bmod 240.$$
This is furthermore the best such result we can have for $a^4$, since $\lambda(p^k) > 4$ for all other prime powers.
There are less straightforward things one can say using a more detailed analysis of the group of units $\bmod n$. For example, if $p$ is an odd prime one can prove that
$$a^{ \frac{p-1}{2} } \equiv \left( \frac{a}{p} \right) \bmod p$$
where $\left( \frac{a}{p} \right)$ is the Legendre symbol.
More generally, Fermat's little theorem implies that if $k | p-1$ then $a^{ \frac{p-1}{k} }$ must be congruent to a root of $x^k - 1 \bmod p$ and there are (as it turns out) exactly $k$ of these, which can be useful to rule out solutions to some easy Diophantine equations.
