A Proof of Fermat's Little Theorem


by 2^Oscar
Tags: fermat, proof, theorem
2^Oscar
2^Oscar is offline
#1
Dec6-09, 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 [latex]\displaystyle \binom{p}{k}[/latex] for any k such that [tex]1 \leq k \leq p-1[/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!(p-k)!}[/tex] form.

Could someone please help me finish off the rest of the question? I'm really stumped...


Cheers,
Oscar
Phys.Org News Partner Science news on Phys.org
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
dodo
dodo is offline
#2
Dec6-09, 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 p|r and r|s then p|s, 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.
robert Ihnot
robert Ihnot is offline
#3
Dec6-09, 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.

robert Ihnot
robert Ihnot is offline
#4
Dec12-09, 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^p-1 \equiv 0 \bmod p. [/tex]
What is the induction hypothesis?[tex] K^p-K \equiv 0 \bmod p.[/tex]

What to prove? [tex] (K+1)^p - (k+1) \equiv 0 \bmod p. [/tex]
nomather1471
nomather1471 is offline
#5
Dec12-09, 09:08 PM
nomather1471's Avatar
P: 19
http://www.hizliupload.com//onizleme/475631.jpg
robert Ihnot
robert Ihnot is offline
#6
Dec13-09, 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^p-K \equiv 0 \bmod p [/tex]
The last step by the induction hypothesis.
nomather1471
nomather1471 is offline
#7
Dec13-09, 04:25 PM
nomather1471's Avatar
P: 19
Quote Quote by robert Ihnot View Post
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^p-K \equiv 0 \bmod p [/tex]
The last step by the induction hypothesis.
Is there any problem at my proof?
robert Ihnot
robert Ihnot is offline
#8
Dec13-09, 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