Fermat's little theorem's proof

Thread starter adi1998
Start date Jan 29, 2012
Tags

Proof

In summary, Fermat's little theorem is a fundamental theorem in number theory that states that for any prime number p, a^p - a is always divisible by p. The proof for this theorem involves using mathematical induction and modular arithmetic. It is important because it serves as the basis for other theorems and concepts in number theory and is also used in cryptography. However, there are limitations to this theorem, as it only applies to prime numbers and there are rare cases where it may not hold true. It can be extended to non-prime moduli using Euler's theorem, which is a generalization of Fermat's little theorem.

Jan 29, 2012

adi1998

Can anyone give me the proof for fermat's little theorem?

Mathematics news on Phys.org

Jan 29, 2012

tiny-tim

Science Advisor

Homework Helper

welcome to pf!

hi adi1998! welcome to pf!

adi1998 said:

Can anyone give me the proof for fermat's little theorem?

always try the pf library …

see https://www.physicsforums.com/library.php?do=view_item&itemid=66

Jan 29, 2012

adi1998

Thank
You

1. What is Fermat's little theorem?

Fermat's little theorem is a fundamental theorem in number theory, named after the French mathematician Pierre de Fermat. It states that if p is a prime number, then for any integer a, a^p - a is always divisible by p.

2. What is the proof for Fermat's little theorem?

The proof for Fermat's little theorem involves using mathematical induction and modular arithmetic. It can be shown that for any integer n, a^n - a is always divisible by n. This can be used to prove Fermat's little theorem by setting n=p-1, where p is a prime number.

3. Why is Fermat's little theorem important?

Fermat's little theorem is important because it is the basis for many other theorems and concepts in number theory. It is also used in cryptography, as it provides a way to generate large prime numbers and test for their primality.

4. Are there any limitations to Fermat's little theorem?

Yes, there are limitations to Fermat's little theorem. It only applies to prime numbers, so it cannot be used to determine if a non-prime number is composite. Additionally, there are some rare cases where it may not hold true, known as Fermat pseudoprimes.

5. Can Fermat's little theorem be extended to non-prime moduli?

Yes, Fermat's little theorem can be extended to non-prime moduli using Euler's theorem. Euler's theorem states that if a and n are coprime integers, then a^phi(n) is congruent to 1 mod n, where phi(n) is Euler's totient function. This is a generalization of Fermat's little theorem and can be used to prove similar results for non-prime moduli.