A Proof of Fermat's Little Theorem

In summary, Oscar attempted to prove Fermat's Little Theorem using the binomial theorem, but failed to bring it all together. He needs help from someone else to finish the proof.
  • #1
2^Oscar
45
0
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
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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 beginning n=1.
 
Last edited:
  • #4
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]
 
  • #5
http://www.hizliupload.com//viewer.php?id=475631.jpg [Broken]
 
Last edited by a moderator:
  • #6
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.
 
Last edited:
  • #7
robert Ihnot said:
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?
 
  • #8
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!
 

1. What is Fermat's Little Theorem and why is it important in mathematics?

Fermat's Little Theorem states that if p is a prime number, then for any integer a, a^p - a is divisible by p. This theorem is important because it has numerous applications in number theory, cryptography, and other areas of mathematics.

2. Who discovered Fermat's Little Theorem?

Fermat's Little Theorem was originally stated by French mathematician Pierre de Fermat in the 17th century, but was not proved until much later by Swiss mathematician Leonhard Euler.

3. Can you provide an example of how Fermat's Little Theorem is used in cryptography?

One example of how Fermat's Little Theorem is used in cryptography is in the RSA encryption algorithm. The algorithm relies on the fact that it is easy to raise a number to a power, but difficult to find the original number from its powers. Fermat's Little Theorem helps to ensure the security of this encryption process.

4. Is Fermat's Little Theorem always true for any prime number?

Yes, Fermat's Little Theorem is proven to hold true for any prime number. However, it may not hold true for composite numbers.

5. What are some real-world applications of Fermat's Little Theorem?

Fermat's Little Theorem has many practical applications, including in the fields of cryptography, number theory, and computer science. It is also used in error-correcting codes, primality testing, and in the construction of pseudorandom number generators.

Similar threads

  • Linear and Abstract Algebra
Replies
12
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
811
Replies
4
Views
1K
Replies
8
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
964
Replies
1
Views
705
  • Linear and Abstract Algebra
Replies
28
Views
2K
Replies
15
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
17
Views
4K
Back
Top