$p$ divides $n^p-n$

Question

Its very easy to prove $p\mid n^p-n$ for p=3,5,7, it fails for p=9 because $$ (n+1)^9-(n+1)= n^9+9n^8+36n^7+84n^6+126n^5+126n^4+84 n^3+36n^2+8n $$ and $84= 2²\times 3\times7$. Is it true for any $p$ prime? I have checked many primes, but have no idea for the general case.

Answer 1

Yes. This is known as Fermat's little theorem. This states $$a^p \equiv a \mod p$$

This gives $a^p-a \equiv 0 \mod p$, or $p \mid a^p-a$.

---

There is a generalisation known as the Euler-Fermat theorem. This states $$a^{\varphi(m)} \equiv 1 \mod m$$

iff $\gcd(a,m)=1$. Because $\varphi(9)=6$, we have

$$a^{6} \equiv 1 \mod 9$$

iff $\gcd(a,9)=1$.

Answer 2

First, well done if you have discovered this for yourself. Indeed the result is true for any prime, and is known, in the form $n^{p-1}\equiv 1 \bmod p$ (where $n$ is not a multiple of $p$), as Fermat's little theorem. It is a major result.

You might want to think of proving it yourself. In what follows, unless otherwise stated or obvious, the numbers involved are not divisible by $p$ and congruences are taken modulo $p$.

First, suppose $a$ and $b$ are not equivalent modulo $p$, then show that $na$ and $nb$ are not equivalent.

Then deduce that the numbers $n, 2n, 3n \dots (p-1)n$ are distinct modulo $p$, and hence equivalent to the numbers $1,2,3\dots p-1$ in some order.

Now see what happens if you multiply the first set, and compare it with what you get when you multiply the second set.

This theorem is related to all sorts of other interesting things, and you could also try proving it by showing that the binomial coefficient $\binom pr$ is divisible by $p$ for $1\le r \lt p$. How to go from there, I will leave you to discover for yourself, if you can.

Answer 3

I'll provide the standard proof of Fermat's little theorem by induction on $n$.

Let $P(n)$ denote the statement $p\mid n^p-n$.

Clearly $p\mid 0^p-0$ for any prime $p$, so $P(0)$ holds.

Assume $P(k)$ is true for some $k\in\mathbb Z_{\ge 0}$. Then by Binomial theorem:

$$(k+1)^p-(k+1)=k^p-k+\binom{p}{p-1}k^{p-1}+\binom{p}{p-2}k^{p-2}+\cdots+\binom{p}{1}k,$$

which is divisible by $p$ because $p\mid \binom{p}{k}=\frac{p!}{(p-k)!k!}$ for any $1\le k\le p-1$. $P(k+1)$ holds too.

For another classic proof see Mark Bennet's answer. The hint at the end of his answer hints to the above induction proof.

Answer 4

Yes, this is only for primes as others have said. A very easy proof is found using group theory if you're familiar with it at all.

Assume $p$ is prime. Then consider the group $U(p)$, the multiplicative group of integers $x\leq p$ such that $\gcd(x,p)=1$. This group has order $\varphi(p)=p-1$, where $\varphi$ is Euler's Phi function. Now consider $a\in U(p)$. Because the order of an element divides the order of a group, we have

$$a^{p-1}=a^{\varphi(p)}=a^{|U(p)|}=1$$

This is all within the group $U(p)$, however this does imply

$$a^{p-1}\equiv 1\pmod p$$

or equivalently,

$$p\:|\:a^{p-1}-1$$

therefore,

$$p\:|\:a\left(a^{p-1}-1\right)=a^p-a$$

QED

Answer 5

Let $K=\Bbb Z/p\Bbb Z$ with $p$ prime. Then $K$ is a field and $(K^*,\times)$ is a multiplicative group with $p-1$ elements. In particular (by the the Lagrange's theorem) the order of each element of this group divide $p-1$. Then for all $x$ in $K$ ; $x^{p-1}=1$, so $x^p=x$ but this equality is also valide for $x=0$. This mean that for all $n$ in $\Bbb Z$; $n^p=n$ mod $p$, or that $p$ divide $n^p-n$.