# A Proof of Fermat's Little Theorem

by 2^Oscar
Tags: fermat, proof, theorem
 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 $$\frac{r}{s}$$. ii) Deduce that p divides the binomial coefficient $\displaystyle \binom{p}{k}$ for any k such that $$1 \leq k \leq p-1$$. iii) Now use the binomial theorem to prove by induction on n that p divides n$$^{p}$$ - 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 $$\frac{p!}{k!(p-k)!}$$ form. Could someone please help me finish off the rest of the question? I'm really stumped... Cheers, Oscar
 P: 687 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 $$\frac r s$$ and apparently expects it to be an integer.
 PF Patron 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.
PF Patron
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? $$1^p-1 \equiv 0 \bmod p.$$
What is the induction hypothesis?$$K^p-K \equiv 0 \bmod p.$$

What to prove? $$(K+1)^p - (k+1) \equiv 0 \bmod p.$$
 P: 19
 PF Patron 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 $$\frac {p!}{0!p!}$$ will divide out p, and similarly for the last term. Every other term contains p only in the numerator. Thus from the problem, $$(K+1)^P -(K+1)\equiv K^p+1^p -(K+1) \equiv K^p-K \equiv 0 \bmod p$$ The last step by the induction hypothesis.
P: 19
 Quote by robert Ihnot Sure! Correct! If you take an example (x+y)^3 = X^3 + 3x^2(y) + 3x(y^2) + y^3. The fact remains that $$\frac {p!}{0!p!}$$ will divide out p, and similarly for the last term. Every other term contains p only in the numerator. Thus from the problem, $$(K+1)^P -(K+1)\equiv K^p+1^p -(K+1) \equiv K^p-K \equiv 0 \bmod p$$ The last step by the induction hypothesis.
Is there any problem at my proof?
 PF Patron 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!

 Related Discussions Linear & Abstract Algebra 20 Linear & Abstract Algebra 38 General Math 14 Linear & Abstract Algebra 5 General Math 65