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.

$\endgroup$
  • $\begingroup$ @ErickWong: I misunderstood the problem. Sorry. :( $\endgroup$ – mrs Dec 28 '12 at 18:29
14
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Don't you think we need group theory tag for question, cause the OP is willing to use that tool. $\endgroup$ – mrs Dec 28 '12 at 11:52
  • 2
    $\begingroup$ I thought that the OP wanted a proof that does not use group theory $\endgroup$ – Amr Dec 28 '12 at 12:02
  • $\begingroup$ +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. $\endgroup$ – Jyrki Lahtonen Dec 28 '12 at 12:06
  • $\begingroup$ @JyrkiLahtonen , Thank you they are better now. $\endgroup$ – Amr Dec 28 '12 at 12:13
  • 1
    $\begingroup$ +1 Very nice as it uses directly and in a simple way what the OP assumes: $$\forall 0<k<p\;\;,\;\;p\mid\binom{p}{k}$$ $\endgroup$ – DonAntonio Dec 28 '12 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.