prime powers modulo prime

Question

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.

Answer 1

This is exactly Fermat's Little Theorem. Its generalization is Fermat-Euler theorem.

Answer 2

"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.