Register to reply

A Proof of Fermat's Little Theorem

by 2^Oscar
Tags: fermat, proof, theorem
Share this thread:
2^Oscar
#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 [itex]\displaystyle \binom{p}{k}[/itex] 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
'Office life' of bacteria may be their weak spot
Lunar explorers will walk at higher speeds than thought
Philips introduces BlueTouch, PulseRelief control for pain relief
dodo
#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
#3
Dec6-09, 08:43 PM
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
#4
Dec12-09, 01:49 AM
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
#5
Dec12-09, 09:08 PM
nomather1471's Avatar
P: 19
robert Ihnot
#6
Dec13-09, 01:25 PM
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
#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
#8
Dec13-09, 08:48 PM
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