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
    Don't you think we need group theory tag for question, cause the OP is willing to use that tool.2012-12-28
  • 2
    I thought that the OP wanted a proof that does not use group theory2012-12-28
  • 0
    +1: Amr I took the liberty of TeXifying the congruences. I think the spacing of parentheses looks nicer this way. If you disagree, then I apologize, and change it back.2012-12-28
  • 0
    @JyrkiLahtonen , Thank you they are better now.2012-12-28
  • 1
    +1 Very nice as it uses directly and in a simple way what the OP assumes: $$\forall 02012-12-28
  • 0
    This in fact is the proof of Fermat's little theorem by Euler. See Weil's "Number Theory: An Approach through History...". I don't have it with me right now, so I can't give a page number, but it's in the chapter on Euler.2012-12-28
  • 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