Proving that $m^p-m$ is divisible by $p$

Question

Let a prime number $p$ and a natural number $m$. Prove that $m^p-m$ is divisible by $p$.

We were given a hint to use a multinomial coefficient. But I'm not really sure how it helps me. If I say that $m=1+1+...+1$ I get : $$\sum_{k_{1},k_{2},\ldots,k_{m}}^{p}{p \choose k_{1},k_{2},\ldots,k_{m}}$$ I remember we proved something in class abount $p \choose k$ being divisible by $p$ only if $1\leq k < p$ but I'm not really sure how it helps me here...

This is Fermat's little theorem. – hmakholm left over Monica Dec 16 '12 at 14:20 — hmakholm left over Monica, Dec 16 '12 at 14:20

score 2 · Answer 1 · answered Dec 16 '12 at 15:32

2

If $p\mid m, p\mid(m^p-m)$

else $(m,p)=1$

We know, $S:\{r,1\le r<p\}, T: \{mr,1\le r<p, (m,p)=1\}$ are equivalent

as if $mr_1\equiv mr_2\pmod p$ where $1\le r_1<r_2<p$

$\implies p\mid(r_2-r_1)$ which is clearly impossible.

So, $\prod_{r,1\le r<p}r\equiv \prod_{r,1\le r<p}mr\pmod p$

$\implies p\mid (m^{p-1}-1)\prod_{r,1\le r<p}r$

$\implies p\mid (m^{p-1}-1)$ as $(p,\prod_{r,1\le r<p}r)=1$

answered Dec 16 '12 at 15:32

lab bhattacharjee

274,582

A lot of concepts here I'm not familiar with... – Nescio Dec 16 '12 at 19:30
@nescio and a good chance to learn something about them... – draks ... Dec 20 '12 at 19:21

score 1 · Accepted Answer · answered Dec 16 '12 at 14:21

The ideas you have written down are in a great direction to solving this problem. Try to remember the proof/reason why $\binom{p}{k}$ is divisible by $p$ if and only if $1\leq k < p$, and then use the same idea to see which of the terms in your sum are divisible by $p.$

Proving that $m^p-m$ is divisible by $p$

2 Answers2