Deriving Fermat's Theorem

Question

I had an exercise for homework for a class that said prove $$(k+1)^p-k^p\equiv 1\pmod{p}$$ for all $k=0,1,....$ So I use the binomial formula to expand $$1=1^p=(k+1-k)^p=((k+1)-k)^p$$ $$=(k+1)^p+\left(\sum_{m=1}^{p-1}\binom{p}{m}(-1)^{m+1}(k+1)^{p-m}k^m\right)-k^p$$ But since $\binom{p}{m}=p\frac{(p-1)!}{(p-m)!m!)}\equiv 0\pmod{p}, (k+1)^p-k^p\equiv 1\pmod{p}.$

But the next task is to use this information to derive Fermat's theorem and I'm not sure now to get the expression in the form $a^{p-1}$. Any hint would help...

Answer 1

You've shown that $$ a^p-a\equiv0\pmod{p}\tag{1} $$ for all $a$. Now, remember that since $p$ is prime, $p\mid ab\implies p\mid a\lor p\mid b$. Now, $(1)$ is $$ a(a^{p-1}-1)\equiv0\pmod{p}\tag{2} $$

Answer 2

The intermediate step is to rewrite what you just proved as

$$(k+1)^p\equiv k^p+1\pmod p$$

and then use this to prove that $k^p\equiv k\pmod p$ for all $k$ by induction. It's certainly true that $1^p\equiv1\pmod p$, so the previous result and the inductive hypothesis combine to show

$$\begin{align} (k+1)^p&\equiv k^p+1\pmod p\\ &\equiv k+1\pmod p \end{align}$$

so the result is true for all (positive) $k$ (hence all $k$, since you really only need it for $1\le k\le p$).

Once you have $k^p\equiv k\pmod p$ for all $k$, you can factor out a $k$ if it's nonzero, and get $k^{p-1}\equiv 1\pmod p$ for all $k\not\equiv0\pmod p$.