Register to reply 
A Proof of Fermat's Little Theorem 
Share this thread: 
#1
Dec609, 12:10 PM

P: 45

Hi guys,
I've been reading a chapter from a book and I've been attempting a question which uses the binomial theorem to prove Fermat's Little Theorem. The question goes as follows: Let p be a prime number: i) Show that if r, s are positive integers such that r divides s, p divides r and p does not divide s, then p divides [tex]\frac{r}{s}[/tex]. ii) Deduce that p divides the binomial coefficient [itex]\displaystyle \binom{p}{k}[/itex] for any k such that [tex]1 \leq k \leq p1[/tex]. iii) Now use the binomial theorem to prove by induction on n that p divides n[tex]^{p}[/tex]  n for all positive integers n. Hence deduce Fermat's Little Theorem. I can handle the first two parts of the question, but I think I may not have showed them in a way which leads onto being able to prove the third part. For i) I said that since r divides s I can express s as some multiple of r, which gets me r in both the numerator and the denominator of the fraction and thus since p divides r p must divide the fraction. I did a similar approach for the second part except using the expanded [tex]\frac{p!}{k!(pk)!}[/tex] form. Could someone please help me finish off the rest of the question? I'm really stumped... Cheers, Oscar 


#2
Dec609, 06:12 PM

P: 688

I imagine that the binomial theorem will come in during the induction step, when you have to say something about (n+1)^p  (n+1).
You may want to revise the statement of the question at I), because something doesn't look right. Divisibility is transitive, so if pr and rs then ps, it cannot be that "p does not divide s" as stated. Maybe it is s who divides r and not the other way around, since the question uses the fraction [tex]\frac r s[/tex] and apparently expects it to be an integer. 


#3
Dec609, 08:43 PM

PF Gold
P: 1,059

r divides s, p divides r and p does not divide s,
This is what looks wrong to Dodo, just ignore it. Now use the binomial theorem to prove by induction on n that p divides n^p  n. What is said about is the Key Statement and a giveaway. For p a prime, just start with the usual begining n=1. 


#4
Dec1209, 01:49 AM

PF Gold
P: 1,059

A Proof of Fermat's Little Theorem
If nobody else wants to say anything, I feel the need to elaborate.
What is the basis? [tex] 1^p1 \equiv 0 \bmod p. [/tex] What is the induction hypothesis?[tex] K^pK \equiv 0 \bmod p.[/tex] What to prove? [tex] (K+1)^p  (k+1) \equiv 0 \bmod p. [/tex] 


#6
Dec1309, 01:25 PM

PF Gold
P: 1,059

Sure! Correct! If you take an example (x+y)^3 = X^3 + 3x^2(y) + 3x(y^2) + y^3. The fact remains that [tex]\frac {p!}{0!p!} [/tex] will divide out p, and similarly for the last term. Every other term contains p only in the numerator.
Thus from the problem, [tex] (K+1)^P (K+1)\equiv K^p+1^p (K+1) \equiv K^pK \equiv 0 \bmod p [/tex] The last step by the induction hypothesis. 


#8
Dec1309, 08:48 PM

PF Gold
P: 1,059

nomather1471: Is there any problem at my proof?
No! I just thought it was a little lengthy writing out all those coefficients. Plus it was a litle difficult to bring it up. I guess I should have left it alone! 


Register to reply 
Related Discussions  
Fermat's Last Theorem, proof by Andrew Wiles  Linear & Abstract Algebra  20  
An Elementary Proof Of Both The Beal Conjecture And Fermat's Last Theorem.  Linear & Abstract Algebra  38  
Fermat's Last Theorem: an amateur proof  General Math  14  
Proof of Fermat's Little Theorem  Linear & Abstract Algebra  5  
Fermat's Last Theorem Proof in WSEAS  General Math  65 