7
$\begingroup$

It is known that $p$ divides the binomial coefficient $\binom{p}{i}$ for $1\leq i\leq p-1$. So from the binomial theorem, it is not hard to see $ (a+1)^p\equiv a^p+1 $ modulo $p$.

Is there a way to derive Fermat's little theorem $a^p\equiv a$ mod $p$, without appealing to Lagrange's theorem? I feel like I could say $(\mathbb{Z}/p\mathbb{Z})^\times$ is a cyclic group of order $p-1$, thus $(a+1)^p\equiv a+1$, hence $a+1\equiv a^p+1$, but this seems to miss this point since I would know $a^p\equiv a$ from the get go.

  • 0
    @ErickWong: I misunderstood the problem. Sorry. :(2012-12-28

1 Answers 1

14

We will prove by induction that for all $n\in N$ we have $n^p=n\pmod p$. The base ($n=0$) is easy to verify.

Induction step:


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


(By the induction hypothesis, $n^p\equiv n \pmod p$

  • 0
    @KCD What did he do when $p$ is not prime ? I am referring to the theorem $a^{\phi(n)}=1$ (mod $n$), when $\gcd(a,n)=1$2012-12-28