Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
@ErickWong: I misunderstood the problem. Sorry. :( –  Babak S. Dec 28 '12 at 18:29

1 Answer 1

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$

share|improve this answer
    
Don't you think we need group theory tag for question, cause the OP is willing to use that tool. –  Babak S. Dec 28 '12 at 11:52
2  
I thought that the OP wanted a proof that does not use group theory –  Amr Dec 28 '12 at 12:02
    
+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. –  Jyrki Lahtonen Dec 28 '12 at 12:06
    
@JyrkiLahtonen , Thank you they are better now. –  Amr Dec 28 '12 at 12:13
1  
+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}$$ –  DonAntonio Dec 28 '12 at 13:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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