prime powers modulo prime I stumbled upon the following property: $n\equiv n^5\bmod 5$ for all $n\in\mathbb{Z}$, so out of I tried other (prime) numbers $n\equiv n^p\bmod p$.
My question is whether this is true for all primes $p$ and $n\in\mathbb{Z}$ and if so, how to prove it. Also, are there any non-primes for which the relation holds?
It might be a very basic fact I've forgotten.
 A: This is exactly Fermat's Little Theorem. Its generalization is Fermat-Euler theorem.
A: "Also, are there any non-primes for which the relation holds?" 
Yes.
It is called Euler's Theorem, and is basically a generalization of Fermat's Little Theorem.
It states the following:
Let $\gcd(a,n)=1$
Then $$a^{\phi(n)} \equiv 1 \pmod{n}$$
Proof:
Let $a_1,a_2,a_3,\dots a_{\phi(n)}$ be the reduced canonical residues modulo $n$. As $(a,n)=1$ $aa_1,aa_2,\dots,aa_{\phi(n)}$ are also a complete set of incongruent reduced residues. 
Thus,
$$aa_1\cdot aa_2\cdots aa_{\phi(n)} \equiv a_1a_2\cdots a_{\phi(n)} \pmod{n}$$
$$a^{\phi(n)}a_1a_2\cdots a_{\phi(n)}\equiv a_1a_2\cdots a_{\phi(n)}$$
Since, $\gcd(a_1a_2\cdots a_{\phi(n)},n)=1$ we may cancel it out of both sides,
$$a^{\phi(n)} \equiv 1 \pmod{n}$$

If $n$ is prime, then $\phi(n)=n-1$ and if $\gcd(a,n)=1$. Then we have,

$$a^{n-1}\equiv 1 \pmod{n} \iff a^n\equiv a\pmod{n}$$
On the other hand, if $\gcd(a,n)\ne1$, then $n|a$ since $n$ is prime, and both sides are congruent to $0$ modulo $n$.
Thus Fermat's little theorem is a special case of Euler's Theorem.

Note: $\phi(n)$ denotes Euler's totient function.
